Seminář PHP – Gymnázium Kolín

Úloha 4: Fibonacciho posloupnost

Začátečník pole (array) cyklus for rekurence MathML

Cíl úlohy

Vytvořte skript, který vygeneruje a vypíše n-tý člen Fibonacciho posloupnosti. Výpočet realizujte efektivně pomocí jednorozměrného pole a cyklu. Vypište jak výsledný člen, tak i předcházející členy posloupnosti.

Rekurentní definice Fibonacciho posloupnosti (MathML)

Každý další člen posloupnosti je součtem dvou bezprostředně předcházejících členů:

F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 1} + F_{n - 2} pro n \geq 3

Začátek posloupnosti: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Úvahy a doporučený postup řešení

Inicializace pole: Začněte inicializací prvních dvou prvků: $fib[1] = 1; $fib[2] = 1;.
Cyklické sčítání: Od třetího indexu spusťte cyklus for ($i = 3; $i <= $n; $i++) a do pole ukládejte $fib[$i] = $fib[$i-1] + $fib[$i-2];.
Úspora paměti: Zamyslete se – je nutné uchovávat celé pole všech členů, nebo stačí pamatovat si pouze poslední dvě hodnoty?
Čitelné formátování čísel: Velká čísla formátujte pomocí number_format($cislo, 0, ',', ' ') s mezerou jako oddělovačem tisíců.

Doplňující otázky k zamyšlení a náměty na rozšíření

1. Co je to zlatý řez ( $φ \approx 1,618$ )? Spočtěte a vypište poměr $\frac{F_{n}}{F_{n - 1}}$ – ke které hodnotě tento podíl konverguje?
2. Kde se s Fibonacciho posloupností a zlatým řezem setkáváme v přírodě? (spirála ulity měkkýšů, uspořádání semen slunečnice, větvení stromů).
3. Proč je řešení cyklem s polem $O (n)$ nesrovnatelně rychlejší než naivní rekurzivní funkce s exponenciální složitostí $O (2^{n})$ ?
4. Který člen Fibonacciho posloupnosti je nejvyšší, který se vejde do 64bitového celého čísla PHP_INT_MAX ( $F_{92} = 7 540 113 804 746 346 429$ )?

Vyzkoušejte funkční řešení: Otevřít vzorovou úlohu fibonacci.php