Zapravo, prva dva Fibonaccijeva broja su unaprijed definirana. Prvi Fibonaccijev broj je 0, a drugi Fibonaccijev broj je 1. Uz indeksiranje temeljeno na nuli i pod pretpostavkom da su Fibonaccijevi brojevi u nizu, tada:
na indeksu 0 , Fibonaccijev broj je 0 , ( unaprijed definiran ) ;na indeksu 1 , Fibonaccijev broj je 1 , ( unaprijed definiran ) ;
na indeksu dva , Fibonaccijev broj je 1 = 1 + 0 , ( po definiciji ) ;
na indeksu 3 , Fibonaccijev broj je dva = 1 + 1 , ( po definiciji ) ;
na indeksu 4 , Fibonaccijev broj je 3 = dva + 1 , ( po definiciji ) ;
na indeksu 5 , Fibonaccijev broj je 5 = 3 + dva , ( po definiciji ) ;
na indeksu 6 , Fibonaccijev broj je 8 = 5 + 3 , ( po definiciji ) ;
na indeksu 7 , Fibonaccijev broj je 13 = 8 + 5 , ( po definiciji ) ;
na indeksu 8 , Fibonaccijev broj je dvadeset i jedan = 13 + 8 , ( po definiciji ) ;
na indeksu 9 , Fibonaccijev broj je 3. 4 = dvadeset i jedan + 13 , ( po definiciji ) ;
i tako dalje.
U programiranju se varijabla n, a ne i, koristi za indekse temeljene na nuli za te Fibonaccijeve brojeve. I uz to, prvih dvanaest Fibonaccijevih brojeva su:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvadeset i jedan | 3. 4 | 55 | 89 |
| 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedanaest |
Drugi red u tablici daje indekse temeljene na nuli, od kojih bi svaki imao varijablu n u programiranju. Prvi red daje odgovarajuće Fibonaccijeve brojeve. Dakle, Fibonaccijevi brojevi nisu bilo koji brojevi. Osnovna definicija počinje s 0, za prvi Fibonaccijev broj i 1 za drugi Fibonaccijev broj. Odatle se proizvode ostali brojevi.
Fibonaccijevi brojevi mogu se proizvesti u O(n) vremenu i također u O(1) vremenu. Za O(n) vremena, ako je n, na primjer, 12, tada bi se proizvelo prvih dvanaest Fibonaccijevih brojeva. Za vrijeme O(1) proizvede se samo jedan Fibonaccijev broj. Na primjer, ako je n 6, tada bi se proizveo Fibonaccijev broj 8.
Ovaj članak objašnjava ova dva načina proizvodnje Fibonaccijevih brojeva u Javi.
Formula za Fibonaccijev broj
Postoji matematička formula za Fibonaccijev broj. Ova se formula može napisati u tri retka ili u jednom retku. U tri retka piše se ovako:
gdje je F n je Fibonaccijev broj na bazi n na nuli th indeks. Ovako je definiran Fibonaccijev broj.
Izrada Fibonaccijevih brojeva u O(n) vremenu
Ako Fibonaccijeve brojeve treba proizvesti u O(3) puta, proizvest će se brojevi 0, 1, 1; to su prva tri Fibonaccijeva broja. Posljednji n th indeks ovdje je 2. Ako se Fibonaccijevi brojevi trebaju proizvesti u O(7) puta, proizvest će se brojevi 0, 1, 1, 2, 3, 5, 8; to su prvih sedam Fibonaccijevih brojeva. Posljednji n th indeks ovdje je 6. Ako se Fibonaccijevi brojevi trebaju proizvesti u O(n) puta, proizvest će se brojevi 0, 1, 1, 2, 3, 5, 8 – – -; to su prvih n Fibonaccijevih brojeva. Posljednji n th indeks ovdje je n-1.
Java metoda u klasi za proizvodnju prvih n Fibonaccijevih brojeva je:
razreda Fibonacci {poništiti fibonacci ( int [ ] P ) {
int n = P. duljina ;
ako ( n > 0 )
P [ 0 ] = 0 ;
ako ( n > 1 )
P [ 1 ] = 1 ;
za ( int ja = dva ; ja < n ; ja ++ ) { //n=0 i n=2 su uzeti u obzir
int tekući br = P [ ja - 1 ] + P [ ja - dva ] ;
P [ ja ] = tekući br ;
}
}
}
Klasa, Fibonacci je privatna. The fibonacci() metoda uzima niz P i vraća void. Metoda počinje određivanjem duljine niza. Ova duljina od n je broj potrebnih Fibonaccijevih brojeva. Prvi i drugi Fibonaccijev broj određuju se eksplicitno i stavljaju na prvo i drugo mjesto u nizu.
Ostali Fibonaccijevi brojevi počevši od trećeg (indeks, n = 2) određuju se u for-petlji i stavljaju na svoja mjesta u nizu. Dakle, funkcija mora vratiti void. Glavna izjava u for-petlji zbraja prethodna dva broja.
Varijabla indeksa, i, korištena je umjesto n, radi jasnoće.
Prikladna Java glavna klasa (s Java glavnom metodom) je:
javnost razreda Glavni {javnost statički poništiti glavni ( Niz args [ ] ) {
int m = 12 ;
int [ ] arr = novi int [ m ] ;
Fibonacci obj = novi Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
za ( int ja = 0 ; ja < m ; ja ++ )
Sustav . van . ispisati ( arr [ ja ] + ' ' ) ;
Sustav . van . println ( ) ;
}
}
Nakon što su brojevi proizvedeni metodom fibonacci(), Java main metoda ih očitava.
Izrada jednog Fibonaccijevog broja u konstantnom vremenu
Postoji matematička formula koja se može koristiti za dobivanje Fibonaccijevog broja, kada joj se da odgovarajući indeks temeljen na nuli, n. Formula je:
gdje je n indeks baziran na nuli i Fib n je odgovarajući Fibonaccijev broj. Imajte na umu da na desnoj strani jednadžbe kvadratni korijen od 5 nije podignut na potenciju n; to je izraz u zagradama koji se diže na potenciju n. Dva su takva izraza.
Ako je n 0, Fib n bilo bi 0. Ako je n 1, Fib n bilo bi 1. Ako je n 2, Fib n bilo bi 1. Ako je n 3, Fib n bilo bi 2. Ako je n 4, Fib n bilo bi 3 – i tako dalje. Čitatelj može matematički provjeriti ovu formulu, zamjenom različitih vrijednosti za n i procjenom.
Kada bi se kodirala, ova bi formula proizvela samo jedan Fibonaccijev broj za n. Ako je potrebno više od jednog Fibonaccijevog broja, kod za formulu mora se pozvati jednom za svaki od različitih odgovarajućih indeksa.
U Javi, metoda za proizvodnju samo jednog Fibonaccijevog broja je:
uvoz java.lang.* ;razreda Lagati {
dvostruko fibbr ( int n ) {
dvostruko FibN = ( matematika . pow ( ( 1 + matematika . sqrt ( 5 ) ) / dva , n ) – matematika . pow ( ( 1 - matematika . sqrt ( 5 ) ) / dva , n ) ) / matematika . sqrt ( 5 ) ;
povratak FibN ;
}
}
Paket java.lang.* trebalo je uvesti na početku programa. To je zato što paket ima klasu Math, koja ima metode power (pow) i square root (sqrt). Prilagođena Java metoda ovdje izravno implementira matematičku formulu.
Vremenska složenost za ovu funkciju je O(1), konstanta ukroćenosti jedne glavne operacije. Prikladna Java glavna klasa, s Java glavnom metodom za gornju metodu je:
javnost razreda Glavni {javnost statički poništiti glavni ( Niz args [ ] ) {
int N = jedanaest ;
Fib obj = novi Lagati ( ) ;
dvostruko pravo = obj. fibbr ( N ) ;
Sustav . van . println ( pravo ) ;
}
}
Šalje se indeks n = 11 i vraća se Fibonaccijev broj 89. Izlaz je:
89.0000000000003Nepotrebne decimalne znamenke mogu se ukloniti, ali to je rasprava za neki drugi put.
Zaključak
Fibonaccijevi brojevi su određeni niz cijelih brojeva. Da biste dobili trenutni broj, zbrojite neposredna prethodna dva odgovarajuća broja. Prva dva Fibonaccijeva broja, 0 nakon čega slijedi 1, unaprijed su deklarirana za cijeli niz. Odatle se proizvode ostali Fibonaccijevi brojevi.
Za proizvodnju Fibonaccijevih brojeva od indeksa 2 do onoga koji odgovara indeksu n-1, upotrijebite for-petlju s glavnom izjavom:
int tekući br = P [ ja - 1 ] + P [ ja – dva ] ;gdje je currNo trenutni Fibonaccijev broj, a P niz za pohranu n brojeva.
Da biste proizveli samo jedan Fibonaccijev broj iz bilo kojeg indeksa n temeljenog na nuli, upotrijebite matematičku formulu:
