Choose jour language!

---

|

FIBONAČIJEV NIZ BROJEVA

---

---

Niz brojeva koji je dobio naziv po Italijanskom matematičaru Leonardu od Pise, poznatijem kao Fibonacci. To su brojevi koji se , ako znamo prva dva broja
f0=0 i
f1=1,
dobijaju po formuli:
 fn=fn-1 + fn-2,  n>2

Svaki novi član niza se dobija kao zbir prethodna 2. 

Fibonačijev niz:
0,1,1,2,3,5,8,13,21,34,55,89,144,....

Primer koji ilustruje ovaj niz brojeva može se videti na slici 1:

​Ovi brojevi imaju veliku primenu u  prirodi. Broj latica na cvetu, broj spirala na suncokretu , šišarka, košnica, listovi na grani, školjka puža Nautilus je tipično Fibonačijev niz.
I kod pčela se može uočiti Fibonačijev niz, jer u košnici uvek ima manje trutova nego pčela. A kada bi podelio broj ženki s brojem mužjaka, dobio bi broj koji predstavlja odnos između dva susedna člana Fibonačijevog niza, što je ujedno i broj fi.

Fibonačijev niz i priroda

Slika 1: Popločanje s kvadratima čije su stranice po dužini sukcesivni Fibonaccijevi brojevi

Slika 2: Fibonačijev niz - Spirala

Određivanje n-tog Fibonačijevog broja-rekurzijom

Jedno od mogućih rešenja je pomoću rekurzije. Napravimo funkciju za određivanje broja iz Fibonačijevog niza na poziciji koja je poslata kao parametar funkcije. Pošto je za izračunavanje
F(N)= F(N-1) + F(N-2)
potrebno ponovo pozvati funkciju, ali sada sa poslatim pozicijama N-1 odnosno N-2, to znači da funkcija mora pozivati samu sebe više puta rekurzivno. Ovaj način nije naročito efikasan za velike podatke zbog prevelikog broja poziva kreirane funkcije.

using namespace std;

int fib(int n)

{

  if(n<=1)

  return n;

 int f1=fib(n-1);

 int f2=fib(n-2);

 return f1+f2;

}

int main()

{

 int N,x;

 cin >> N;

 x=fib(N);

 cout << x << endl;

 return 0;

}

Na slici 2 su prikazani pozivi funkcije za određivanje 4-tog elementa Fibonačijevog niza. Može se zaključiti da će za veće pozicije biti previše rekurzivnih poziva funkcije, tako da je izvršavanje sporo.

Slika 2: Određivanje n tog elementa Fibonačijevog niza rekurzijom - pozivi funkcija

​Određivanje n-tog fibonačijevog broja - dinamičko programiranje

U ovom slučaju, da bi skratili vreme izvršavanja, pamtimo u niz one vrednosti koje su prethodno izračunate. Ovde nema rekurzije, nego se funkcija poziva samo jedanput, a onda se, koristeći for petlju, izračunava svaki  tekući element, sabiranjem njegova dva prethodnika zapamćena u nizu f; 

using namespace std;

int fib(int n)

{

 int f[n+2];
 f[0]=0;

 f[1]=1;

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

 {

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

 }

 return f[n];

}

int main()

{

 int N,x;

 cin >> N;

 x=fib(N);

 cout << x << endl;

 return 0;

}

Određivanje n-tog fibonačijevog broja - dinamičko programiranje-optimizovana metoda

Prethodni kod može da se dodatno ubrza ako, umesto da pamtimo ceo niz, pamtimo samo dva poslednja elementa:

using namespace std;

int fib(int n)

{

 long long a,b,f;
 a=0;
 b=1;
 for(long long i=2; i<=n; i++)

 {

   f=a+b;
   a=b;
   b=f;

 }

return f;

}

int main()

{

 long long N,x;

 cin >> N;

 x=fib(N);

 cout << x << endl;

 return 0;

}

U početku su prethodnici a i b inicijalizovani na 0 i 1. Kada se odredi novi Fibonačijev broj kao zvir prethodnika a i b, onda se pripreme prethodnici za novu iteraciju: drugi u sledećem jednak je izračunatom Fibonačijevom broju u tekućem ciklusu 
b=f
dok je prvi prethodnik novog ciklusa, zapravo onaj koji je u tekućem ciklusu bio drugi prethodnik:
a=b.

Ako želiš da naučiš kako se Fibonacci optimizuje pomoću dinamičkog programiranja (memoizacija i tabulacija), pogledaj detaljnu lekciju:
DP Fibonacci — memoizacija i tabulacija

---

Prethodno
​|< Matematički algoritmi

Sledeće
​​Prosti brojevi i faktorizacija >|

---

---