ALG1

6.3. Kilka przykładów derekursywacji algorytmów 171

Musimy przełożyć krążki z drążka oznaczonego « na drążek b, posiłkując się drążkiem pomocniczym c - tak jednak postępując, aby w żadnym przypadku krążek o mniejszej średnicy nie został przykryty przez inny krążek o większej średnicy. Przyjmuje się, że krążek o numerze / ma najmniejszą średnicę, a ten o numerze n - największą. Ponadto, dla potrzeb programu wynikowego oznaczymy krążki a. b i c jako 0, 1 i 2.

Analiza rekurencyjna zadania prowadzi nas do następujących spostrzeżeń;

•    jeśli mamy do czynienia z jednym krążkiem, to zadanie sprowadza się do przemieszczenia go z a na h (przypadek elementarny);

•    jeśli mamy do czynienia z n>2 krążkami, to przy założeniu, że umiemy przemieścić n-1 krążków z jednego drążka na drugi, zadanie sprowadza się do wykonania przemieszczeń symbolicznie przedstawionych na rysunku 6-2.

Rys. 6 - 2.

Wieże Han o i -sposób rozwiązywania.

ETAP 2

ETAP I

a)    b)    r)

ri

i

a)    b)    c)

ETAP 4

E l AP J

	I	{_ □ c_	—s _J

a)    b)    c)

a)    b)    c)

Etap pierwszy przedstawia sytuację wyjściową. Załóżmy teraz, że przenieśliśmy jakimś „tajemniczym” sposobem n-1 krążków z drążka a na drążek c Na drążku a pozostał nam największy krążek, ten o numerze n. W tym momencie dotarliśmy do sympatycznie prostego przypadku elementarnego i już bez żadnej dodatkowej magii możemy krążek o numerze n przenieść z drążka a na drążek b. Znajdziemy się w ten sposób w sytuacji oznaczonej na rysunku jako etap 3. Jak doprowadzić do rozwiązania łamigłówki dysponując taką konfiguracją danych?

Pouczeni doświadczeniem etapu pierwszego, postąpimy dokładnie w taki sam sposób: weźmiemy n-l kiążków z drążka c i przemieścimy je tajemniczym sposobem na drążek b...