Wieże Hanoi

Michał Leśniewski, Warszawa 2006r. - 28 Liceum

„Wieże Hanoi” to bardzo stara łamigłówka matematyczna, która powstała na podstawie azjatyckiej legendy:

„W wielkiej świątyni Benares w Hanoi, pod kopułą, która zaznacza środek świata, znajduje się płytka z brązu, na której umocowane są trzy diamentowe igły, wysokie na łokieć i cienkie jak talia osy. Na jednej z tych igieł, w momencie stworzenia świata, Bóg umieścił 64 krążki ze szczerego złota. Największy z nich leży na płytce z brązu, a pozostałe jeden na drugim, idąc malejąco od największego do najmniejszego. Jest to wieża Brahma. Bez przerwy we dnie i w nocy kapłani przekładają krążki z jednej diamentowej igły na drugą, przestrzegając niewzruszonych praw Brahma. Prawa te chcą, aby kapłan na służbie brał tylko jeden krążek na raz i aby umieszczał go na jednej z igieł w ten sposób, by nigdy nie znalazł się pod nim krążek mniejszy. Wówczas, gdy 64 krążki zostaną przełożone z igły, na której umieścił je Bóg w momencie stworzenia świata, na jedną z dwóch pozostałych igieł, wieża, świątynia, bramini rozsypią się w proch i w jednym oka mgnieniu nastąpi koniec świata.”

Przełożenie 64 krążków zgodnie ze wskazaną zasadą, trwałoby całe wieki, dlatego też rozwiązując łamigłówkę przyjmujemy, że wieża ma najwyżej kilkanaście krążków.

Rozwiązanie

Po kilku próbach rozwiązania tej łamigłówki, każdy zapewne zauważy, że istnieje jedna zasada, pozwalająca rozwiązać łamigłówkę dla dowolnej ilości krążków. Po jej opanowaniu każdy bez najmniejszego problemu poradzi sobie nawet z bardzo wysoką wieżą. Dzięki odnalezieniu tej zasady można ułożyć algorytm oparty na rekurencji, który automatycznie rozwiąże każdą wieżę.

Oto zasada przełożenia i krążków z wieży a na b wykorzystując wieżę c:

1) Jeżeli i = 1, to przełóż tylko jeden krążek i zakończ.

2) Przekładamy (i – 1) krążków z a na c (wykorzystując tę samą zasadę od początku)

3) Przekładamy 1 krążek z a na b

4) Przekładamy (i – 1) krążków przełożonych wcześniej na c na b (wykorzystując tę samą zasadę od początku)

Algorytm

Załóżmy, że przełóż(a, b) to procedura, która przekłada jeden krążek z wierzchołka wieży a na wierzchołek wieży b.

Oto uproszczona procedura hanoi(a, b, c, i), która przekłada i krążków z wieży a na wieżę b wykorzystując wieżę c.

void hanoi(int a, int b, int c, int i)

{

// Warunek zakończenia rekurencji (do przełożenia mamy tylko 1 krążek)

if (i == 1) przełóż(a, b);

// W innym przypadku:

else

{

// REKURENCJA! przełóż (i – 1) krążków z wieży źródłowej na pomocniczą

hanoi(i - 1, a, c, b);

// Przełóż jeden krążek z wieży źródłowej na docelową

przełóż(a, b);

// REKURENCJA! Przełóż (i – 1) krążków z wieży tymczasowej na docelową

hanoi(i - 1, c, b, a);

}

}

Demonstracja