Wie
ż
e Hanoi
2
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
Pozycja pocz
ą
tkowa
Pozycja po
ś
rednia
Pozycja ko
ń
cowa
3
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
Pozycja pocz
ą
tkowa
Pozycja po
ś
rednia
Pozycja ko
ń
cowa
4
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
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.
Pozycja pocz
ą
tkowa
Pozycja po
ś
rednia
Pozycja ko
ń
cowa
5
Rozwi
ą
zanie dla 4 klocków
Celem jest przeło
ż
enie klocków z pozycji pocz
ą
tkowej (LEWO) na pozycj
ę
ko
ń
cow
ą
(PRAWO) z wykorzystaniem pozycji po
ś
redniej (
Ś
RODEK)
LEWO
Ś
RODEK
PRAWO
6
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
Ś
RODEK
LEWO
Ś
RODEK
PRAWO
7
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
8
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji
Ś
RODEK na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
9
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
Ś
RODEK
LEWO
Ś
RODEK
PRAWO
10
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji PRAWO na pozycj
ę
LEWO
LEWO
Ś
RODEK
PRAWO
11
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji PRAWO na pozycj
ę
Ś
RODEK
LEWO
Ś
RODEK
PRAWO
12
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
Ś
RODEK
LEWO
Ś
RODEK
PRAWO
13
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
14
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji
Ś
RODEK na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
15
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji
Ś
RODEK na pozycj
ę
LEWO
LEWO
Ś
RODEK
PRAWO
16
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji PRAWO na pozycj
ę
LEWO
LEWO
Ś
RODEK
PRAWO
17
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji
Ś
RODEK na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
18
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
Ś
RODEK
LEWO
Ś
RODEK
PRAWO
19
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji LEWO na pozycj
ę
PRAWO
LEWO
Ś
RODEK
PRAWO
20
Rozwi
ą
zanie dla 4 klocków
Przesu
ń
klocek z pozycji
Ś
RODEK na pozycj
ę
PRAWO
Gotowe !
W sumie 15 ruchów (2^N-1)
LEWO
Ś
RODEK
PRAWO
21
Idea rozwi
ą
zania rekurencyjnego
Doprowad
ź
do sytuacji, w której wszystkie klocki prócz najwi
ę
kszego s
ą
na pozycji
po
ś
redniej
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
ą
PRAWO
LEWO
Ś
RODEK
PRAWO
22
Idea rozwi
ą
zania rekurencyjnego
Przesu
ń
najwi
ę
kszy klocek na pozycj
ę
ko
ń
cow
ą
Klocek najwi
ę
kszy nie b
ę
dzie ju
ż
ruszany
LEWO
Ś
RODEK
PRAWO
23
Idea rozwi
ą
zania rekurencyjnego
LEWO
Ś
RODEK
PRAWO
Ponownie 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
teraz pozycj
ą
pocz
ą
tkow
ą
jest
Ś
RODEK, ko
ń
cow
ą
PRAWO a po
ś
redni
ą
LEWO
24
Idea rozwi
ą
zania rekurencyjnego
LEWO
Ś
RODEK
PRAWO
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
klocka na pozycj
ę
ko
ń
cow
ą
(PRAWO) i (3) ponowne przeło
ż
enie N-2 górnych klocków
na pozycj
ę
ko
ń
cow
ą
(PRAWO).
Itd.
(1)
(2)
(3)