ALG2
172 Rozdział 6. Derekursywacja
Wzmiankowany powyżej „tajemniczy sposób” nie powinien stanowić niespodzianki dla osób, które mają za sobą lekturę rozdziału 2. Chodzi oczywiście o sprowokowanie serii wywołań rekurencyjnych, które będą pamiętały o naszych intencjach i postępując wg założonych reguł, rozwiążą łamigłówkę.
Zauważmy, że przy przyjętych oznaczeniach mamy a l b l c=01 / i 2 i i, czyli c=3-a-b. Procedura, która rozwiązuje problem wież Hanoi, jest teraz niesłychanie prosta:
hanoLcpf
void hanoi(int n, int a, int b)
(
if (n—1)
cout « "Przesuń dysk nr ”s< n << " z ” « a « " na "<< h << endl;
else
I
hanoi(n-1,a,3-a b);
cout << "Przesuń dysk nr "« n << " z ” « a « " na "« b <<endl; hanoi(n-1,3-a-b,b);
)
Niestety, algorytm ten jest dość kosztowny, bowiem czas jego wykonania wynosi aż (T-l)*t^ gdzie jest czasem pojedynczego przemieszczenia krążka z jednego drążka na inny1. Wynik ten nie jest trudny do uzyskania, ale dla czytelności wykładu zostanie pominięty.
O ile jednak nie możemy specjalnie w ten czas ingerować (sam problem jest dość czasochłonny „z natury”), to możemy nieco ułatwić generację kodu kompilatorowi, eliminując drugie wywołanie rekurencyjne, które spełnia warunek narzucony przez Twierdzenie 1 (patrz str. 170). Przekształcenie procedury hanoi wg podanej tam reguły jest natychmiastowe:
void hanoi2(int n, int a, int b)
(
while (n!-l)
(
hanoi2(n-1,a,3-a-b);
cout « "Przesuń dysk nr ”<< n « " z " << a << " na "<< b « endl; n=n-l; a=3-a-b;
)
cout « "Przesuń dysk nr 1 z " << a << " na "
<< b << endl;
)
Wynik ten nie jest trudny do uzyskania, ale dla czytelności wykładu zostanie pominięty.
Wyszukiwarka
Podobne podstrony:
ALG2 182 Rozdział 6. Derekursywatji 6, Jest to forma niewątpliwie równoważna, cho
ET2 172 Rozdział 10. Polityka turystyczna Poprzez swoje kompetencje organ wojewódzki wpływa na możl
ALG2 22 Rozdział 1. Zanim wystartujemy programowania nic znikły bynajmniej z horyzontu: Dijkstra, H
ALG2 32 Rozdział 2. Rekurencja Wyżej podaliśmy warunki pozytywnego zakończenie programu. W przypadk
ALG2 42 Rozdział 2. Rekurencja 2. m.in. wartości zmiennych tego poziomu (tzw. kontekst). Co więcej,
ALG2 52 Rozdział 2. RekurenZad. 2-4Oto jedno z możliwych rozwiązań: trójkąty ,cpp double y) void nu
ALG2 52 Rozdział 3. Analiza sprawności algorytmów Rys. 3 -
ALG2 72 Rozdział 3. Analiza sprawności algorytmówn o) = i, i = A + O, A = 1. Po t
ALG2 102___Rozdział 5. Struktury danych I ELEMENT *q=inf.głowa; if (pusta()) cout << "(l
ALG2 112 Rozdział 5. Struktury danych 112 Rozdział 5. Struktury danych //rekord informacyjny listy
ALG2 122 Rozdział 5. Struktury danych Czerniak zarabia 3000zl Wynik usunięcia rekordu pracownika za
ALG2 132 Rozdział 5. Struktury da //"w" zostanie "załadowane" wartością zdjętą
ALG2 142 Rozdział 5. Struktury danych a ż do momentu znalezienia właściwego dlań miejsca. Popatrzmy
ALG2 152 Rozdział 5. Struktury danytl 5.; raturn oblicz(w->lcwy)+oblicz(w->prawy); case - :
ALG2 162 Rozdział 5. Struktury danych c) pewien element listy, który odpowiada kryteriom poszukiwań
ALG6 166 Rozdział 6. Derekursywacji kosztuje cenny czas procesora, który dodaje się do ogólnego cza
ALG8 168 Rozdział 6. Derekursywacjł Jak odróżnić powrót z procedury P, który powoduje definitywne j
ALG4 174 Rozdział 6. Derekursywatp 6.4. to dlaczego nie wspomnieliśmy o tym wcześniej, wprowadzając
ALG8 178 Rozdział 6. Derekursywacja 6.! Dużą wadą nowej techniki będzie niemożność łatwego jej
więcej podobnych podstron