Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Пример: Числа Фибоначчи


 

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

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

Для решения этой задачи достаточно хранить в памяти элемент последовательности. Решение задачи разбивается на два основных этапа: начальную установку и продвижение по последовательности.

Для вычисления чисел Фибоначчи первый этап выглядит следующим образом:
a:=1; b:=1
Продвижение по последовательности на один элемент вперед выполняется так:

for k:=3 до n do
begin
c:=a+b;
a:=b;
b:=c;
end;

Каждый из элементов последовательности, начиная с третьего в данном случае, как бы отбирает значение у следующего элемента. Последний элемент, после того как у него отобрали значение, получает новое путем применения рекуррентной формулы. Безвозвратно теряемые старые значения уже не нужны, поскольку на последующие вычисления они повлиять не могут.
Составим алгоритм нахождения n-го числа Фибоначчи с начала до конца:

program fibonacciITER;

var

n, f, a, b, c, k: integer;

begin

writeln (‘Введите число n');

readln ( n );

a:=1; b:=1;

for k:=3 to n do

begin

c:=a+b;

a:=b;

b:=c

end;

f:=c;

writeln (n, '-й член последовательности Фибоначчи равен ', f);
end.

 

В следующей программе числа Фибоначчи вычисляются вначале с использованием итерации, а затем с использованием рекурсии, причем глубина рекурсии отображается. Перед каждым рекурсивным вызовом команда delay(900) приостанавливает вывод глубины рекурсии на 0.9 с.

 

program fibonacci;

uses crt;

var n,result:integer;

function fibit(n:integer):integer;

var a,b,c,i:integer;

begin

a := 1; b := 1;

if (n=1) or (n=2)

then fibit :=1

else begin

for i:= 3 to n do

begin c :=a+b; a := b; b :=c; write (c,' '); end;

fibit :=c;

writeln;

end;

end;

function fibrek(n:integer):integer;

begin

if (n=1) or (n=2) then fibrek := 1

else

begin

writeln ('Глубина рекурсии:',n);

delay(900) ;

fibrek := fibrek(n-1)+fibrek(n-2);

end;

end;

<== предыдущая лекция | следующая лекция ==>
Рекурсия не всегда может быть заменена итерацией | Пример обработки рекуррентной последовательности

Дата добавления: 2014-01-03; Просмотров: 212; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.