Как найти общую формулу по рекуррентной формуле - Сайт, где вы сможете решить свои вопросы

Рекуррентная формула — формула вида ${displaystyle a_{n}=f(n,a_{n-1},a_{n-2},dots ,a_{n-p})}$ , выражающая каждый член последовательности a_n через предыдущих членов и номер члена последовательности .

Общая проблематика вычислений с использованием рекуррентных формул является предметом теории рекурсивных функций.

Рекуррентным уравнением называется уравнение, связывающее несколько подряд идущих членов некоторой числовой последовательности. Последовательность, удовлетворяющая такому уравнению, называется рекуррентной последовательностью.

Примеры[править | править код]

Функция факториала натурального числа удовлетворяет рекуррентной формуле:

${displaystyle n!={begin{cases}1,&n=0;\(n-1)!cdot n,&ngeqslant 1.end{cases}}}$

Числа Фибоначчи задаются линейной рекуррентной формулой:

${displaystyle F_{n}={begin{cases}0,&n=0;\1,&n=1;\F_{n-1}+F_{n-2},&ngeqslant 2.end{cases}}}$

Чтобы определить коэффициенты a_n

, достаточно установить, что ${displaystyle 4n(n+nu )a_{n}+a_{n-2}=0}$

для всех

. После чего сразу получается известный результат:

${displaystyle a_{n}={frac {(-1)^{n}a_{0}}{2^{2^{n}}n!(1+nu )(2+nu )cdots (n+nu )}}.}$

Длина стороны при удвоении числа сторон вписанного правильного n-угольника:

${displaystyle a_{2n}={sqrt {2R^{2}-2R{sqrt {R^{2}-{frac {a_{n}^{2}}{4}}}}}},qquad ngeq 2,}$

где

— радиус описанной окружности.

Линейные рекуррентные уравнения[править | править код]

Линейное рекуррентное уравнение с постоянными коэффициентами имеет вид:

${displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+ldots +a_{r}f_{n}=varphi (n).}$

Здесь — неотрицательные целые числа, $f_{{n}}$ — последовательность чисел, ${displaystyle a_{1},a_{2},ldots ,a_{r}}$ — постоянные числа, $a_{{r}}neq 0$ , — заданная функция от .

Однородные линейные рекуррентные уравнения[править | править код]

Предположим, что последовательность чисел ${displaystyle f_{0},f_{1},dots }$ удовлетворяет однородному линейному рекуррентному уравнению ${displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+ldots +a_{r}f_{n}=0}$ , где — неотрицательные целые числа, ${displaystyle a_{1},ldots ,a_{r}}$ — заданные постоянные числа и $a_{{r}}neq 0$ .

Обозначим через F(z) производящую функцию последовательности ${displaystyle f_{0},f_{1},dots }$ . Построим многочлен ${displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+ldots +a_{r}z^{r}}$ . Этот многочлен можно рассматривать как производящую функцию последовательности ${displaystyle 1,a_{1},a_{2},ldots ,a_{r},0,0,dots }$ . Рассмотрим произведение производящих функций . Коэффициент $c_{{n+r}}$ при $z^{{n+r}}$ и определяется соотношением ${displaystyle c_{n+r}=f_{0}0+ldots +f_{n-1}0+f_{n}a_{r}+ldots +f_{n+r}1=f_{n+r}+a_{1}f_{n+r-1}+ldots +a_{r}f_{n}}$ и равен нулю. Это означает, что многочлен C(z) имеет степень самое большее r-1 , следовательно степень числителя рациональной функции $F(z)={frac {C(z)}{K(z)}}$ меньше степени знаменателя.

Характеристическим многочленом линейного рекуррентного уравнения называется многочлен ${displaystyle g(z)=z^{r}+a_{1}z^{r-1}+ldots +a_{r}}$ . Корни этого многочлена называются характеристическими. Характеристический многочлен можно представить в виде ${displaystyle g(z)=(z-alpha _{1})^{e_{1}}(z-alpha _{2})^{e_{2}}cdots (z-alpha _{s})^{e_{s}}}$ , где ${displaystyle alpha _{1},ldots ,alpha _{s}}$ — различные характеристические корни, ${displaystyle e_{1},ldots ,e_{s}}$ — кратности характеристических корней, ${displaystyle e_{1}+e_{2}+ldots +e_{s}=r}$ .

Характеристический многочлен g(z) и многочлен K(z) связаны между собой соотношением ${displaystyle K(z)=z^{r}gleft({frac {1}{z}}right)}$ . Таким образом,

${displaystyle K(z)=(1-alpha _{1}z)^{e_{1}}(1-alpha _{2}z)^{e_{2}}cdots (1-alpha _{s}z)^{e_{s}}.}$

Рациональную функцию можно представить в виде суммы дробей:

${displaystyle F(z)={frac {C(z)}{K(z)}}=sum _{i=1}^{s}sum _{k=1}^{e_{i}}{frac {beta _{ik}}{(1-alpha _{i}z)^{k}}}.}$

Каждая дробь в этом выражении имеет вид $beta (1-alpha z)^{{-k}}$ , поэтому её можно разложить в степенной ряд следующего вида

${displaystyle beta (1-alpha z)^{-k}=beta left[1+(-k)(-alpha z)+ldots +{frac {(-k)cdots (-k-n+1)}{n!}}(-alpha z)^{n}+ldots right]}$

Коэффициент при $z^{n}$ в этом ряду равен

${displaystyle {frac {beta (n+k-1)cdots k}{n!}}alpha ^{n}=beta {binom {n+k-1}{n}}alpha ^{n}=beta {binom {n+k-1}{k-1}}alpha ^{n}.}$

Следовательно, производящая функция ${displaystyle F(z)=sum _{n=0}^{infty }left(sum _{i=1}^{s}p_{i}(n)alpha _{i}^{n}right)z^{n}}$ и $f_{{n}}=sum _{{i=1}}^{{s}}p_{{i}}(n)alpha _{{i}}^{{n}}$ является общим решением линейного рекуррентного уравнения, где $p_{{i}}(n)$ — многочлен от степени самое большее $e_{{i}}-1$ .

Пример

Пусть требуется найти решение уравнения $f_{{n+2}}-f_{{n+1}}+f_{{n}}=0$ c граничными условиями $f_{{0}}=1$ и $f_{{1}}=1$ .

Данное уравнение имеет характеристический многочлен ${displaystyle z^{2}-z+1=(z-alpha _{1})(z-alpha _{2})}$ , где $alpha _{{1}}={frac {1}{2}}+i{frac {{sqrt {3}}}{2}}=e^{{i{frac {pi }{3}}}}$ , $alpha _{{2}}={frac {1}{2}}-i{frac {{sqrt {3}}}{2}}=e^{{-i{frac {pi }{3}}}}$ . Общее решение имеет вид $f_{{n}}=c_{{1}}alpha _{{1}}^{{n}}+c_{{2}}alpha _{{2}}^{{n}}=c_{{1}}e^{{{frac {ipi n}{3}}}}+c_{{2}}e^{{{frac {-ipi n}{3}}}}$ . Подставляя n=0,1 , получаем $c_{{1}}+c_{{2}}=1$ , $c_{{1}}alpha _{{1}}+c_{{2}}alpha _{{2}}=1$ . Получаем значения $c_{{1}}={frac {1}{2}}-i{frac {1}{2{sqrt {3}}}}$ , $c_{{2}}={frac {1}{2}}+i{frac {1}{2{sqrt {3}}}}$ . Таким образом ${displaystyle f_{n}=left({frac {1}{2}}-i{frac {1}{2{sqrt {3}}}}right)left(cos left({frac {pi n}{3}}right)+isin left({frac {pi n}{3}}right)right)+left({frac {1}{2}}+i{frac {1}{2{sqrt {3}}}}right)left(cos left({frac {pi n}{3}}right)-isin left({frac {pi n}{3}}right)right)=cos left({frac {pi n}{3}}right)+{frac {1}{sqrt {3}}}sin left({frac {pi n}{3}}right)}$ .

Приложения[править | править код]

Существует формула, выражающая общий член линейной рекуррентной последовательности через корни её характеристического многочлена. Например, для последовательности Фибоначчи такой формулой является формула Бине.
Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода , выражается через время решения вспомогательных подзадач.^[1]

См. также[править | править код]

Линейная рекуррентная последовательность
Рекурсивная функция
Рекурсия
Основная теорема о рекуррентных соотношениях (упрощенное решение некоторых видов рекуррентных соотношений, возникающих при анализе сложности рекурсивных алгоритмов)

Примечания[править | править код]

↑ Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ = Introduction To Algorithms / И. Красиков. — Издательский дом “Вильямс”, 2005. — С. 79. — 1296 с.

Литература[править | править код]

Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М., издательство=Радио и связь, 1984. — 240 с.

Источник

Время на прочтение
6 мин

Количество просмотров 33K

Пеленгский фермер Бух’ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 3 раза. Но, начиная со второго дня, на ферму повадилась нападать стая страшных зверей долбогрызов, каждый вечер пожирающих вдвое больше хрякоплюхов, чем их было в предыдущий день. Сколько хрякоплюхов будет у фермера на 7-й вечер, если вначале их было 10?

Вы спросили у гаальца, что он думает по поводу этой задачки. После некоторого размышления тот ответил:
— В начале было 10 хрякоплюхов. В первый день они размножились, и к началу второго дня их стало 30. Во второй день они опять размножились (их стало 90), но вечером пришли долбогрызы и съели вдвое больше хрякоплюхов, чем было вчера (в первый день), т.е. 20 штук. Итого, в начале третьего дня получаем 70 хрякоплюхов. Мне кажется, что, продолжая решать таким образом, можно вычислить число хрякоплюхов в любой день.

Это задача из игры «Космические Рейнджеры 2», квест Амнезия.
Попробуем вывести формулу для количества хрякоплюхов на n-ный день, и посчитать для примера количество хрякоплюхов на 32-й день.

Посмотрим на первые несколько дней (я добавил день «0» только для удобства формулы, можно все делать и без него)

	День 1	День 2	День 3
Утро	10	30	70
После размножения	10 * 3 = 30	30 * 3 = 90	70 * 3 = 210
После долбогрызов (вечер)	10 * 3 — 0 * 2 = 30	30 * 3 — 10 * 2 = 70	70 * 3 — 30 * 2 = 150

Нас будет интересовать количество хрякоплюхов на утро n-ного дня, и, несмотря на то, что в задаче спрашивается про вечер, верным будет утреннее количество.
Таким образом, количество хрякоплюхов (на утро) являет собой последовательность

Про эту последовательность мы знаем (по условию задачи) что

Так же, по условию задачи, ночью ничего не происходит, поэтому хрякоплюхи вечером в полном составе без изменений переносятся на утро следующего дня (т.е. количество хрякоплюхов утром равно их количеству вечером предыдущего дня).

Т.е. на утро второго дня их стало

.
На утро третьего дня их уже

	День n-2	День n-1	День n
Утро	$F_{n-2}$	$F_{n-1}$	$F_{n} = 3F_{n-1} - 2F_{n-2}$
После размножения	$3 * F_{n-2}$	$3 * F_{n-1}$	$3 * F_{n}$
После долбогрызов (вечер)	$3 * F_{n-2} - 2 * F_{n-3}$	$3 * F_{n-1} - 2 * F_{n-2}$	$3 * F_{n} - 2 * F_{n-1}$

Начиная со второго дня

$n=2$ действует такая рекуррентная формула:

$F_{n} = 3 * F_{n-1} - 2 * F_{n-2}$

Итого, ещё раз всё вместе

$F_0 := 0 \ F_1 := 10 \ F_{n} = 3 * F_{n-1} - 2 * F_{n-2}$

Мы получили формальное определение последовательности и этого уже достаточно чтобы можно было вручную посчитать сколько будет хрякоплюхов на какой день. Более того, если у нас магическим образом появилась какая-то формула для

$F_n$ , и эта формула выполняется для этих 3-х условий, то эта формула будет тем, что нам нужно.

Мы же будем пытаться получить эту формулу.

Как правило, чтобы что-то найти нужно составить уравнение, поэтому так и поступим.
Наша последовательность

$F$ — это то, что мы хотим найти (точнее, мы хотим получить формулу для её членов).

Будем делать уравнение из последовательностей. Для этого изобретём сложение для последовательностей:

Т.е. сумма последовательностей есть тоже последовательность.

Важно упомянуть что наши последовательности вообще-то бесконечные, и так просто что-то с ними делать нельзя. Нельзя, к примеру, безо всяких оговорок просуммировать все члены последовательности — никто не может бесконечное время сидеть и суммировать.

Бесконечная последовательность — это то, где для любого номера члена мы можем сказать как его посчитать за конечное время. В случае последовательности

$F$ мы как бы говорим: возьмите день0, возьмите день1 и далее потихоньку, шаг за шагом, считайте следующие дни пока не дойдёте до нужного вам.

Для суммы последовательностей мы говорим: если вам нужен 100-й член суммы, то возьмите по 100-му члену из слагаемых последовательностей и сложите их. Нужен миллионный — так же, возьмите миллионный там, возьмите миллионный сям, сложите эти числа и получите что вам нужно.

Это похоже на то, как суммируются многочлены, к примеру:

Можно даже представить себе бесконечный многочлен

где

— просто какие-то символы. И если мы складываем два таких «бесконечночлена», то их сумма будет как раз сумма последовательностей (мы так определили сумму последовательностей).

Тут важно понимать что на самом деле нет никаких бесконечных многочленов, это просто иная но более удобная запись бесконечной последовательности: пишем

, а видим

Теперь придумаем умножение для последовательностей. Просто попарно перемножить члены так же как со сложением не пойдёт — хотя это и будет похоже на умножение, интересных свойств это не даст. Да и хочется чтобы умножение было бы похоже на умножение многочленов.

К примеру, вот так умножаются обычные конечные многочлены:

Берутся и перемножаются: раскрываются скобки, и группируются члены с одной и той же степенью икса

$(a_0 + a_1*x + a_2*x^2) * (b_0 + b_1*x + b_2*x^2) = \ a_0 * (b_0 + b_1*x + b_2*x^2) + a_1*x * (b_0 + b_1*x + b_2*x^2) + \ a_2*x^2 * (b_0 + b_1*x + b_2*x^2) = \ a_0 * b_0 +\ x(a_0*b_1 + a_1*b_0) + \ x^2*text{(...что-то длинное...)} + \ x^3*text{(...что-то длинное...)} + \ x^4*text{(...что-то длинное...)}$

Другими словами, каждый член первого многочлена умножается на каждый член второго.
Каждый с каждым.

Так просто это обобщить на бесконечные последовательности нельзя — опять же, потому что никто не может бесконечное количество раз умножить на бесконечное количество элементов. Тут важно правильно сказать, а именно что пускай n-ный член произведения последовательностей равен

$"A*B"_n := A_0*B_n + A_1*B_{n-1} + A_2 * B_{n-2} + ... + A_n * B_0 = sum_{i=0}^{i=n} A_i*B_{n-i}$

Почему именно так

В самом деле, если вам интересно что стоит на 100-м месте, т.е. какой коэффициент у

$x^{100}$ , то вы вполне можете сказать:

$x^{100}$ может получиться если умножились

$a_0 * b_{100}*x^{100}$ . Также

$x^{100}$ может получиться если умножились

$a_1*x * b_{99}*x^{99}$ . Можно сообразить и привести всю 101 пару членов, которые при перемножении дадут

$x^{100}$ . И после этого упомянуть что больше никак

$x^{100}$ в произведении не может получится.

Теперь мы умеем складывать бесконечные последовательности и так же умеем их перемножать. Можно заметить некоторые хорошие свойства, к примеру что

;

. Мы придумали это сложение и умножение, нужно обязательно проверять что такие свойства выполняются (это «группа» и «кольцо»). Это несложно проверить, и, в целом-то, эти все свойства довольно естественны, особенно для тех кто хоть сколько-то складывал и умножал конечные многочлены.

Попробуем теперь для примера посчитать

. Согласно определению умножения получаем

$"100*F"_n = sum_{i=0}^{i=n} (100, 0, 0, 0, 0, ....)_i*F_{n-i} = 100*F_{n}$

Выглядит логично — умножение последовательности на число даст умножение каждого члена на это число. И это сходится с

Важное замечание:

, где соответственно

Теперь посчитаем

. Так же согласно определению умножения получаем

$"x*F"_n = sum_{i=0}^{i=n} (0, 1, 0, 0, 0, ....)_i*F_{n-i} = F_{n-1} text{при n > 0, либо 0 при n = 0}$

Т.е.

Что, собственно, так же сходится с

Так же получаем что

Это базовые операции над нашей последовательностью, и теперь вот это всё хорошо бы собрать и применить к начальной рекуррентной формуле

$F_{n} - 3 * F_{n-1} + 2 * F_{n-2} = 0$ :

$F = (F_0, F_1, F_2, ...)\ 3 * x * F = (0, 3F_0, 3F_1, 3F_2, ....)\ 2 * x^2 * F = (0, 0, 2F_0, 2F_1, 2F_2, ....)$

Из первой строчки вычитаем вторую и прибавляем третью:

$F - 3 * x * F + 2 * x^2 * F = \ (F_0 - 0 + 0, F_1 - 3F_0 + 0, F_2 - 3F_1 + 2F_0, ...., F_{n} - 3 * F_{n-1} + 2 * F_{n-2}) = \ (F_0, F_1 - 3F_0, 0, 0, 0, ....) = F_0 + (F_1 - 3F_0)x = 10x$

Итого получаем (используя хорошие свойства сложения и умножения):

что, напомню еще раз, на самом деле

Это и есть уравнение, и его мы будем решать. Мы не можем взять так просто и поделить на

, хотя бы потому что мы не определяли операцию деления. Вместо этого мы будем умножать обе части уравнения на что-то такое, что как бы является

$(1 - 3x + 2x^2)^{-1}$ , и в конечном итоге оставим одинокую F слева.
На текущий момент из того что мы имееем мы не можем достоверно сказать существует ли вообще такое

$(1 - 3x + 2x^2)^{-1}$ (хотя так-то оно существует, и мы его сейчас сделаем).

Почему можно умножить обе части уравнения на что-то

Если у нас есть какие-то

$A$ и

$B$ , да и при том такие что

$A=B$ , то

Но из этого абсолютно не следует что если

, то

$A=B$ . К примеру, из того что

вовсе не следует что

$4 = 5$ .
Для того, чтобы было верно

нужно чтобы существовал такой элемент

$D$ , что

.
Тогда можно получить что

Немного преобразуем наше уравнение:

$F*(1 - 3x + 2x^2) = 10x \ Leftrightarrow \ F*(1-x)(1/2-x)*2 = 10x$

Это, опять же, не просто так, это потому что последовательность

умноженная на

и умноженная на

даёт в результате

Вот теперь уже чуть легче, теперь хорошо бы отыскать такие

$"(1-x)^{-1}"$ и

$"(1/2-x)^{-1}"$ , да и умножить на них наше уравнение.
Такие обратные последовательности есть, и вот их формула

$(alpha - x)*(1/alpha + x/alpha^2 + x^2/alpha^3 + .... + x^{n-1}/alpha^{n} + ...) = \ alpha * 1/alpha - x*1/alpha + alpha*x/alpha^2 + .... = 1$

Как это можно получить

Для начала попробуем на простом случае, с

Ясно что

, тут без вариантов. Теперь посмотрим что может получится у 1-й степени x:

(я просто покомпонентно перемножаю первую последовательность на вторую). Ясно что

. Так же далее получаем что

.
Для общего случая

действуем подобным образом.

Таким образом, умножаем обе части уравнения:

$F*(1-x)(1/2-x)*2 = 10x \ Leftrightarrow \ F*(1-x)(1/2-x)*2 * (1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) * \ (1/2) = 10x *(1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) * (1/2) \ Leftrightarrow \ F = 5x * (1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) \ Leftrightarrow \ F = 10x * (1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...)$

Посмотрим повнимательней на

$(1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...) = \ (1, 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2^{n}, ...)$

По определению произведения получаем формулу для n-ного члена:

$"(1, 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2^{n}, ...)"_{n} = \ "(1, 2, 4, ...., 2^{n}, ...) * (1, 1, 1, ...., 1, ....)"_{n} = \ sum_{i=0}^{i=n} A_i*B_{n-i} = \ sum_{i=0}^{i=n} 2^{i} = \ 1 + 2 + 4 + .... + 2^n = 2^{n+1} - 1$

Откуда появился последний шаг

Это обычная сумма членов конечной геометрической прогрессии. Можно по-быстрому получить вот так:
Пусть

. Тогда

$S_{n+1} = 1 + 2 + .... + 2^n + 2^{n+1} = S_n + 2^{n+1}$ .
В то же время,

$2 * S_n = 2 + 4 + 8 + ... + 2^{n+1} = 1 + 2 + 4 + 8 + ... + 2^{n+1} - 1 = S_{n+1} - 1$ следовательно

$S_{n+1} = 2*S_n - 1$
Итого приравнивая

$S_{n+1}$ получаем

$S_n + 2^{n+1} = 2*S_n - 1 implies S_n = 2^{n+1} - 1$ .

Подставляем полученное произведение

$F = 10x * (1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...) \ Leftrightarrow \ F = 10x * (1, 3, 7, ..., 2^{n+1} - 1, ...) \ Leftrightarrow \ F = (0, 10, 30, 70, ...., 10*(2^{n} - 1), ...)$

При умножении на

все члены умножились на 10 и сдвинулись на 1 вправо.
Итого получаем результат

$F_n = 10*(2^{n} - 1)$

Именно эту формулу нужно использовать для прохождения квеста, и именно её можно найти в подсказках в квесте.
К примеру на 32-й день получаем

$F_{32} = 10*(2^{32} - 1) = 42949672950$ .
Глядя на формулу можно сказать что хрякоплюхам долбогрызы не помеха — они даже будучи поедаемыми успевают экспоненциально размножаться.

Таким же образом можно вывести формулу для n-ного члена последовательности Фибоначчи, правда там числа будут пострашней — с корнями, и при этом при любом n формула даст натуральное число.

Немного размышлений о сложности алгоритма

Если реализовывать алгоритм расчета хрякоплюхов согласно рекуррентному определению (необязательно при этом использовать рекурсию), то сложность получается O(n).
А вот если по формуле — то тут можно и поспорить, будет ли это O(n) либо O(1). Зависит как мы считаем 2**n — это O(1) или O(n). С одной стороны, это битовый сдвиг, с другой стороны при n больших чем разрядность процессора потребуется больше времени на вычисления.
К примеру, если сделать Ethereum контракт, который будет считать этих хрякоплюхов, и посмотреть что получится по потреблению gas в зависимости от алгоритма:

Код на solidity

pragma solidity ^0.4.0;

contract Rangers {
    /*
    10 -> 1335 gas 
    20 -> 2385 gas
    30 -> 3435 gas
    40 -> 4485 gas
    50 -> 5535 gas
    60 -> 6585 gas
    70 -> 7635 gas
    80 -> 8685 gas
    90 -> 9735 gas
    100 -> 10785 gas
    */
    function byStepByStep(uint n) public pure returns (uint) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 10;
        }
        uint result = 10;
        uint prev1 = 10;
        uint prev2 = 0;
        for (uint i = 2; i <= n; i++) {
            result = 3*prev1 - 2*prev2;
            prev2 = prev1;
            prev1 = result;
        }
        return result;
    }
	
    /*
     10 -> 310 gas
     100 -> 310 gas
     200 -> 310 gas
    */
    function byFormula(uint n) public pure returns (uint) {
        return 10*(2 ** n - 1);
    }   
}

То вполне предсказуемо получится что по шагам будет O(n), а по формуле самый настоящий O(1).

Источник

Рекуррентные соотношения и уравнения

В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

Метод производящих функций
Метод характеристического уравнения

В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.

Метод производящих функций

Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$)
$$a_{0} = …, \ a_{1} = …, \ a_{k-1} = …, \ … \ a_{n} = …, ngeqslant k$$
Домножить каждую строчку на $z$ в соответствующей степени $z^{k} cdot a_{k}$ и сложить все выражения для $n ge 0$. В левой части получится сумма $displaystylesum_{n=0}^{infty} a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
Решить полученное уравнение относительно $G(z)$.
Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

Записать соответствующее однородное рекуррентное уравнение (РУ):
$$
p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + … + p_n a_n =f to \ to p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + … + p_n a_n =0.
$$
Выписать для него характеристическое уравнение и найти его корни $lambda_i$
$$
p_{n+k} lambda^{k} + p_{n+k-1}lambda^{k-1} + … + p_{n-1}lambda + p_n =0.
$$
Выписать согласно полученным корням $lambda_1, …,lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже).
$$
C_1 lambda_1^n +…+C_k lambda_k^n , mbox { для случая различных простых корней},
$$
$$
C_1 lambda_1^n + C_2 nlambda_1^n +…+C_m n^m lambda_1^n+…+C_k lambda_k^n mbox { для случая корня }, lambda_1 , { кратности }, m.
$$
Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $mu^n*P(n)$, $P(n)$ – многочлен от $n$).
Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
Подставить начальные условия $a_0, a_1, …, a_{k-1}$ и получить значения констант $C_1, …, C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи – это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , … $$

Числа Фибоначчи растут быстро: $f_{10}=55$, $f_{20}=6765$, а $f_{100}=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

$$begin{array}{rcl}
f_0&{}={}&0,\
f_1&{}={}&1,\
f_n&{}={}&f_{n-1}+f_{n-2}, quad ngeq2.\
end{array}
$$

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$begin{array}{rcl}
1cdot f_0 &= &0cdot 1,\
zcdot f_1 &= &1cdot z,\
zcdot f_n & = &(f_{n-1}+f_{n-2})cdot z^n, quad ngeq2.\
end{array}
$$

Складываем все строчки:

$$f_0 + f_1 z + sum_{n=2}^{infty}f_nz^n =
z + sum_{n=2}^{infty}f_{n-1}z^n+sum_{n=2}^{infty}f_{n-2}z^n.
$$

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

$$begin{array}{rcl}
G(z) &=& z + zsum_{n=2}^{infty}f_{n-1}z^{n-1}+z^2 sum_{n=2}^{infty}f_{n-2}z^{n-2},\
G(z) &=& z + zsum_{n=1}^{infty}f_{n}z^{n}+z^2 sum_{n=0}^{infty}f_{n}z^{n},\
G(z) &=& z + z(G(z)-f_0)+z^2 G(z),\
G(z) &=& z + zG(z)+z^2G(z),\
end{array}
$$

откуда выводим искомое выражение для производящей функции:

$$ G(z) = frac{z}{1-z-z^2}. $$

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

$$1-z-z^2 = 0,\
z_1=-frac{1-sqrt{5}}{2}, z_2=-frac{1+sqrt{5}}{2}.$$

Таким образом,

$$G(z) = frac{z}{1-z-z^2}=frac{-z}{(z_1-z)(z_2-z)}
= frac{z_1/(z_1-z_2)}{z_1-z} + frac{z_2/(z_2-z_1)}{z_2-z}.
$$

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

$$frac{1}{1-z} = sum_{n=0}^{infty}z^n = 1 + z + z^2 + z^3 + cdots.$$

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

$$ frac{z_1/(z_1-z_2)}{z_1-z} = frac{1}{z_1-z_2} frac{1}{1-frac{z}{z_1}} =
frac1{z_1-z_2}sum_{n=0}^{infty}frac{z^n}{z_1^n}.
$$

Аналогично (но с делением на $z_2$) действуем со второй дробью:

$$frac{z_2/(z_2-z_1)}{z_2-z} = frac{1}{z_2-z_1}frac{1}{1-frac{z}{z_2}} =
frac{1}{z_2-z_1}sum_{n=0}^{infty}frac{z^n}{z_2^n}.
$$

Таким образом,

$$G(z)=sum_{n=0}^{infty} f_nz^n =sum_{n=0}^{infty}biggl (frac{1}{z_1-z_2} frac{1}{z_1^n} + frac{1}{z_2-z_1}frac{1}{z_2^n} biggr)z^n,
$$

и, следовательно,

$$f_n = frac1{z_1-z_2}frac{1}{z_1^n} + frac1{z_2-z_1}frac{1}{z_2^n}.
$$

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, quad 1/z_2 = -z_1, quad z_1-z_2=sqrt{5} $$

$$f_n=frac{1}{sqrt{5}}left( biggl( frac{1+sqrt{5}}{2} biggr)^n – biggl( frac{1-sqrt{5}}{2} biggr)^n right).
$$

И окончательно,

$$ f_n = frac1{2^nsqrt{5}} bigl( (1+sqrt{5})^n – (1-sqrt{5})^n bigr). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_{n-1}+f_{n-2}$, и найдем его корни:

$$
x^2=x+1,\
D=1+4=5, \
x_{1,2}=frac{1pm sqrt{5}}{2}.
$$

Тогда общее решение однородного рекуррентного уравнения имеет вид:

$$
f_n=C_1 biggl(frac{1- sqrt{5}}{2} biggr)^n+C_2 biggl(frac{1+ sqrt{5}}{2} biggr)^n.
$$

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

$$
f_0=C_1 +C_2 =0,\
f_1=C_1 bigl(frac{1- sqrt{5}}{2} bigr)+C_2 bigl(frac{1+ sqrt{5}}{2} bigr)=1.
$$

Решая систему, найдем

$$
C_1 =-1/sqrt{5},\
C_2 = 1/sqrt{5}.
$$

Итоговое выражение для последовательности чисел Фибоначчи:

$$
f_n= -frac{1}{sqrt{5}} bigl(frac{1- sqrt{5}}{2} bigr)^n +frac{1}{sqrt{5}} bigl(frac{1+ sqrt{5}}{2} bigr)^n = \
=frac1{2^nsqrt{5}} bigl( (1+sqrt{5})^n – (1-sqrt{5})^n bigr).
$$

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Понравилось? Добавьте в закладки

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$
с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность ${a_n}$, удовлетворяющую рекуррентному соотношению $a_{n+2} + 4 a_{n+1} + 3 a_{n} = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Решим ваши задачи быстро и подробно!

Полезные ссылки

Рекуррентные последовательности, ЛОРУ, ЛНРУ Краткое изложений лекций по ДМ для 1 курса МГУ
Решение рекуррентных соотношений Краткая теория и примеры, метод производящих функций
Разностное уравнение и рекуррентная последовательность Более продвинутый материал
Примеры: примитивно-рекурсивные функции
Примеры: разностные уравнения

Источник

Использование рекуррентной формулы для вычисления суммы ряда

Рекуррентной
называется всякая формула, выражающая
каждый член последовательности через
предыдущие члены этой последовательности.
Используется чаще всего в целях избавления
от больших чисел при вычислении суммы
членов последовательности.

Как
правило, в этом случае рекуррентная
формула имеет вид:
,
откуда, зная общий член последовательности,
можно будет найти коэффициент c,
на который нужно умножать каждый
предыдущий член последовательности,
чтобы найти следующий:

Пример. Вычислить
.

Найдем коэффициент
c, разделив

Таким
образом, очередной член ряда можно
вычислить по рекуррентной формуле:

Пример 3. Найти количество членов
бесконечного ряда

, сумма которых дает приближенное
значение sin(x)
с точностью ε=10^-4.

Private
Sub
Command1_Click()

Const
Pi = 3.14159265358979

Eps
= Val(Text4.Text) ‘Точность

x
= Val(Text1.Text) ‘Аргумент
x

x
= x
/ 180 * Pi
‘Перевод
в радианную меру

f
= Sin(x)
‘Вычисление
точного значения функции

s
= 0 ‘Инициализация
переменной s

a
= x
‘Первый
член ряда

k
= 1

‘Вывод
значения Sin(x)
по формату

Text2.Text
= Format(f, “0.000E+”)

Do
While
Abs(f
– s)
> e
‘Цикл
выполняется пока условие

a
= -a * x ^ 2 / (2 * k) / (2 * k + 1)

s
= s + a:

k
= k + 1

Loop

Text3.Text
= Format(s, “0.000E+”)

Text5.Text
= Str(k)

End
Sub

Замечание.
Иногда возникает необходимость переделать
цикл типа For…Next
на цикл Do…Loop
(наоборот не всегда получается).

For…Next

Do…Loop

с
предусловием

Do…Loop

с постусловием

For
i = 1 to
n

Тело
цикла

Next
i

i
= 1

Do
While
i <= n

Tело
цикла

i=i+1

Loop

i=1

Тело
цикла

i=i+1

Loop
Until
i > n

Использование функции Timer

Условие
продолжения или завершения цикла не
всегда связано только с внутренними
причинами, – изменяющимися от шага к
шагу значениями каких-либо переменных.
Часто, например, цикл завершается после
того, как исчерпывается отпущенное на
его выполнение время. Чтобы реализовать
такое условие, следует воспользоваться
системной функцией Timer.
Она возвращает текущее время с точностью
до 0,01 сек.

Пример
4. Вычислить сумму бесконечного ряда
с использованием функции Timer

Private
Sub
Command1_Click()

Dim
x,y,a As
Single

Eps
= Val(Text1.Text)

T=Timer
‘Зафиксировали
время начала работы программы

s
= 0: n = 1

a
= n/(n^2+1)

s=s+a:
n=n+1

If
Timer-T>10
Then
Exit
Do
‘Если
разница между текущим ‘временем
и временем начала работы больше 10
сек, то выход из цикла

Loop
Until
a<0.0001

End
Sub

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Рекуррентные соотношения и уравнения