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

Редицата с числа на Фибоначи (Fibonacci numbers, Lamé's sequence) е съставена от естествени числа. Рекурентната формула за общия член е F(n) = F(n-1) + F(n-2).

На графиката са представено небалансирано двоично дърво на извиквания с поредните числа на Фибоначи. При изчисляване на всеки следващ номер елемент неизменно се ползват предходните две стойности. Проблемът с дисбаланса на дървото, при рекурсивен алгоритъм,  възнква следствие многократно изчисляване на елементи, които вече са били изчислени.

Задачата за изчисляване числа на Фибоначи е добила широка популярност. Накратко: да се пресметнат броя зайци след година, ако двойка зайци (с различен пол) се размножават всеки месец като на новородения чифт зайци са му необходими два месеца, за да даде първото си поколение, след което същите продължават да се размножават също всеки месец. Задачата е сродна със задачата редица на Narayana и в двете се допуска, че зайците неограничено се размножават. Следващите няколко сегмента код илюстрират различен подход за изчисляване на рекурентната редица: F(n) = F(n-1) + F(n-2) за F(1) = F(2) = 1. Бързото нарастване на стойностите в редицата числа на Фибоначи е илюстрирано на графиката. Следва описание на няколко варианта за програмен код.

Рекурсивен вариант за изчисляване числа на Фибоначи:

 int fib_1(int n)

  {    if (n < 2) return n;

    return fib_1(n - 1) + fib_1(n - 2);

  }  

Вариант с итерация за изчисляване числа на Фибоначи:

  int fib_2(int n)

  { int i,f,a,b;

     f=a=0;   b=1;

     for (i=1;i<n;i++)   {f=a+b;      a=b;      b=f; }

     return f;

}

Изчисляване числа на Фибоначи - модифициран вариант със запомняне на предходните 2 стойности:

  int fib_3(int n)

  { int i,a,b = 1;

        i=a=0;

       for (; i<n; i++)       { a+= b;   b = a - b; }

   return a;

 }

Изчисляване числа на Фибоначи - вариант с масив:

 int fib_4(int n)

{ int j,f[n+1];

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

   for (j=3;j<=n;j++)     { f[j] = f[j-1] + f[j-2]; }

     return f[n];

}

Всеки от разгледаните варианти си има своите предимства и недостатъци.

Използваният алгоритъм в задачата за изчисляване числа на Фибоначи е намерил приложение в множество числови редици - тук са дадени примери с рекурентна формула обхващаща 10 и повече предходни елемента в редицата. Вариантът с масив има линейна сложност и демонстрира едната страна на дилемата памет за скорост. Този вариант е удобен при изчисляване числа на n-nacci като представяне коефициенти на определени полиноми, извеждане на прости числа и други. Рекурсивният вариант за изчисляване числа на Фибоначи демонстрира разликите в скорост и използвана памет в дилемата рекурсия и итерация. Графиката показва дървовидната структура при рекурсивен вариант - многократно се изчисляват едни и същи стойности. Описание на тези извиквания за изчисляване на 7-мото поредно число в списъчен вид: 6+5; 5+4; 4+3; 3+2; 2+1; 2+1; 3+2; 2+1; 4+3; 3+2; 2+1; 2+1.

Част от характерните особености за елементите в редицата числа на Фибоначи са:

F(n+k) = F(k-1)*F(n) + F(k)*F(n+1), където n,k са индекси в редицата;

F(n)^2 - F(n-1)^2 = F(n+1)*F(n-2);

Отношението F(kn)/F(k) е естествено число.

Отношението между две съседни числа на Фибоначи дава приближена стойност на златното сечение ϕ=1.61803399… В триъгълник на Kepler (вид триъгълник от равнината, имащ отношение между дължините на страните 1 : 1.272 : 1.618  = 1 : sqr(ϕ) : ϕ, където ϕ е ирационално число, представящо число на Фидий, златното сечение) се ползват двойка съседни числа на Фибоначи с достатъчно голям индекс.

Разгледайте допълнителен материал за: суми на Фибоначи, триъгълник на Hosoya-Фибоначи, фрактал на Фибоначи, триъгълник с фибономни коефициенти, триъгълник на Фибоначи с разлики, числа на Лукас, редица на заяка. Добре познати числови редици, свързани с числа на Фибоначи (с подобна рекурентна формула) са: числа на Трибоначи, числа на Tetranacci, числа на Pentanacci, числа на Hexanacci, числа на Heptanacci, числа на Octanacci, числа на Nonanacci.