a_popov

Материал из вики

Числа Фибоначчи — элементы числовой последовательности в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени итальянского математика средневековой Европы Леонардо Пизанский (прозвище Фибоначчи, что обозначает «хороший сын родился»).

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:

В «нулевом» месяце имеется пара кроликов (1 новая пара).
В первом месяце первая пара производит на свет другую пару (1 новая пара).
Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).
В третьем месяце вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (3 новые пары).

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

Пусть популяция за месяц n будет равна F(n). В это время только те кролики, которые жили в месяце n-2, являются способными к размножению и производят потомков, тогда F(n-2) пар прибавится к текущей популяции F(n-1). Таким образом общее количество пар будет равно F(n) = F(n-1) + F(n-2).