Рекуррентная зависимость.

Рекуррентная зависимость – зависимость, в которой любой элемент можно найти по любым k предыдущим элементам этой последовательности, где:

k- глубина (порядок) рекуррентны.

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

a_n = f (a_n-1, a_n-2 , …, a_n-k)

- Если заданы первые k элементов последовательности – решение одно

- Если задана только последовательность – решений бесконечное множество

Примерами рекуррентных последовательностей являются арифметическая (1) и геометрическая (2) прогрессии:

a₁=1, a₂=3, a₃=5, a₄=7, a₅=9, … (1)

a₁=1, a₂=2, a₃=4, a₄=8, a₅=16, … (2)

Рекуррентные формулы для указанных арифметической и геометрической прогрессий

a_i = a_i-1 +2

a_i = 2*a_i-1

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

Для арифметической прогрессии:

Для геометрической прогрессии:

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

K=1

Особенности цикла при рекуррентной зависимости:

1) Результат, полученный на очередном шаге, является начальным для следующего шага.

2) Для получения n-го элемента последовательности не требуется n ячеек памяти. Для получения любого элемента последовательности потребуется k+1 ячеек памяти, где k – глубина рекурренты.

За счет этого идет выигрыш по времени и памяти.

Пример: найти 100-ый элемент последовательности Фибоначчи

a_n+1 = a_n-1 + a_n, где а₀ и а₁ = 1

Пример – рассчитать с помощью рекуррентной формулы гиперболический синус

Для этого построим итерационный цикл «Пока» и воспользуемся рекуррентной зависимостью

- такая рекуррентная зависимость позволит уменьшить время вычисления.

Считаем что Е – const, задает точность вычисления

Использование итерационного цикла иногда не даёт результат, например, если ряд не сходится.

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

Дата добавления: 2015-11-30