Kezdőlap


Feladat:	I.25	Korcsoport: -	Nehézségi fok: -
Füzet:	2002/május, 297. oldal		PDF \| MathML
Témakör(ök):	Feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A Zeckendorf tétel alapján minden természetes szám egyértelműen előállítható Fibonacci számok összegeként úgy, hogy $n = F_{k_{1}} + F_{k_{2}} + ... + F_{k_{r}}$ , ahol $\forall i (1 \leq i < r) : k_{i} \geq k_{i + 1} + 2$ , és $k_{r} \geq 2$ . A Fibonacci számokat az alábbi módon számolhatjuk:

\begin{matrix} F_{k} = {\begin{matrix} 0 & ha k = 0 \\ 1 & ha k = 1 \\ F_{k - 1} + F_{k - 2} & ha k > 1. \end{matrix} \end{matrix}

Készítsünk programot (I25.PAS,

...

), amely adott

n

(

1 \leq n \leq 10 000 000

) természetes számot felbont Fibonacci számok összegére! (A megoldásban a hatékonyságot is értékeljük.)