Czego się nauczysz
Przepiszesz definicję ciągu Fibonacciego wprost na funkcję rekurencyjną i zobaczysz w drzewie wywołań, dlaczego taki program dla n = 40 liczy kilka minut.
Po co ci to na maturze
Pytanie „ile razy zostanie wywołana funkcja dla n = 6” to klasyka zadań na analizę algorytmów rekurencyjnych. Do tego program napisany wprost z definicji potrafi liczyć minutami, a odpowiedź trzeba podać w czasie egzaminu.
Etapy lekcji
Spis lekcji
Teoria
6 rozdziałówNie zaczęte- 1.1Definicja wprost na kodDwa przypadki bazowe i dwa wywołania w jednym kroku.
- 1.2Najpierw cała lewa gałąźfib(n - 2) rusza dopiero wtedy, gdy fib(n - 1) skończy się w całości.
- 1.3To samo liczone od zeraDrzewo wywołań pokazuje, że te same wartości liczą się wiele razy.
- 1.4Ile kosztuje drzewoLiczba wywołań rośnie mniej więcej 1,6 razy z każdym kolejnym n.
- 1.5Jedno wywołanie zamiast dwóchFunkcja oddaje dwa sąsiednie wyrazy naraz, jak kartka z okienkiem.
- 1.6PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.