Cho số nguyên dương n.Hãy cho biết có bao nhiêu dãy số nguyên dương có tổng các phần tử trong dãy bằng n.
Dữ liệu vào :Vào từ file count.inp chứa duy nhất một số nguyên n<=1018
Kết quả:Ghi ra file count.out một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho 123456789.
VD: INPUT: 3
OUTPUT:4
GIẢI THÍCH
1. (1,1,1);
2.(1,2);
3.(2,1);
4.(3)
số đầu tiên, ta có thể chọn là 1 hoặc 2 hoặc 3.... hoặc n. Nên ta có công thức truy hồi.
Gọi S[k] là số cách phân tích số k.
S[n]=S[0]+S[1]+S[2]+..+S[n-2]+S[n-1].
S[n]=(S[0]+S[1]+S[2]+..+S[n-2])+S[n-1].
S[n]=S[n-1]+S[n-1].
Vậy ta có thuật toán
S[1]=1
S[k]=2^(k-1)*n
const fi = 'count.inp';
fo = 'count.out';
var n:longint;
function tim(n:longint):longint;
begin
if(n=1) then tim:=1
else tim:=tim(n-1)+tim(n-1);
end;
procedure xuly;
var i,j:longint;
begin
writeln(tim(n));
end;
begin
assign(input, fi); reset(input);
readln(n);
close(input);
assign(output, fo); rewrite(output);
xuly;
close(output);
end.
Anh ơi sao mình lại có công thức như vậy ạ? Em chưa hiểu lắm. Em cảm ơn
Chưa hiểu chỗ nào bạn? Vì số đầu tiên có thể là 1 hoặc 2,3,...,n nên S[n] = S[n-1]+S[n-2]+..+S[n-n]
