ALG5

6.6. Klasyczne schematy derekursywacji 185

Sprawdźmy teraz, czy w istocie podane wyżej przekształcenie działa. W tym celu powróćmy do programu przykładowego ze strony 179 (zapisanego teraz w nieco zwięźlejszej postaci).

odwroH.cpp

void P2()

(

if (a!=0)

I

a—;

P2();

b=b+ (++a);

1

ei.se

b=l;

)

Stosując omawiane przekształcenie otrzymujemy natychmiast:

void P?_TTF.RAT()

{

int k=0;

while (a!=0)

i

a—; k++;

)

while(k—!0) h>=b+ (++a) ; i

Wykonanie programu potwierdza równoważność obu procedur.

6.6.3.Schemat z podwójnym wywołaniem rekurencyjnym

Ostatni omawiany schemat rekurencyjny należy do tzadko spotykanych w praktyce. Ponadto dowód na poprawność transformacji jest dość złożony, dlatego poniżej przeanalizujemy jedynie gotowy rezultat i omówimy przykład zastosowania transformacji.

Oto dwie rówmoważne formy algorytmów:

int N=l; void P()

(

do

{

while(warunek(x)) (

A (x > ;

N*=2;

)

Olx) ;

Wyszukiwarka

Podobne podstrony:
ALG1 6.6. Klasyczne schematy derekursywacji 181 wykonują systematycznie pewne stałe fragmenty kodu
ALG3 6,6. Klasyczne schematy derekursywacji 183 ( A<x) i PO ; D(x) i } also C(X)
ALG5 3.4. Przykład 3: Wpadamy w pułapkę 657«)-/t(l + N + Nt[i]). T{n) ~ max(A AV[/]). Początek jest
ALG5 3.4. Derekursywacja z wykorzystaniem stosu 175 Metoda ta jest podzielona na dwa etapy: l zamia
M-14.01.02 185 6.4.    Sprawdzenie robót spawalniczych 6.4.1.
Kaufland uncleu0x300?llback Kaufland Sprawdź Teraz w naszym małym wielkim sklepie jeszcze więce
zaplanowano sprawdzenie dysku, system Windows sprawdzi teraz dysk. chkdsk sprawdza pliki (poziom 1 z
INSTRUKCJA PUG@5 5 3001 Schemat 19, część 3
RATY 0% NA WYBRANE MASZYNY SPRAWDŹ TERAZ > AUTORYZOWANY DILER ORAZ
A* CORMAY Poznaj naszą ofertę dedykowaną weterynarii Sprawdź teraz
Ponad ^nowych marek w ofercie* Ready for Tomorrow • od Iipca2019 r. Sprawdź teraz ► Sprawdź teraz
Furorę robiły zwłaszcza zabawne filmiki powielające klasyczny schemat. Oto w jednym przedziale siedz

więcej podobnych podstron