0257 - Descompunerea unui numar in termeni Fibonacci
Cerință[edit | edit source]
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[edit | edit source]
Programul citește de la tastatură numărul n.
Date de ieșire[edit | edit source]
Programul afișează pe ecran, separaţi prin câte un spaţiu, termenii descompunerii, în ordine descrescătoare.
Restricții și precizări[edit | edit source]
1 ≤ n ≤ 1.000.000.000
Exemplu[edit | edit source]
Date de intrare: 30
Date de ieșire: 21 8 1
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line> def fib(n):
f1, f2 = 1, 1
while f1 + f2 <= n:
f3 = f1 + f2
f1 = f2
f2 = f3
return f2
if __name__ == "__main__":
n = int(input())
while n != 0:
print(fib(n), end=' ')
n = n - fib(n)
</syntaxhighlight>