Wieże Hanoi  popularna łamigłówka, w której celem jest przeniesienie
piramidy złożonej z N klocków (ułożonych od
największego do najmniejszego) z pozycji początkowej
na pozycję końcową z wykorzystaniem jednej pozycji
pośredniej
Wieże Hanoi
Pozycja początkowa Pozycja pośrednia Pozycja końcowa
3
Wieże Hanoi  popularna łamigłówka, w której celem jest przeniesienie Wieże Hanoi  popularna łamigłówka, w której celem jest przeniesienie
piramidy złożonej z N klocków (ułożonych od piramidy złożonej z N klocków (ułożonych od
największego do najmniejszego) z pozycji początkowej największego do najmniejszego) z pozycji początkowej
na pozycję końcową z wykorzystaniem jednej pozycji na pozycję końcową z wykorzystaniem jednej pozycji
pośredniej pośredniej
Pozycja początkowa Pozycja pośrednia Pozycja końcowa Pozycja początkowa Pozycja pośrednia Pozycja końcowa
Ograniczenia: nie wolno kłaść większego krążka na mniejszy,
nie wolno przenosić więcej niż jeden krążek naraz,
wolno brac tylko krążki leżące na szczycie.
2 4
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Celem jest przełożenie klocków z pozycji początkowej (LEWO) na pozycję końcową Przesuń klocek z pozycji LEWO na pozycję PRAWO
(PRAWO) z wykorzystaniem pozycji pośredniej (ŚRODEK)
5 7
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji LEWO na pozycję ŚRODEK Przesuń klocek z pozycji ŚRODEK na pozycję PRAWO
6 8
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji LEWO na pozycję ŚRODEK Przesuń klocek z pozycji PRAWO na pozycję ŚRODEK
9 11
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji PRAWO na pozycję LEWO Przesuń klocek z pozycji LEWO na pozycję ŚRODEK
10 12
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji LEWO na pozycję PRAWO Przesuń klocek z pozycji ŚRODEK na pozycję LEWO
13 15
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji ŚRODEK na pozycję PRAWO Przesuń klocek z pozycji PRAWO na pozycję LEWO
14 16
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji ŚRODEK na pozycję PRAWO Przesuń klocek z pozycji LEWO na pozycję PRAWO
17 19
Rozwiązanie dla 4 klocków Rozwiązanie dla 4 klocków
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń klocek z pozycji LEWO na pozycję ŚRODEK Przesuń klocek z pozycji ŚRODEK na pozycję PRAWO
Gotowe !
W sumie 15 ruchów (2^N-1)
18 20
Idea rozwiązania rekurencyjnego Idea rozwiązania rekurencyjnego
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Doprowadz
do sytuacji, w której wszystkie klocki prócz największego są na pozycji Ponownie wykonaj całe zadanie dla N-1 krążków: przesuń N-1 klocków z pozycji
pośredniej początkowej na pozycję końcową z wykorzystaniem pozycji pośredniej, z tym, że
teraz pozycją początkową jest ŚRODEK, końcową PRAWO a pośrednią LEWO
Innymi słowy wykonaj całe zadanie dla N-1 krążków: przesuń N-1 klocków z pozycji
początkowej na pozycję końcową z wykorzystaniem pozycji pośredniej, z tym, że dla
N-1 klocków pozycją początkową jest LEWO, końcową ŚRODEK a pośrednią PRA21
WO
23
Idea rozwiązania rekurencyjnego Idea rozwiązania rekurencyjnego
(3)
(1)
(2)
LEWO ŚRODEK PRAWO LEWO ŚRODEK PRAWO
Przesuń największy klocek na pozycję końcową Oczywiście tej operacji również dokonujemy rekurencyjnie, poprzez: (1) przełożenie
N-2 górnych klocków na pozycję pośrednią (LEWO), (2) przesunięcie spodniego
Klocek największy nie będzie już ruszany klocka na pozycję końcową (PRAWO) i (3) ponowne przełożenie N-2 górnych klocków
na pozycję końcową (PRAWO).
Itd.
22 24