Изменения

Перейти к: навигация, поиск

Решение рекуррентных соотношений

205 байт добавлено, 17:45, 25 марта 2018
Определения
}}
Во многих задачах полезно знатьЧасто мы хотим найти решение рекуррентного соотношения, есть ли у рекурсивной функции нерекурсивная или как еще говорят замкнутая форма (англ. ''closed-form''), то есть получение которое явно выражает <tex>f(n)</tex> в виде аналитически заданной функции-ый член последовательности. Например, рекурсивная функциядля рекурсивной функции, описывающая описывающей сумму чисел натурального ряда:
<tex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}</tex>
 
<tex>n<tex>-ый член может быть записан в виде
 
Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Method'').
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Method'').
302
правки

Навигация