ALG1

3.7. Analiza programów rekurencyjnych 71

Cały ten bagaż wzorów był naprawdę niezbędny! Dla zilustrowania metody rozwiążemy proste zadanie.

3.7.2.Ilustracja metody na przykładzie

Spójrzmy jeszcze raz na Przykład z §3.2. Otrzymaliśmy wtedy następujące równanie:

7X0)-1,

T(n) = 1 + T(n -1).

Spróbujmy je rozwiązać nowo poznaną metodą.

ETAP 1 Poszukiwanie równania charakterystycznego:

Z postaci ogólnej SRL=T(n)-T(n-l) wynika, że RC=x-l.

ETAP 2 Pierwiastek równania charakterystycznego:

Jest to oczywiście r=l.

ETAP 3 Równanie ogólne.

RO=Arn, gdzie A jest jakąś stalą do odnalezienia. Ponieważ r=l, to RO=A (7 podniesione do dowolnej potęgi da nam oczywiście I). Stalą A wyliczymy dalej.

ETAP 4 Poszukiwanie równania szczególnego:

Wiemy, że u(n,m) = l (jeden jest wielomianem stopnia zero!). Ponadto l jest pierwiastkiem pierwszego stopnia równania charakterystycznego. Tak więc: S=ri’c=nc.

Pozostaje nam jeszcze do odnalezienia stała c. Wiemy, że RS musi spełniać pierwotne równanie rekurencyjne, zatem po podstawieniu go jako T(n) otrzymamy:

n-c = 1 + (zz — \)c, rt c =    1 + n c-c,

c =    1.

ETAP 5 Poszukiwanie ostatecznego rozwiązania:

Wiemy, że ostatecznym rozwiązaniem równania jest suma RC) i RS: T(n)=RO+RS= A+nc=A+n. Stalą A możemy z łatwością wyliczyć poprzez podstawienie przypadku elementarnego:

Wyszukiwarka

Podobne podstrony:
ALG3 3.7. Analiza programów rekurencyjnych 737X1) = 1 + 1 = 2, -2 + 7 T(n) = 1 + 1 + 71 Widać już,
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
ALG5 3.7. Analiza programów rekurencyjnych 75 otrzymując w efekcie: =26„_, +3log, 3} _ frównanie li
ALG9 3.7. Analiza programów rekurencyjnych 69 W tym paragrafie przedstawiona zostanie metoda mająca
ALG1 2.2. Ilustracja pojęcia rekurencji 31 od psychologii zachowań dziecka chwyciłby się za głowę z
146 4 Analiza programów publicystycznych ja/dowe - zawsze wtedy gościem był urzędujący prezydent bąd
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
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
ALG1 i 2.10. Rozwiązania i wskazówki do zadań 51Zad. 2-3 Program nie należy do zbyt skomplikowanych
ALG1 3.2. Przykład 1: Jeszcze raz funkcja silnia... 61 W obliczeniach wykonywanych przez programist
higeina 21 Przykłady programu świetlnego dla kurcząt-brojlerów Wiek Godzin światła na
oooooooo Analiza statyczna konstrukcji przy użyciu MES #000000000Etapy analizy w programie MES Użyci
img004 14 - Eurypides . Tragrdit kuk. Rozbija on cały ten porządek, opętujc całe społeczeństwo, wypę

więcej podobnych podstron