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

РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Говорят, что элементы u₁, u₂,..., u_n, образуют рекуррентную последовательность k - го порядка, если заданы первые k членов последовательности u₁, u₂,..., u_k, а для n > k

u_n = F (u_n-1, u_n-2,..., u_n-k ),

где F некоторая функция k аргументов.

1. Т.е. значение n -го элемента может быть вычислено по k предыдущим элементам. Предыдущие значения функции запоминаются в буфере t (см. рисунок ниже).

3. Известным примером рекуррентной последовательности второго порядка является последовательность чисел Фибоначчи:

u₁ = u₂ = 1

u_n = u_n-1 + u_n-2, для n > 2, k=2.

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

1. Сдвиг буфера t влево.

2. Вычисление нового элемента t_k+1.

3. Запись его по индексу k+1.

4. Вычисления с t_k+1 и переход к п.1.

Дата добавления: 2014-01-11