3. Rekurziós összefüggések Flashcards
Rekurzív összefüggés
Egy rekurzív összefüggés azt jelenti, hogy az aktuális elemet (jelölve $a_n$) a korábbi elemekből számoljuk ki az $F$ függvény segítségével. Tehát $a_n = F(a_{n-1}, a_{n-2}, …, n)$. Ez azt jelenti, hogy az $a_n$ értékét az előző elemek ($a_{n-1}, a_{n-2}, …$) és az aktuális $n$ szám kombinálásával kapjuk meg a $F$ függvény segítségével.
rekurzív összefüggés: a_n:= F(a_{n-1}, a_{n-2},…,n)
Kezdeti érték probléma
a_1:= A_1,…,a_k:=A_k
Adottak $A_1, A_2, …, A_k$ komplex számok, és egy rögzített $k$ természetes szám. Ekkor a kezdeti érték probléma az, hogy meg kell határoznunk az $a_1, a_2, …, a_k$ értékeket. Ezek a kezdeti értékek szolgálnak kiindulópontként a rekurzív összefüggés alkalmazásához. Tehát az $a_1, a_2, …, a_k$ értékeket a megadott $A_1, A_2, …, A_k$ számokkal tesszük egyenlővé.
Fibonacci sorozat
$f_n=f_{n-1}+f_{n-2} (n>2), f_0=0, f_1=1$
Fibonacci sorozat Lineáris, másodrendű, állandó, homogén együtthatós rekurzió
Lineáris: mivel A1,…,AK fokszámai mind 1. Ha a fokszám nagyobb lenne 1-nél már nem lineáris rekurzióról beszélnénk.
másodrendű: mert 2 előző eredményre van szükség a(n) kiszámolásához.
állandó: mert $f(n-1) és f(n-2)$-höz tartozó együtthatók komplex számok $(1f(n-1) + 1f(n-2))$. Akkor nem lenne pl. állandó, ha $nf(n-1) +nf(n-2)$ lenne.
homogén együtthatós: mert a(n)-t meg tudjuk adni kizárólag az előző eredményekkel, nincs szükség egyéb számra/eredményre.
Hanoi tornyai:
h_n=2^n-1, h_0=0, h_1=1
Hanoi tornyai Lineáris, elsőrendű, állandó, inhomogén együtthatós rekurzió
Lineáris: mivel A1,…,AK fokszámai mind 1. Ha a fokszám nagyobb lenne 1-nél már nem lineáris rekurzióról beszélnénk.
elsőrendű: mert 1 előző eredményre van szükség $a(n)$ kiszámolásához.
állandó: mert $f(n-1) és f(n-2)$-höz tartozó együtthatók komplex számok $(1f(n-1) + 1f(n-2))$. Akkor nem lenne pl. állandó, ha $nf(n-1) +nf(n-2)$ lenne.
inhomogén együtthatós: mert nem elég, ha tudjuk az előző eredményt, még pluszban hozzá is kell adnunk 1-et.
