Wieże Hanoi to łamigłówka z trzema słupkami i kilkoma krążkami o różnych rozmiarach. Na początku wszystkie krążki leżą na pierwszym słupku jak wieża, największy na dole. Zadanie: przenieść całą wieżę na trzeci słupek. Wolno przenosić jeden krążek naraz i nigdy nie wolno położyć większego krążka na mniejszym.
Według legendy, która towarzyszyła zabawce sprzedawanej w XIX wieku, mnisi w świątyni przekładają 64 złote krążki, a gdy skończą, nastąpi koniec świata. Zagadkę sprowadził do Europy francuski matematyk Édouard Lucas w 1883 roku. Czy trzeba się bać? Zaraz to policzymy.
Zacznijmy od małych wież
- 1 krążek: przenosimy go prosto na cel. To 1 ruch.
- 2 krążki: mały na słupek pomocniczy, duży na cel, mały na duży. To 3 ruchy.
- 3 krążki: kombinacja, którą zobaczysz w animacji poniżej. To 7 ruchów.
Myślenie rekurencyjne
Zauważ, co dzieje się w animacji. Aby przenieść największy krążek (3), musiałeś najpierw zdjąć z niego dwa mniejsze, czyli przenieść wieżę z 2 krążków na słupek pomocniczy. Potem jeden ruch dużego krążka, a na koniec znów przenieść wieżę z 2 krążków, tym razem na cel. Wieża z 3 krążków to dwie wieże z 2 krążków plus jeden ruch.
Ten sposób myślenia przydaje się daleko poza łamigłówkami. Wielka matrioszka zawiera mniejszą matrioszkę, która zawiera jeszcze mniejszą. Aby je policzyć, wystarczy otworzyć największą i policzyć resztę, a resztę liczymy tak samo.
Ile ruchów potrzeba?
Niech R(n) oznacza liczbę ruchów dla n krążków. Z rozumowania wyżej: R(n) = R(n − 1) + 1 + R(n − 1) = 2 · R(n − 1) + 1. Zaczynamy od R(1) = 1 i liczymy:
- R(2) = 2 · 1 + 1 = 3,
- R(3) = 2 · 3 + 1 = 7,
- R(4) = 2 · 7 + 1 = 15,
- R(5) = 2 · 15 + 1 = 31,
- R(6) = 2 · 31 + 1 = 63.
Liczby 1, 3, 7, 15, 31, 63 to potęgi dwójki zmniejszone o 1: 2¹ − 1, 2² − 1, 2³ − 1… Zatem dla n krążków minimum to 2ⁿ − 1 ruchów. Każdy dodatkowy krążek podwaja pracę.
Rekurencja także gdzie indziej
Silnię liczby zapisujemy tak samo: 5! = 5 · 4!, a 4! = 4 · 3!, i tak dalej, aż dojdziemy do 1! = 1. Wynik 5! = 120 składa się z kolejnych mniejszych wyników. Taki zapis jest krótki, bo każdy krok wygląda identycznie. Ćwicz zawsze dwie rzeczy: jak sprowadzić problem do mniejszego i kiedy się zatrzymać. Gdybyś pominął drugą część, rozumowanie nigdy by się nie skończyło.
Prosty wzorzec dla ręki
Najmniejszy krążek porusza się co drugi ruch. Jeśli wieża ma nieparzystą liczbę krążków (np. 3), najmniejszy krążek wędruje cyklicznie A → C → B → A… Jeśli parzystą (np. 2 lub 4), wędruje A → B → C → A… W pozostałych ruchach jest tylko jeden dozwolony ruch innym krążkiem, więc nie musisz niczego wymyślać. Wystarczy pilnować tego rytmu.
Zadania
1. Ile ruchów wymaga wieża z 5 krążków? A z 7?
Pokaż rozwiązanie
2. Wypisz ruchy dla wieży z 2 krążków (A – start, B – pomocniczy, C – cel). Krążki: 1 (mały), 2 (duży).
Pokaż rozwiązanie
3. Przy jednym ruchu na sekundę ile czasu zajmie wieża z 7 krążków?
Pokaż rozwiązanie
4. Wieża z 10 krążków ma 1023 ruchów. Ile ruchów ma wieża z 11 krążków?
Pokaż rozwiązanie
Typowe błędy
- Przenoszenie największego krążka zbyt wcześnie, gdy mniejsze jeszcze na nim leżą.
- Zbędne ruchy, które wydłużają rozwiązanie ponad minimum.
- Zgadywanie wzoru bez sprawdzenia: 2ⁿ − 1, nie 2ⁿ.
Zapamiętaj
- Minimalna liczba ruchów dla n krążków to 2ⁿ − 1.
- Duży problem to dwa razy mniejszy problem plus jeden ruch.
- Każdy nowy krążek podwaja liczbę ruchów.
- Najmniejszy krążek rusza się co drugi ruch.
Spróbuj samodzielnie w grze Wieże Hanoi. Licznik pokaże Ci, ile ruchów to minimum.
Komentarze