0257 - Descompunerea unui numar in termeni Fibonacci

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

<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>