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čunavanjeF(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;
}
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;
}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>| |