Wieże Hanoi (ang. The Towers of Hanoi) są łamigłówką wymyśloną w 1883 roku przez matematyka francuskiego Edouarda Lucasa. Łamigłówka ta zbudowana jest z deseczki, na której znajdują się trzy patyczki w równych odstępach. Na pierwszym patyczku nasunięte są drewniane krążki o coraz mniejszych średnicach.
Celem jest przesunięcie wszystkich krążków z patyczka 0 na patyczek 2 wg następujących reguł:
-
naraz można przenosić tylko po jednym krążku,
-
krążek zdjęty z patyczka musi być nasunięty na jeden z pozostałych dwóch patyczków,
-
krążek można nasunąć na patyczek, jeśli jest on pusty lub zawiera krążek większy.
Łamigłówkę tę można prosto rozwiązać wykorzystując zasady rekurencji.
Załóżmy, że mamy jeden krążek. Wtedy rozwiązanie jest oczywiste - krążek przenosimy z patyczka 0 na 2 i zadanie jest zakończone:
Teraz przyjmijmy, że nasza wieża składa się z dwóch krążków. Startowym jest patyczek 0, a docelowym jest patyczek 2.
Rozwiązaniem będzie przeniesienie najpierw wierzchniego krążka na patyczek pomocniczy 1 (robimy to rekurencyjnie poprzednim sposobem przyjmując patyczek startowy 0 i docelowy 1). Następnie krążek większy przenosimy na patyczek docelowy 2 i znów rekurencyjnie przenosimy mniejszy krążek z patyczka pomocniczego 1 na docelowy 2.
Jeśli krążków jest 3, to najpierw dwa pierwsze przenosimy na
patyczek 1, stosując powyższą metodę przy założeniu, że
wyjściowym patyczkiem jest patyczek 0, a docelowym patyczek
1. Teraz przenosimy krążek największy z patyczka startowego
0 na docelowy 2. Pozostaje nam rekurencyjnie przenieść dwa
pozostałe krążki z patyczka 1 (który
przyjmujemy jako startowy) na patyczek docelowy 2.
Dla większej liczby krążków problem przyjmuje ten sam schemat postępowania:
n - liczba krążków do przeniesienia
A - patyczek startowy
B - patyczek pomocniczy
C - patyczek docelowy
przenieś(A,C,B,n)
jeśli n > 1, to
przenieś(A,B,C,n-1)
przesuń krążek z patyczka A na patyczek C
jeśli n > 1, to przenieś (B,C,A,n-1)