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

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

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

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

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

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

F_n =  F_n-1 + F_n-2, F₁ = F₂ = 1

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

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

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

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

int f(int n)

{

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

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

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

  return a;

}

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

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

   При вычислении чисел Фибоначчи F_n для больших аргументов (n > 92) следует воспользоваться длинной арифметикой.

   Формула Бине выражает в явном виде значение F_n как функцию от n:

где  – золотое сечение. При этом φ и  (-φ)^-1 = 1 – φ являются корнями квадратного уравнения x² – x – 1 = 0.

Следствие. При больших значениях n имеет место равенство: . Следствие имеет место, так как с ростом n значение  стремится к нулю.

   Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть

НОД(F_n, F_m) = F_НОД(n,m)

   Следствие 1. F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n = 2). 

   Следствие 2. F_n может быть простым только для простых n (за исключением n = 4).

   1. Свойства чисел Фибоначчи. Доказать следующие свойства: 

   а) F₀ + F₁ + F₂ + F₃ + … +  F_n = F_n+2 – 1;

   б) F₁ + F₃ + F₅ + … +  F_2n-1 = F_2n;

   в) F₀ - F₁ + F₂ - F₃ + … - F_2n-1 +  F_2n = F_2n-1 – 1;

   г) F₀² + F₁² + F₂² + F₃² + … +  F_n² = F_n * F_n+1;

   д) F_n+1F_n-1 – F_n² = (-1)ⁿ (Равенство Ж. Д. Кассини);

   е) F_n+m = F_mF_n+1 + F_m-1 F_n;

   2. Лестница. Необходимо пройти по лестнице, состоящей из n ступенек. Из очередной ступеньки можно перейти или на следующую ступеньку, или перешагнуть через одну. Сколько существует вариантов прохождения лестницы?

   3. Кирпичная стена [Вальядолид, 900]. Высота кирпича равна 2, ширина – 1. Необходимо построить стену высоты 2 и длиной n. Сколькими способами можно это сделать в зависимости от значения n?

   4. Путь пчелы. Пчела начинает свой путь с клетки 1 или 2 и направляется в клетку с номером n. Двигаться пчеле можно только по соседним клеткам от меньшего номера к большему. Сколькими разными путями пчела может попасть в клетку с номером n?

   5. Новости по телефону.n друзей проживают в разных городах и разговаривают между собой только по телефону. Один телефонный звонок всегда длится одну минуту. Один из друзей желает поделиться новостью со всеми друзьями за наименьшее время. Найти наименьшее время, за которое все друзья будут знать новость, если каждый может совершить не более 2 звонков.

   6. AVL – деревья. Бинарное дерево называется AVL – деревом, если оно имеет следующие свойства:

• высоты поддеревьев каждой вершины отличаются не более чем на единицу;
• каждое поддерево для каждой вершины является AVL – деревом.

   Вычислить количество листьев в AVL – дереве высоты n.

   7. Резисторы. n одинаковых резисторов, с сопротивлением 1 Ом каждый, соединили как показано на рисунке (к первому резистору подсоединены резисторы с четными номерами последовательно, а с нечетными – параллельно). Найти сопротивление всей системы из n резисторов.

  8. Замораживание Фибоначчи [Вальядолид, 495]. Последовательность чисел Фибоначчи (0, 1, 1, 2, 3, 5, 8, 13, 21, ....) определяется рекуррентным соотношением:

f₀ = 0, f₁ = 1,

f_i = f_i-1 + f_i-2, i ≥ 2

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

   Вход. Каждая строка содержит целое неотрицательное число n (n £ 5000).

   Выход. Для каждого входного n вывести n - ое число Фибоначчи в соответствии с ниже приведенным форматом.

9. Луч сквозь стекло  [Вальядолид, 10334]. Две пластины стекла совместили друг с другом. 
Сколькими способами an луч света может пройти сквозь пластины, если по пути он изменит направление n раз?

   Вход.Каждая строка содержит одно число n (0 ≤ n ≤ 1000).

   Выход. Для каждого теста вывести в отдельной строке значение a_n.

   10. Шум мирового кубка  [Вальядолид, 10450]. По заданному числу n вычислить количество последовательностей из 0 и 1 длины n, в которых две единицы не стоят рядом.

   Вход. Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит число n (0 < n < 51).

   Выход. Для каждого теста вывести его номер и количество последовательностей из 0 и 1 длины n, в которых две единицы не стоят рядом.

11. Числа Фибоначчи  [Вальядолид, 10579]. Числа Фибоначчи задаются рекуррентным соотношением:

f(1) = 1, f(2) = 1, f(n) = f(n – 1) + f(n – 2)

   Вход. Каждая строка содержит целое неотрицательное n.

   Выход. Для каждого входного n вывести n - ое число Фибоначчи (значение f(n)). Известно, что f(n) содержит не более 1000 знаков.

   12. Пчела [Вальядолид, 11000]. В Африке живет специальный вид пчел. Каждый год самка производит на свет одного самца, а самец – самца и самку, после чего родители погибают. Ученые изобрели магическую самку пчелу, которая плодится как обыкновенная самка, но при этом является бессмертной. Необходимо вычислить число самцов и общее количество пчел в семействе, если изначально была лишь одна магическая самка пчела.

   Вход. Каждая строка содержит целое N (N ³ 0).Последний тест содержит N = -1 и не обрабатывается.

   Выход. Для каждого значения N вывести число самцов и общее количество пчел в семействе через N лет. Выводимые числа не более 2³².

   13. Флаги [Тимус 1225]. Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?

   Вход. Число полос n (1 ≤ n ≤ 45) на флаге.

   Выход. Количество способов, которыми можно покрасить флаг из n полос.

   14. Определитель. Вычислить определитель порядка n ´ n, где на главной диагонали и под ней стоят единицы, а над главной диагональю стоят минус единицы:

   15. Бесконечная сумма. Вычислить бесконечную сумму:

0.1 + 0.01 + 0.002 + 0.0003 + 0.00005 + 0.000008 + 0.0000013 + ...

 УКАЗАНИЯ И РЕШЕНИЯ

   1. Свойства чисел Фибоначчи. Доказательство всех равенств проводим по индукции.

а) База. n = 0. F₀ = F₂ – 1, что верно.

    Шаг. F₁ + F₂ + F₃ + … +  F_n =  (F₁ + F₂ + F₃ + … +  F_n-1) + F_n = F_n+1 – 1 + F_n = F_n+2 – 1.

б) База. n = 1. F₁ = F₂, что верно.

    Шаг. F₁ + F₃ + F₅ + … +  F_2n+1 = (F₁ + F₃ + F₅ + … +  F_2n-1) + F_2n+1 =  F_2n + F_2n+1 = F_2n+2.

в) База. n = 1. F₀ – F₁ + F₂ = 0 – 1 + 1 = 0, F₁ – 1  = 1 – 1 = 0.

    Шаг. (F₀ – F₁ + F₂ – F₃ + … – F_2n-1 +  F_2n) – F_2n+1 +  F_2n+2 =

F_2n-1 – 1 – F_2n+1 +  F_2n+2 = F_2n-1 - 1 – F_2n+1 +  F_2n + F_2n+1 = F_2n-1 +  F_2n – 1 = F_2n+1 – 1.

г) База. n = 0. F₀² = F₀ * F₁, что верно.

    Шаг. F₀²+F₁²+ …+ F_n+1² =  (F₀²+F₁²+ …+ F_n²)+ F_n+1²= F_n*F_n+1+F_n+1² = F_n+1*(F_n + F_n+1) = F_n+1*F_n+2.

д) Равенство получается из матричного тождества  после вычисления определителей.

е) Индукция по m. База. m = 1. F_n+1 = F₁F_n+1 + F₀F_n =   1 * F_n+1 + 0 * F_n = F_n+1, что верно.

    Шаг. F_n+m+1 = F_n+m +  F_n+m-1 = F_mF_n+1 + F_m-1F_n + F_m-1 F_n+1 + F_m-2F_n =

 (F_m + F_m-1) F_n+1 + (F_m-1 + F_m-2) F_n = F_m+1 F_n+1 + F_mF_n.

   2. Лестница. Пусть f(n) – количество вариантов, которыми можно пройти по n ступенькам. С n - ой ступеньки можно перейти или на (n – 1) - ую, или на (n – 2) - ую. Количество вариантов пройти n ступенек равно количеству вариантов пройти n – 1 ступенек плюс количество вариантов пройти n – 2 ступеньки, то есть f(n) = f(n – 1) + f(n – 2). Очевидно, что f(1) = 1 и f(2) = 2. Таким образом f(n) является (n + 1)- ым числом Фибоначчи.

   3. Кирпичная стена [Вальядолид, 900]. Обозначим через f(n) количество способов, которыми можно построить кирпичную стену высоты 2 и длины n. Тогда можно положить один кирпич вертикально и далее строить стену длины n – 1 f(n – 1) способом, или положить два кирпича горизонтально и строить стену длины n – 2 f(n – 2) способами. То есть f(n) = f(n – 1) + f(n – 2). Также имеем: f(1) = 1 (один вертикальный кирпич), f(2) = 2 (два вертикальных или два горизонтальных кирпича). То есть f(n) является (n + 1) - ым числом Фибоначчи.

   4. Путь пчелы.  Из клетки с номером n пчела может попасть или в клетку с номером n + 1, или с номером n + 2. Задача сводится к движению по ступенькам лестницы. Количество разных путей до клетки с номером n равно F_n.

   5. Новости по телефону.  Звонки между друзьями следует организовать как показано на рисунке. Тогда на i - ой минуте о новости узнают еще F_i друзей. Наименьшее число минут, за которое новость распространится среди всех друзей, равно такому наименьшему значению k, для которого F₁ + F₂ + … + F_k ³ n (или то же самое что F_k+2 – 1 ³ n), где F₁ = 1 (личность, которая распространяет новость) и F₂ = 1 (друг, которому сделан первый звонок).

                  личность, распространяющая новость

                                    /------------^----\

      первая минута           A                     \   

                                /----^----\                \  

      вторая минута       C           \               B

                             /--^--\          \           /--^--\ 

      третья минута    D       \         E        F           \     

                         /--^-\       \     /--^--\   /--^--\     \

                     ...   ...    ... ...    ... ...    ...   ...

 6. AVL – деревья. Обозначим через f(n) число листьев в AVL – дереве высоты n. Тогда f(0) = 1, f(1) = 1, f(2) = 2.

   Если AVL – дерево имеет высоту n, то его левое поддерево (например, для определенности) имеет высоту n – 1, а правое n – 2. Количество листьев тогда равно

f(n) = f(n – 1) + f(n – 2),

   то есть числам Фибоначчи.

   7. Резисторы. Обозначим через f(n) сопротивление системы из n резисторов. Очевидно, что f(1) = 1, f(2) = 2. Докажем по индукции, что

при четном n  и  при нечетном n.

   Если система состоит из четного количества резисторов, то следующий резистор соединяется параллельно и результирующее сопротивление равно

   В случае нечетного количество резисторов соединение со следующим резистором происходит последовательно и результирующее сопротивление равно

   8. Замораживание Фибоначчи [Вальядолид, 495]. Поскольку n ≤ 5000, то для нахождения f_n следует воспользоваться классом BigInteger. Найдем и запомним в массиве m все значения f_n (0 ≤ n ≤ 5000) и для каждого входного n будем выводить m[n] = f_n.

Реализация. Вычислим все значения f_n (0 ≤ i ≤ 5000) и занесем их в массив m[5001]. Поскольку f₅₀₀₀ содержит не более 1100 десятичных знаков, то установим MAXLENGTH = 1100.

#include< stdio.h >

#include< memory.h >

#define MAXLENGTH 1100

class BigInteger{ . . .};

BigInteger m[5001];

void main(void)

{

  int i, n;

   Положим m[1] = 1 и воспользуемся рекуррентной формулой m[i] = m[i -1] + m[i - 2].

  m[1] = BigInteger(1);

  for (i = 2; i < 5001; i++) m[i] = m[i-1] + m[i-2];

Для каждого входного значения n выводим f_n = m[n] в соответствии с требуемым форматом.

  while(scanf("%d",&n) == 1)

  printf("The Fibonacci number for %d is ",n),m[n].print();

}

   9. Луч сквозь стекло  [Вальядолид, 10334]. При наложении двух стеклянных пластин образуется одна внутренняя сторона и две внешние, относительно которых может отражаться луч света. Каждый проход луча с n отражениями будем кодировать последовательностью нулей и единиц длины n: если отражение осуществляется относительно внутренней стороны, то ставим 1, если относительно внешней – то 0. Например, показанному ниже движению луча с 4 отражениями соответствует последовательность 1, 0, 0, 0.

   Можно заметить, что две единицы в такой последовательности никогда не будут стоять вместе, потому что два последовательных отражения относительно внутренней стороны никогда не могут иметь место. Таким образом, количество возможных проходов луча с n отражениями равно количеству последовательностей из 0 и 1 длины n, в которых две единицы не стоят вместе. Количество таких последовательностей равно числам Фибоначчи (задача 10450). Числа Фибоначчи имеют вид: f₀ = 0, f₁ = 1, f₂ = 1, f_i = f_i-1 + f_i-2. Число способов a_n прохода луча света сквозь пластины равно f_n+2.

   Поскольку n ≤ 1000, то следует воспользоваться классом BigInteger.

   Пример. Варианты прохождения луча сквозь пластины для n = 0, 1, 2 показаны выше на рисунке. При этом a₀ = f₂ = 1, a₁ = f₃ = 2, a₂ = f₄ = 3.

   Реализация. Вычислим все значения a_i (0 £ i £ 1000), занесем их в массив m[1001]. Поскольку a₁₀₀₀ = f₁₀₀₂ содержит не более 210 десятичных знаков, то установим MAXLENGTH = 210.

#include< stdio.h >

#include< memory.h >

#define MAXLENGTH 210

class BigInteger{ . . .};

BigInteger m[1001];

void main(void)

{

  int i,n;

   Вычислим все значения m[i] = a_i, 0 £ i £ 1000. Положим m[0] = 1, m[1] = 2, а далее воспользуемся рекуррентной формулой m[i] = m[i -1] + m[i - 2].

  m[0] = BigInteger(1); m[1] = BigInteger(2);

  for (i = 2; i < 1001; i++) m[i] = m[i-1] + m[i-2];

   Читаем входное значение n и выводим m[n].

  while (scanf("%d",&n) == 1) m[n].print();

}

   10. Шум мирового кубка  [Вальядолид, 10450]. Обозначим через f(n) количество искомых последовательностей из 0 и 1 длины n. Если на первом месте последовательности будет находиться 0, то начиная со второго места можно построить f(n – 1) последовательностей. Если на первом месте стоит 1, то на втором месте обязательно должен стоять 0, а на последующих n - 2 свободных местах можно построить f(n – 2) последовательностей.

   При этом f(1) = 2 (имеем две последовательности длины 2: 0 и 1), f(2) = 3 (последовательности 00, 01, 10). Значения f(n) образуют числа Фибоначчи . Известно, что f₀ = 0, f₁ = 1, f₂ = 1, f_i = f_i-1 + f_i-2. Учитывая начальные условия, получим: f(n) = f_n+2.

   Пример. Рассмотрим второй тест. Всего существует 5 последовательностей из 0 и 1 длины 3, в которых две единицы не стоят рядом: 000, 001, 010, 100, 101.

   Реализация. В массиве fib вычислим значения f(n): f(n) = fib[n]. Для n > 44 значения f(n) будут выходить за границы типа int, поэтому воспользуемся 64 - битовым целочисленным типом long long (__int64).

#include< stdio.h >

int tests, i, n;

long long fib[51];

void main(void)

{

   Нахождение значений f(n) совершим в цикле:

  fib[1] = 2; fib[2] = 3;

  for(i = 3; i < 51; i++) fib[i] = fib[i-1] + fib[i-2];

Читаем количество тестов и для каждого входного n выводим значение fib[n].

  scanf("%d",&tests);

  for (i = 1; i <= tests; i++)

  {

    scanf("%d",&n);

    printf("Scenario #%d:\n",i);

    printf("%lld\n\n",fib[n]);

  }

}

   11. Числа Фибоначчи  [Вальядолид, 10579]. Воспользуемся классом BigInteger. Для каждого входного n вычислим значение f(n), используя приведенную в условии рекуррентную формулу.

Реализация. Воспользуемся классом BigInteger. Положим длину чисел MAXLENGTH равной 1001.

#include< cstdio >

#include< memory >

#include< string >

#define MAXLENGTH 1001

using namespace std;

class BigInteger{ . . .};

void main(void)

{

   Читаем входное значение n. Изначально положим a = f(0) = 0, b = f(1) = 1. Во вложенном цикле while после выполнения i - ой итерации имеют место соотношения: a = f(i), b = f(i + 1). Выполнив цикл n раз, выводим a = f(n).

  BigInteger a(0), b(1), temp(0);

  int n;

  while (scanf("%d",&n) == 1)

  {

    a = BigInteger(0); b = BigInteger(1);

    while (n--) temp = a, a = b, b = temp + a;

    a.print();

  }

}

   12. Пчела [Вальядолид, 11000]. Обозначим n - ое число Фибоначчи через f(n). Тогда через n лет число самцов в пчелином семействе будет равно f(n) – 1, а общее число пчел f(n + 1) – 1. Через n = 0 лет семейство состоит из единственной пчелы самки, то есть имеется 0 самцов и 1 пчела. Положим f(0) = 1, f(1) = 2. Далее по индукции докажем справедливость приведенного утверждения. После n + 1 года число самцов равно суммарному числу самок и самцов после n - го года, то есть f(n + 1) – 1. Число самок после n + 1 года равно числу самцов после n - го года плюс одна бессмертная самка, то есть f(n) – 1 + 1 = f(n). Таким образом общее число пчел после n + 1 года равно f(n + 1) – 1 + f(n) = f(n + 2) – 1.

   Реализация. Искомые числа Фибоначчи не превосходят 2³². Вычислим их первые 50 значений и занесем в массив f типа long long.

#include< stdio.h >

long long f[50];

void main(void)

{

  int i, n;

   Заполним массив f числами Фибоначчи.

  f[0] = 1; f[1] = 2;

  for(i = 2; i < 50; i++) f[i] = f[i-1] + f[i-2];

Для каждого входного n выведем результат.

  while (scanf("%d",&n),n >= 0)

    printf("%lld %lld\n",f[n]-1,f[n+1]-1);

}

   13. Флаги [Тимус 1225]. Обозначим через f_red(n) и f_white(n) количество способов раскраски флага из n полос при условии, что первой полосой будет соответственно красная или белая. Тогда

f_red(n) = f_white(n – 1) + f_white(n – 2), f_red(1) = 1, f_red(2) = 1;

f_white(n) = f_red(n – 1) + f_red(n – 2), f_white(1) = 1, f_white(2) = 1.

Если f(n) – искомое общее количество способов раскраски, то

f(n) = f_red(n) + f_white(n)

Поскольку f_red(1) = f_white(1) = 1, f_red(2) = f_white(2) = 1, а f_red(n) и f_white(n) одинаковыми формулами выражаются друг через друга, то f_red(n) = f_white(n) = f_n, где f_n – n-ое число Фибоначчи. Таким образом f(n) = 2 * f_n.

   Реализация. В массиве fib вычислим значения f_red(n): f_red(n) = fib[n]. Для n > 44 значения f_red(n) будут выходить за границы типа int, поэтому воспользуемся 64 - битовым целочисленным типом __int64.

__int64 fib[46];

Читаем входное значение n. Нахождение значения fib[n] совершим в цикле:

scanf("%d",&n);

fib[1] = 1; fib[2] = 1;

for (i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];

   Выводим результат f(n) = 2* f_red(n) = 2 * fib[n]:

printf("%I64d\n",2*fib[n]);

   14. Определитель. Обозначим через f(n) значение определителя. Тогда  f(1) = 1, f(2) = 2. Раскрывая определитель по первой строке, получим:

f(n) = f(n – 1) + f(n – 2)

   Откуда f(n) = F_n+1.

15. Бесконечная сумма. Положим x = 1/10 в производящей функции чисел Фибоначчи. Получим:

СПИСОК ИСПОЛЬЗОВАННЫХ ЗАДАЧ

[Вальядолид] acm.uva.es/problemset: 495 (Замораживание Фибоначчи), 10334 (Луч сквозь стекло), 10450 (Шум мирового кубка), 10579 (Числа Фибоначчи), 11000 (Пчела).

[Тимус] acm.timus.ru: 1225 (Флаги).