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.

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...

Wyszukiwarka

Podobne podstrony:
ALG3 6.3. Kilka przykładów derekursywacji algorytmów 173 Pokaźna grupa procedur rekurencyjnych dość
ALG1 6.6. Klasyczne schematy derekursywacji 181 wykonują systematycznie pewne stałe fragmenty kodu
Zdjęcie0248 147 DLA DZIECI I ML0D7IF.ŻY. ■1^7 twórców bawili literackich. Można podać zaledwie kilka
pokazać odniesienie algorytmu do ułamków dziesiętnych: Nauczyciel podaje kilka przykładów do
ALG1 3.2. Przykład 1: Jeszcze raz funkcja silnia... 61 W obliczeniach wykonywanych przez programist
zaproponować kilka przykładowych (ale zróżnicowanych) ćwiczeń pozwalających poloniście rozwijać tę
zaproponować kilka przykładowych (ale zróżnicowanych) ćwiczeń pozwalających poloniście rozwijać tę
IMG64 POSTRZEGAJĄCYStereotypy i stereotypizacja: kilka przykładów    nta W poprzedni
Zastosowanie nowoczesnych metod TI do rozwiązywania codziennych problemów Podaje kilka przykładów

więcej podobnych podstron