Итерационные и рекуррентные последовательности

Знакомый нам способ определения последовательности – формула общего члена последовательности.

Пример: последовательность четных чисел

f(n)=2n

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

Итерационным (рекуррентным) определением последовательности называется определение зависимости очередного члена от предыдущего (или в общем случае рекуррентной последовательности – от нескольких предыдущих).

Итерация – повторение. Рекуррентность – возвратность, зависимость от предыдущего.

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

f(0)=0 f(n+1)=f(n)+2

f(0)=0 f(n+1)=f(n)+a_n+1

f(0)=1 f(n+1)=f(n)• a_n+1

f(n)=max(a₁, …, a_n)

f(1)=a₁ f(n+1)=max(f(n),a_n+1)

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

Трасса цикла – есть рекуррентно задаваемая последовательность (состояний).

Найти n-ые члены определенных выше последовательностей

1.

2.

3. f(n)=max(a₁, …, a_n)

в предположении доступности обычных арифметических операций (функций двух аргументов) и сравнений.

Сам оператор цикла задает лишь итерационную зависимость текущего состояния всех переменных от их предыдущего состояния. Начальное состояние (значение 1-го члена итерации) задается независимо перед выполнением цикла – инициализация цикла.

Обратите внимание на последний пример. Сначала мы, как и в предыдущих примерах, определяем наибольшее среди n чисел в терминах максимума двух чисел (итерационное определение). Но последняя функция не допустима – ее собственной определение является подзадачей (условное определение). Здесь мы подходим к важной методике построения программ - программированию «сверху вниз».

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