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)