Czego się nauczysz
Dopiszesz do funkcji rekurencyjnej słownik z policzonymi wynikami i zobaczysz, jak drzewo wywołań fib(n) kurczy się do 2n - 1 wywołań.
Po co ci to na maturze
Gdy zadanie podaje ciąg wzorem rekurencyjnym, np. liczbę krów w kolejnych latach, program przepisany wprost ze wzoru dla większych lat się nie doczeka wyniku. Zapamiętywanie policzonych wartości sprawia, że kończy w ułamku sekundy.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Zapisz wynik, zanim go oddaszSłownik, w którym kluczem jest argument, a wartością policzony wynik.
- 1.2Drzewo bez powtórekDruga prośba o tę samą wartość kończy się od razu, bez poddrzewa.
- 1.3Ile teraz kosztujeZ wykładniczej liczby wywołań robi się 2n - 1. Stos zostaje tak samo głęboki.
- 1.4Inne funkcje i kilka argumentówKluczem jest komplet argumentów. Przy dwóch argumentach to krotka.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.