ALG0

ALG0



170


Rozdział 6. Oerekursywaci


6.3.


Uwaga: Wywołanie rekurencyjne procedury P zawarte w jakiejkolwiek pętli, rp:

void P(int n)

I

while(V)

(

Instrl;

P(n-l);

}

)

nie jest uważane za terminalne, bow iem w zależności od warunku V, wywol* nie P(n-l) może, ale nie musi być wykonywane jako ostatnie.

Twierdzenie 1 Następujące procedury PI i P2 są sobie wzajemnie równowai ne, pod warunkiem że PI zawiera tylko jedno rekurencyjut wywołanie terminalne.

void P2(x)

(

while(!Cond(x)) (

InstrŻ(x); x=F(x);

)

Instrl(x);

)


void fi(x)

(

if (Cond(x))

Instrl(x); else (

Instr2(x);

PI(F(x))

I

)

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

Wypróbujmy teraz świeżo nabytą wiedzę na „nieśmiertelnym’' przykładzie tzw. wież Hanoi. Jest to łamigłówka o dość legendarnym rodowodzie — w co wnikać nie będziemy podczas naszych wywodów, koncentrując się raczej na problemie logicznym i sposobie rozwiązania go.

iy) i końcowa (z prawej) dla 4 krążków

O


Zadanie jest następujące: marny do dyspozycji n krążków o malejących średnicach, każdy z nich posiada wydrążoną dziurkę, która umożliwia nadzianie go na jeden z 3 wbitych w ziemię drążków'. Na rysunku 6-1 jest przedstawiona sytuacja początkowa (z lewej stron

r~

A-

r

i

jL

_j

»)    b)    c)


Rys. 6-1.    T,

Wieże Hanoi    r- y

- prezentacja

problemu.    j

»)    b)


Wyszukiwarka

Podobne podstrony:
ALG0 150 Rozdział 5. Struktury danytl Jak jednak obejrzeć zawartość drzewa, które tak pieczołowicie
ALG0 30 Rozdział 2. Rekurencja 2.2 potwornie skomplikowany: klocków jest cala masa i niespecjalnie
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
ALG4 184 Rozdział 6. Oerekursywa przetestować, czy wszystkie „zaległe” jej wywołania zostały już
ET0 170 Rozdział 10. Polityka turystyczna z. planem promocji opracowywanym przez organizację. Dział
ALG0 20 Rozdział 1. Zanim wystartujemy (Na marginesie warto dodać, że przedsiębiorstwo Hollcritha
Alg0 60 Rozdział 3. Analiza sprawności algorytmów •    Znak graficzny 3 należy czyta
ALG0 70 Rozdział 3. Analiza sprawności algorytmów Przykład: SRL=xn-3x„.i+2 x„ -2=0 daje
ALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. Sortowanie
ALG0 100 Rozdział 5. Struktury danyi z tych przypadków w istniejącej liście trzeba znaleźć miejsce
ALG0 110 Rozdział 5. Struktury danych Rysunek 5-9 zawiera już kilka nowości w porównaniu z tym, co
ALG0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
Alg0 120 Rozdział 5. Struktury danych i if (pos!=q) rsturn(O);    II element nie
ALG0 130 Rozdział 5. Struktury danych Symboliczny stos znajdujący się pod każdą z sześciu grup inst
ALG0 140 Rozdział 5. Struktury danych porządek. Czy czasem owa procedura nie jest na tyle kosztowna
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
ALG8 168 Rozdział 6. Derekursywacjł Jak odróżnić powrót z procedury P, który powoduje definitywne j
ALG6 46_ _ Rozdział2. Rekurencja rekurencyjnych jest pamięcioźerność: wielokrotne wywołania rekuren

więcej podobnych podstron