0257 - Descompunerea unui numar in termeni Fibonacci
De la Universitas MediaWiki
Cerință
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
Rezolvare
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)
