TONGFIBO Biểu diễn tổng các số Fibonaci

Đề bài

Cho số tự nhiên N và dãy số Fibonaci: 1, 1, 2, 3, 5, 8, ....

Yêu cầu: biểu diễn N thành tổng của của ít nhất các số Fibonaci khác nhau?

Input: số tự nhiên N (N ≤ 10^6) 

Output: các số Fibonacci theo thứ tự từ lớn đến nhỏ có tổng bằng N

Ví dụ

Input

16

Output

13 3

Giải

Đầu tiêu ta tạo mảng số fibonacci

f[0]:=1;f[1]:=1;
for i:=1 to n do
    f[i]:=f[i-1]+f[i-2]; 

  Ta sẽ tìm số Fibonacci gần với số N nhất. Đây sẽ chính là số hạng đầu tiên nằm trong dãy kết quả. Sau đó, lấy hiệu của số N và số Fibonacci gần với số N nhất, tiếp tục tìm số Fib gần với hiệu trên và cứ thế cho đến khi hiệu đó là một số Fib. Kết quả các số Fibonacci sẽ được liệt kê theo thứ tự từ lớn đến nhỏ.

while n>0 do
    //Tim so fibonaci j gan n nhat
    i:=1;
    while f[i]<=n do
        inc(i);
        j:=f[i-1];
        write(j,' ');
        //Tính hieu còn lai 

        n:=n-j;

Code Pascal

var n:longint; 

    f:array[0..1000] of int64;

procedure taofibo(n:longint);
Var i:longint;
begin
    f[0]:=1;
    f[1]:=1;
    i:=1;
    while f[i]<n do
    begin
        inc(i);
        f[i]:=f[i-1]+f[i-2];
    end;
end;

procedure giai;
var i,j:longint;
begin
    taofibo(n);
    while n>0 do
    begin
        //Tim so fibonaci j gan n nhat
        i:=1;
        while f[i]<=n do inc(i);
        j:=f[i-1];
        write(j,' ');
        //Tính hi?u còn l?i
        n:=n-j;
    end;
end; 

begin
    assign(input,'tongfibo.inp');reset(input);
    assign(output,'tongfibo.out');rewrite(output);
    read(n);
    giai;
end.