A kiújulás képletű

A kiújulás képletű - a képlet a forma a_n = f (n, a_, a_, \ pontok, a_) , expresszáló minden távon a szekvencia a_n keresztül p korábbi tagok és esetleg egy szekvenciát távú n.

Általános problémák számítástechnikában kiújulás képletek a tárgya az elmélet rekurzív függvények.

Az ismétlődés egyenlet egy egyenlet, amely kapcsolódik a több egymást követő tagok egy számszerű sorrendben. Sequence kielégíti ezt az egyenletet nevezzük visszatérő szekvenciát.

1 n = 0; \\ (n-1)! \ Cdot n, n \ geqslant 1. \ end

1 n = 1; \\ F_ + F_, n \ geqslant 2. \ end

  • Az érték az integrál \ Textstyle I_n = \ int \ sin ^ n x \, dx kielégíti a rekurziós képlet: I_n = \ frac x> + \ fracI_.
  • A megoldás a differenciálegyenlet Bessel y + (1 / x) y „+ (1- \ nu ^ 2 / x ^ 2) y = 0 Ez felírható hatványsorba: y = \ sum \ limits_ ^ a_n x ^.
Az együtthatók megállapításához a_n, elegendő annak megállapítása, hogy 4n (n + \ nu) a_n + A_ = 0 minden n ⩾ 1. Ezután a kapott azonnal ismert eredmény: a_n = \ fracn! (1+ \ nu) (2+ \ nu) \ cdots (n + \ nu)>.
  • Oldalhosszúság számának megduplázásával az oldalán a beírt szabályos n-szög. a _ = \ sqrt >>, \ qquad n \ ge 2,
ahol R - sugara a körülírt kör.

Lineáris rekurzív egyenletek

Lineáris rekurzív sorozat állandó együtthatós formában van:

itt n - nem negatív egész, F_ - egy számsorozat, a_, a_, \ ldots, a_ - állandók, a_ \ ne 0, \ Varphi (n) - adott funkció n.

Homogén lineáris rekurzív egyenletek

Tegyük fel, hogy egy számsorozat F_, F_, \ dots kielégíti a homogén lineáris rekurzív egyenlet F_ + a_f_ + a_f_ + \ ldots + a_f_ = 0, ahol n - nem negatív egész, a_, \ ldots, a_ - előre beállított állandók, és a_ \ ne 0.

Jelöljük F (z) generáló függvény F_, F_, \ dots. Készítünk egy polinomot K (z) = 1 + a_z + a_z ^ + \ ldots + a_z ^. Ez a többtagú lehet tekinteni, mint generáló függvény 1, a_, a_, \ ldots, a_, 0, 0, \ dots. Tekintsük a termék generátorfüggvény C (Z) = F (z) K (Z). tényező C_ a Z ^ és r> 0 viszonya határozza meg C_ = F_ 0 + \ ldots + F_ 0 + F_ a_ + \ ldots + F_ 1 = F_ + a_f_ + \ ldots + a_f_ és nulla. Ez azt jelenti, hogy a polinom C (Z) Úgy tartja a legtöbb R-1, ezért azt a mértéket, a számláló a racionális függvény F (z) = \ frac kevesebb, mint a nevező.

A karakterisztikus polinomja egy lineáris rekurzív egyenlet egy polinom g (Z) = z ^ + a_z ^ + \ ldots + A_. A gyökerek a polinom nevezzük a jellemző. A karakterisztikus polinomja felírható g (Z) = (Z- \ alpha _) ^> (z- \ alpha _) ^> \ cdots (z- \ alpha _) ^>, ahol \ Alpha_, \ ldots, \ alpha_ - különböző jellemző gyökerek, E_, \ ldots, E_ - a sok jellegzetes gyökerek, E_ + e _ + \ ldots + E_ = r.

A karakterisztikus polinom g (Z) és a polinom K (Z) kapcsolja össze K (z) = z ^ g (\ frac). Így

Racionális függvény felírható összegeként frakciói:

Minden lövés ez a kifejezés formája van \ Beta (1- \ alpha z) ^, így lehet bővíteni egy hatványsor formájában

együttható Z ^ N ez a szám egyenlő

Következésképpen a generáló függvény F (z) = \ sum _ ^ (\ sum_ ^ P_ (n) \ alpha _ ^) z ^ és f _ = \ sum_ ^ P_ (n) \ alpha_ ^ jelentése az általános megoldás a lineáris rekurzív egyenlet, ahol a P_ (n) - polinom n foka legfeljebb E_-1.

Tegyük fel, hogy megoldást találni F_-F_ + F_ = 0 c peremfeltételek F_ = 1 és F_ = 1.

alkalmazások

Van egy általános képletű, amely kifejezi a általános kifejezés egy lineáris ismétlődő szekvencia a gyökereken keresztül a karakterisztikus polinommal. Például, a Fibonacci ilyen képlet a képlet Binet. Az ismétlődés képletek leírására használjuk az időt az algoritmus rekurzív eléréséhez is. Ebben a képletben, a szükséges idő a megoldás a bemeneti mennyiség n. kifejezve az idő a döntést támogató részfeladatok. [1]

jegyzetek

irodalom

Kapcsolódó cikkek