Strona główna » Algorytmy » Artykuły » Wieża Hanoi - Analiza gry

Wieża Hanoi - Analiza gry

Wieża Hanoi

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.

Zasady

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:

  1. można przekładać tylko jeden krążek naraz
  2. przekładany krążek można zdjąć tylko z wierzchu palika i położyć na wierzchu drugiego palika
  3. nie wolno kłaść większego krążka na mniejszy

Spróbuj zmierzyć się z ułożeniem Wieży Hanoi.

Rozpatrywanie przypadków

Przypadek trywialny

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.

Dwa krążki

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.

Trzy krążki

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.

Podsumowanie

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.

Dowolny przypadek

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)

Implementacja

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ę.

  1. void przesunWieze(int wys, int pZ, int pDo, int pTemp) {
  2.   if (wys >= 1) {
  3.     przesunWieze(wys - 1, pZ, pTemp, pDo);
  4.     cout << "Przesun z " << pZ << " do " << pDo << endl;
  5.     przesunWieze(wys - 1, pTemp, pDo, pZ);
  6.   }
  7. }

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).

Testowanie funkcji

W celu wypisania wszystkich ruchów dla wieży z trzema krążkami wystarczy poniższa funkcja main():

  1. int main () {
  2.   przesunWieze(3, 1, 2, 3);
  3.   system("pause");
  4.   return 0;
  5. }

W tym przypadku program wypisze na ekran:

  1. Przesun z 1 do 2
  2. Przesun z 1 do 3
  3. Przesun z 2 do 3
  4. Przesun z 1 do 2
  5. Przesun z 3 do 1
  6. Przesun z 3 do 2
  7. Przesun z 1 do 2