Czego się nauczysz
Nauczysz się rozwiązywać wieże Hanoi trzema linijkami rekurencji i policzysz, skąd bierze się 2ⁿ − 1 ruchów.
Po co ci to na maturze
Wieże Hanoi to klasyczny przykład w zadaniach na analizę algorytmów rekurencyjnych: ile ruchów potrzeba, co wypisze program dla trzech krążków, który krążek rusza się w danym ruchu.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Największy krążek na końcu drogiŻeby ruszyć największy krążek, wszystkie mniejsze muszą leżeć na trzecim słupku.
- 1.2Skąd 2ⁿ − 1Każdy dołożony krążek podwaja pracę i dokłada jeden ruch.
- 1.3Słupki zmieniają roleTen sam słupek raz jest celem, raz pomocą. Kolejność argumentów decyduje o wszystkim.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.