View source for 0257 - Descompunerea unui numar in termeni Fibonacci

== Cerință ==

Se dă un număr natural n. <br />
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'''<br />
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>