3.5 Wieże Hanoi

 

DOWIESZ SIĘ

• na czym polega problem wież Hanoi,
• jak rozwiązać problem wież Hanoi za pomocą algorytmu rekurencyjnego,
• jak zapisać rozwiązanie problemu wież Hanoi w Scratchu.

Typowym przykładem przydatności rekurencji jest problem znany jako wieże Hanoi. Podczas tej lekcji przekonasz się, że zastosowanie wielokrotnej rekurencji bywa naprawdę pomocne.

NA CZYM POLEGA PROBLEM

Na początku świata Brahma postawił w klasztorze w Hanoi wieżę z 64 złotych krążków. Nakazał mnichom przenosić je według ścisłych zasad. Gdy mnisi przeniosą wszystkie krążki i utworzą nową wieżę, nastąpi koniec świata…

Wokół zabawki wprowadzonej na rynek europejski w 1883 r. przez francuskiego matematyka Édouarda Lucasa (czytaj: edułarda lukasa) szybko pojawiło się wiele legend. To jedna z nich. A sama zabawka? Na podstawce znajdują się trzy słupki; na jednym z nich umieszcza się osiem krążków o coraz mniejszych średnicach. Należy przenieść wszystkie krążki na inny słupek z zachowaniem następujących reguł:

• wolno przenosić po jednym krążku,
• nie wolno położyć większego krążka na mniejszym,
• można wykorzystywać trzeci słupek jako pomocniczy.

Rys. 1. Zabawka – wieże Hanoi

• Wykonaj tę grę dla trzech krążków (możesz spróbować zrobić to w pamięci). Powinno ci się udać przenieść wszystkie krążki w siedmiu ruchach.
• Znajdź w Wikipedii animację prezentującą rozwiązanie łamigłówki dla czterech krążków i zapisz kolejne ruchy, które trzeba wykonać.

JAK ROZWIĄZAĆ PROBLEM

To zadanie ma dość proste rozwiązanie rekurencyjne. Jeśli założyć, że przekładanie (n${\displaystyle n}$ – 1) krążków jakoś się uda, to algorytm – rozwiązanie dla n${\displaystyle n}$ krążków może wyglądać tak jak przedstawiono na poniższym rysunku.

1. Stan początkowy dla n${\displaystyle n}$ = 5 krążków.
   

   

2. Przenieś (n${\displaystyle n}$ – 1) krążków ze słupka A na B, potraktuj słupek C jako pomocniczy.
   

   

3. Przenieś n${\displaystyle n}$-ty krążek ze słupka A na C.
   

   

4. Przenieś (n${\displaystyle n}$ – 1) krążków ze słupka B na C; potraktuj słupek A jako pomocniczy. Jeśli nie ma krążków do przenoszenia, następuje koniec gry.
   

   

   Rys. 2. Schemat rozwiązania problemu wież Hanoi

Problem ten jest prezentowany w podręcznikach do informatyki jako przykład rekurencji oraz wykorzystywany podczas testów psychologicznych na kojarzenie i w badaniach neurologicznych. Algorytm znajduje także zastosowanie w schematach wykonywania kopii zapasowych danych czy zarządzaniu projektami.

JAK ZBUDOWAĆ SKRYPT

Skrypt bloku rekurencyjnego wHanoi, zbudowany według tego algorytmu, i wynik jego działania dla n${\displaystyle n}$ = 3 możesz zobaczyć na rys. 3, a wypróbować po uruchomieniu pokazu pod adresem https://scratch.mit.edu/projects/37051896.

Rys. 3. Skrypt wHanoi i jego rozwiązanie dla trzech krążków

Krążki są ponumerowane od najwyższego. Ile ruchów trzeba wykonać? Dla jednego krążka to oczywiście 1 ruch, dla dwóch – 3 ruchy, dla trzech – 7. Dla większej liczby krążków możesz to sprawdzić w projekcie.