Wieża Hanoi to łamigłówka, która powstała w XIX w. Początkowo grało się w nią ceramicznymi krążkami na terenie Chin oraz Japonii w Azji Wschodniej. Wokół gry krąży legenda mówiąca, że mnisi w świątyni Brahmy rozwiązują łamigłówkę z 64 złotymi krążkami. Podobno, gdy zagadka zostanie rozwiązana nastąpi koniec świata. Choć wizja jest przerażająca to nie ma czego się obawiać. Wyjaśnienie można znaleźć w dalszej części artykułu.
Gra składa się z trzech palików na których umieszczone zostają krążki wyglądem przypominające wieże. Krążki są różnej średnicy i początkowo są ustawione na paliku od największego do najmniejszego na wierzchu. Zadanie polega na przeniesieniu n krążków z pierwszego palika na drugi. Podczas rozwiązywania zadań należy pamiętać, że:
Spróbuj zmierzyć się z ułożeniem Wieży Hanoi.
Przypadek Wieży Hanoi z jednym krążkiem jest bardzo prostym przypadkiem, który wymaga zaledwie jednego ruchu. Jest nim przełożenie z palika numer 1 na palik numer 2. Przyjmując, że funkcja L(n) określa ile jest potrzebnych ruchów do rozwiązania zagadki o n krążkach to L(1) = 1.
Dla dwóch krążków sytuacja zaczyna się nieco komplikować, ponieważ najpierw trzeba dostać się do krążka numer 2 przekładając mniejszy krążek na palik 3, a potem na 2 palik przełożyć kolejno największy i najmniejszy krążek. Warto zauważyć, że L(2) = 3.
Wieża z Hanoi to już zadanie, które może zacząć sprawiać trudności i jest pierwszym przypadkiem, gdy wyraźnie widać co należy robić, aby rozwiązać wieżę Hanoi dla dowolnej ilości krążków. Największy klocek znajduje się na dnie wieży. Oznacza to, że najpierw należy przełożyć całą wieżę na klocku na palik tymczasowy. Pozostała wieże można wtedy ułożyć tak jakby to była wieża Hanoi o jeden krążek mniej.
Do przełożenia dwóch górnych klocków należy wykonać 3 ruchy na palik tymczasowy (tj. 3). Następnie przełożenie największego klocka to tylko jeden ruch. Z kolei przeniesienie wieży z dwoma krążkami L(2) = 3. Podsumowując przypadek dla 3 krążków L(3) = 7. Poniżej znajduje się gotowe rozwiązanie.
Kolejne liczby funkcji L to 1, 3, 7, ?, ale pytanie ile funkcja wyniesie dla n = 4. W celu rozwiązania Wieży Hanoi należy przełożyć wieżę o wysokości n - 1 z pierwszego palika na tymczasowy, przełożyć potem klocek na drugi palik, a następnie przełożyć wszystkie paliki z tymczasowego na końcowy. Oznacza to, że L(n) = L(n - 1) + 1 + L(n - 1) = 2L(n - 1) + 1. Wyznaczona zależność rekurencyjna doprowadza do określenia postaci jawnej wzory L(n) = 2n - 1.
Poniżej została udostępniona możliwość przygotowania wieży Hanoi o dowolnej liczbie krążków. Można też wybrać czas przechodzenia pomiędzy kolejnymi animacjami.
| Krążków n | |
|---|---|
| Opóźnienie (ms) |
Metoda rozwiązywania Wieży Hanoi początkowo może nie być intuicyjna, ale program rozwiązujący wieże Hanoi można napisać na podstawie algorytmu podanego wcześniej. Jak wiadomo wykorzystuje on rekurencję, więc program może rozwiązać zadanie przy pomocy tej samej metody. Poniżej znajduje się funkcja, która wypisuje listę ruchów do wykonania, aby rozwiązać zagadkę.
Przedstawiony algorytm potrafi wypisać listę ruchów od momentu, gdy wszystkie krążki znajdują się na paliku początkowym. Wykonuje on rekurencję, gdy (2.) jest chociaż jeden krążek do przesunięcia. Wykonywane instrukcje to (3.) Przeniesienie wieży o wysokości h - 1 na palik tymczasowy. (4.) Wypisania ruchu (można tutaj zastąpić np. aktualizacją listy krążków na każdy paliku). (5.) Przesuń wieżę z palika tymczasowego na palik końcowy używając palika początkowego jako tymczasowego (wtedy jest on pusty).
W celu wypisania wszystkich ruchów dla wieży z trzema krążkami wystarczy poniższa funkcja main():
W tym przypadku program wypisze na ekran: