два. кролика или одного

    m[i] = m[i-1] + m[i-2];

  for (i = 2; i <= n; i++)

  memset(m,0,sizeof(m));

   В случае необходимости запоминания всех чисел Фибоначчи f(1), f(2), …, f(n), заведем массив m, в котором положим m[i] = f(i), 0 £ i £ n. Реализация может быть как циклическая, так и рекурсивная с запоминанием:

   Максимальным числом Фибоначчи, которое помещается в тип int, является F46 = 1836311903. В 64-битовый целочисленный тип long long (__int64) помещается максимум F92. Если в задаче требуется находить значения f(n) для n > 92, то следует воспользоваться длинной арифметикой.

    temp = a, a = b, b = temp + a;

  for (i = 0; i < n; i++)

  int i, temp, a = 0, b = 1;

   Рассмотрим несколько функций f(n) вычисления n - го числа Фибоначчи. Для нахождения f(n) с линейной сложностью без запоминания значений f(1), f(2), …, f(n – 1) можно использовать циклический вариант:

которая называется последовательностью Фибоначчи.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... ,

   Положим F0 = 0, при этом соотношение при n = 2 останется истинным. Таким образом образовалась последовательность

Fn =  Fn-1 + Fn-2, F1 = F2 = 1

  Если через Fn обозначить количество кроликов после n - го месяца, то имеет место следующее рекуррентное соотношение:

   Количество кроликов в n - ый месяц будет равно количеству кроликов, которое было в (n – 1) - ом месяце, плюс количество родившихся. Последних будет столько, сколько кроликов дают потомство (которым уже исполнилось 2 месяца). Их число равно количеству кроликов в (n – 2) - ой месяц.

   Очевидно, что в начале первого и второго месяца у фермера один кролик, поскольку потомства еще нет. На третий месяц будет два кролика. На четвертый месяц первый кролик даст еще одного, а второй потомства не даст, так как ему еще один месяц. Таким образом, на четвертый месяц будет три кролика.

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

   В XIII веке итальянский математик Леонардо Фибоначчи исследовал решение следующей задачи:

← Числа Фибоначчи

Числа Фибоначчи - E-Olimp система подготовки и проведения олимпиад по спортивному программированию