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 inny¹. 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;

)

1

Wynik ten nie jest trudny do uzyskania, ale dla czytelności wykładu zostanie pominięty.