289
Se consideră şirul Fibonacci, definit astfel: f
1
=1
, f
2
=1
, f
n
=
f
n-1
+
f
n-2
, dacă n>2
.
Cerinţa
Se dă un număr natural n
. Să se descompună în sumă cu număr minim de termeni ai şirului lui Fibonacci.
Date de intrare
Programul citește de la tastatură numărul n
.
Date de ieşire
Programul afișează pe ecran, separaţi prin câte un spaţiu, termenii descompunerii, în ordine descrescătoare.
Restricţii şi precizări
1 ≤ n ≤ 1.000.000.000
Exemplu
Date de intrare
30
Date de ieșire
21 8 1
#include <bits/stdc++.h> using namespace std; int fib(int n) { int f1 = 1, f2 = 1, f3 ; while(f1 + f2 <= n) { f3 = f1 + f2; f1 = f2; f2 = f3; } return f2; } int main() { int n; cin>>n; while(n!=0) { cout<<fib(n)<<" "; n=n-fib(n); } return 0; }
Comentarii