Лекции по TURBO PASCAL

Последовательность Фибоначчи

Последняя последовательность из самостоятельного задания называется последовательностью Фибоначчи. Эта последовательность начинается с двух единиц и каждый последующей её элемент равен сумме двух предыдущих. Поэтому следующий её элемент будет 8+13=21.

Найдем ещё несколько элементов этой последовательности:

1 1 2 3 5 8 13 21 34 55 89 144 233

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

a₁ = 1

a₂ = 1

a_i = a_i-2 + a_i-1 , где i > 2.

По этой схеме можно найти любой элемент последовательности Фибоначчи, если известны значения предыдущих элементов, например:

a₅ = a₄ + a₃ = 2 + 3 = 5

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

Программа будет такой:

Program Fibonacci;

Var a : array [1..10] of integer;

i : integer;

Begin

a[1] := 1; { Первые два элемента заданы сразу }

a[2] := 1;

For i := 3 to 10 do {Ищем с 3 эл-та, так как первые два уже найдены}

a[i] := a[i-2] + a[i-1];

writeln (’Последовательность Фибоначчи: ’);

For i := 1 to 10 do { Печатаем на экран }

writeln (a[i]);

end.

Итак, уже, думаю, у вас сформировалось вполне конкретное определение рекуррентной последовательности:

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

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

Содержание