ALG5
3.7. Analiza programów rekurencyjnych 75
otrzymując w efekcie:
=26„_, +3log, 3} _
frównanie liniowe. bo=0 J
Zadanie w tej postaci nadaje się już do rozwiązania! Po dokonaniu niewielkich obliczeń możemy otrzymać: b„=(2„-l)\og^J, co ostatecznie daje
o _ _ ,2»-l
c* l i “ J •
3.7.5.Funkcja Ackermanna, czyli coś dla smakoszy
Gdyby inale dzieci znały się odrobinę na informatyce, to rodzice na pewno by je straszyli nie kominiarzem, ale funkcją Ackermanna. Jest to wspaniały przykład ukazujący, jak pozornie niegroźna „z wyglądu” funkcja rckurcncyjna może być kosztowna w użyciu. Spójrzmy na listing:
a.cpp
int A(int n, int p)
I
if (n~0) return 1;
if ((p==0)Si(n>=l)) if (n==i) return 2; else
return n+2; if ( (p>=l)&&(n>=l))
return A(A(n-',p),p-1);
I
Pytanie dotyczące tego programu brzmi: jaki jest powód komunikatu Slack overflow! (ong. przepełnienie stosu) podczas próby wykonania go? Komunikat ten sugeruje jednoznacznie, iż podczas wykonania programu nastąpiła znaczna ilość wywołań funkcji Ackermanna. Jak znaczna, okaże się już za chwilę...
Pobieżna analiza funkcji A prowadzi do następującego spostrzeżenia:
V« > 1, A(n. 1) = A(A(n-1,1),0) = A(n-1,1) + 2,
co daje natychmiast
Vm > I, /4(m,I) = 2«.
Wyszukiwarka
Podobne podstrony:
ALG1 3.7. Analiza programów rekurencyjnych 71 Cały ten bagaż wzorów był naprawdę niezbędny! Dla zil
ALG3 3.7. Analiza programów rekurencyjnych 737X1) = 1 + 1 = 2, -2 + 7 T(n) = 1 + 1 + 71 Widać już,
ALG9 3.7. Analiza programów rekurencyjnych 69 W tym paragrafie przedstawiona zostanie metoda mająca
ALG5 35 2.4. Niebezpieczeństwa rekurencji2.4.1.Ciąg Fibonacciego Naszym pierwszym zadaniem jest nap
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
-75- Takiej analizy programu i jego realizacji dokonał:ar kilka razy. Po przerobieniu określonej czę
ALG2 32 Rozdział 2. Rekurencja Wyżej podaliśmy warunki pozytywnego zakończenie programu. W przypadk
ALG3 2.3. Jak wykonują się programy rekurencyjne? 332.3. Jak wykonują się programy rekurencyjne? Do
ALG6 36 Rozdział 2. Rekurencja każemy. W rozdziale 9 zostanie omówiona ciekawa technika programowan
ALG5 2.7. Myślenie rekurencyjne 45 Przypadkiem elementarnym będzie tutaj narysowanie jednej pary kw
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
ALG5 3.1. Dobre samopoczucie użytkownika programu 55 Wcale nie jest aż tak dobrze z szybkością wspó
ALG5 Rozdział 6Derekursywacja Podjęcie tematu przekształcania algorytmów rekurencyjnych na ich post
ALG5 7,3. Transformacja kluczowa 195 tylko, aby jako wynik otrzymać pewną liczbę, którą można późni
oooooooo Analiza statyczna konstrukcji przy użyciu MES #000000000Etapy analizy w programie MES Użyci
Podstawy chemii, ćwiczenia laboratoryjne7 w wyniku analizy, tak aby nie otrzymać zbyt małej lub duż
więcej podobnych podstron