0257 - Descompunerea unui numar in termeni Fibonacci

From Bitnami MediaWiki
Revision as of 18:29, 7 January 2023 by Heres.Gabriela (talk | contribs) (Pagină nouă: == 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: '''2...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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>