Dãy Fibonaci là dãy gồm các số: 1, 1, 2, 3, 5, 8, …. được xác định bởi công thức sau:
F1=1, F2=1, Fi=Fi-1+Fi-2 với i>2.
Em hãy biểu diễn một số tự nhiên N thành tổng của ít nhất các số Fibonaci khác nhau.
Dữ liệu vào: cho file FIBO.INP chứa số N (N ≤ 2000000000)
Dữ liệu ra: ghi ra file FIBO.OUT biểu diễn số N thành tổng của ít nhất các số Fibonaci khác nhau.
Ví dụ:
FIBO.INP FIBO.OUT
129 129 = 89 + 34 + 5 + 1
Hoặc
FIBO.INP FIBO.OUT
8 8 = 8
Program BTT;
Uses crt;
Var n,x,y,z: qword;
Begin
Clrscr;
Write(‘Nhap n: ‘); Readln(n);
Repeat
x:=1; y:=0;
Repeat
z:=x+y;
x:=y;
y:=z;
Until z>n;
Write(x,’ ‘);
n:=n-x;
Until n=0;
Readln
End.