ALG9
3.7. Analiza programów rekurencyjnych 69
W tym paragrafie przedstawiona zostanie metoda mająca charakter o wiele ogólniejszy. Ma ona swoje uzasadnienie matematyczne, którego z powodu jego skomplikowania nie będę przedstawiał. Osoby szczególnie zainteresowane stroną matematyczną powinny dotrzeć bez kłopotu do odpowiedniej literatury (patrz uwagi zamieszczone we wstępie rozdziału).
3.7.1.Terminologia
Lektura kilku następnych paragrafów wymaga od nas poznania terminologii, którą będziemy się dość często posługiwać. Pomimo „groźnego” wyglądu, zrozumienie poniższych definicji nie powinno Czytelnikowi sprawić szczególnych kłopotów.
Szereg rekurencyjny liniowy SRL jest to szereg o następującej postaci:
r
x
H+r.wIłO
oznaczenia:
u(n.m) nierekurencyjna reszta równania, będąca wielomianem stopnia m i zmiennej n. Przykładowo:
• jeśli u(n,m)—3n+1, to mamy wielomian stopnia pierwszego;
• jeśli u(n,»i)=2, to jest to wielomian stopnia zerowego.
uwagi:
• współczynniki a, są dowolnymi liczbami rzeczywistymi;
• r jest liczbą całkowitą.
Skomplikowaną postacią tego wzoru nie należy się przejmować, jest to po prostu sformalizowany zapis ogólnego równania rekurencyjnego, podany raczej gwoli formalności niż w jakimś praktycznym celu.
Równanie charakterystyczne RC jest to wielomian sztucznie stworzony na podstawie równania rekurencyjnego, powstały wg wzoru:
r
Równanie to można rozwiązać, otrzymując rozkład postaci:
r
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ż,
ALG5 3.7. Analiza programów rekurencyjnych 75 otrzymując w efekcie: =26„_, +3log, 3} _ frównanie li
Rozdział 4Wykorzystanie teorii wartości ekstremalnych (EVT) W tym rozdziale przedstawiona zostanie m
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
ALG!0 210 Rozdział 8. Przeszukiwanie tekstów Zaprezentowany w tym paragrafie algorytm wykorzystuje k
2, Programy studiów 1. stopnia W tym rozdziale przedstawione są programy studiów stacjonarnych 1. st
Rozdział 11.7. Psychologia stosowana W tym rozdziale przedstawione zostaną, wraz z krótką
Scan9 Do analizy programu wykonującego funkcje logiczne zapisanego w formie STL przydatne mogą być
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ę
ALG9 5.B. Zbiory 1595.8. Zbiory Implementacja programowa zbiorów matematycznych napotyka na szereg
oooooooo Analiza statyczna konstrukcji przy użyciu MES #000000000Etapy analizy w programie MES Użyci
więcej podobnych podstron