Главная » Free Pascal » Числа Фибоначчи Free Pascal

0

Более поздний рекурсивный алгоритм связывают с именем итальянского мате- матика Фибоначчи (XII—XIII вв.). Он занимался оценкой потомства кроликов при следующих предположениях: все начинается с разнополой пары, ежегодно прино- сящей приплод в виде новой пары — самца и самки. Дети начинают пополнять по- пуляцию по такой же схеме через два года после своего рождения. Считая, что смертность отсутствует, получаем:

± в начале эксперимента 1 пара (родители);

± через 1 год 2 пары (родители и дети 1-го поколения);

± через 2 года 3 пары (родители; дети 1-го поколения; дети 2-го поколения);

± через 3 года 5 пар (родители; дети 1-го, 2-го и 3-го поколений; потомки де- тей 1-го поколения).

Фибоначчи  вывел  формулу  для  количества  пар:  1,  1,  1 + 1 = 2,  1 + 2 = 3, 2 + 3 = 5, … В общем виде очередное число Фибоначчи образуется как сумма двух предыдущих:

Fn = Fn-2 + Fn-1 .

Кроме курьезной задачи о потомстве виртуальных кроликов, числа Фибоначчи используются в задачах поиска экстремума функций.

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

   Листинг 9 .1 1 .  Функ ция  вычисления  числа  Фибоначчи                                                              

function Fib(n:integer):longint; begin

if n<3 then Fib:=1

else Fib:=Fib(n-1)+Fib(n-2); end;

Эта функция каждый раз при входе в нее дважды обращается сама к себе. И на ее примере можно оценить степень неэффективности алгоритма. В табл. 9.2 первая строка указывает число сложений, затрачиваемых для данного n по обычной схеме вычислений, а вторая строка — число сложений по рекуррентной схеме.

Таблица 9.2

n

0

1

2

3

4

5

6

7

8

9

10

Обычные сложения

0

0

1

2

3

4

5

6

7

8

9

Сложения с рекурсией

0

0

1

2

4

7

12

20

33

54

88

Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)

По теме:

  • Комментарии