De fapt, primele două numere Fibonacci sunt predefinite. Primul număr Fibonacci este 0, iar al doilea număr Fibonacci este 1. Cu indexarea pe bază de zero și presupunând că numerele Fibonacci sunt într-o matrice, atunci:
la index 0 , numărul Fibonacci este 0 , ( predefinite ) ;la index 1 , numărul Fibonacci este 1 , ( predefinite ) ;
la index Două , numărul Fibonacci este 1 = 1 + 0 , ( prin definitie ) ;
la index 3 , numărul Fibonacci este Două = 1 + 1 , ( prin definitie ) ;
la index 4 , numărul Fibonacci este 3 = Două + 1 , ( prin definitie ) ;
la index 5 , numărul Fibonacci este 5 = 3 + Două , ( prin definitie ) ;
la index 6 , numărul Fibonacci este 8 = 5 + 3 , ( prin definitie ) ;
la index 7 , numărul Fibonacci este 13 = 8 + 5 , ( prin definitie ) ;
la index 8 , numărul Fibonacci este douăzeci și unu = 13 + 8 , ( prin definitie ) ;
la index 9 , numărul Fibonacci este 3. 4 = douăzeci și unu + 13 , ( prin definitie ) ;
si asa mai departe.
În programare, variabila n, și nu i este utilizată pentru indicii bazați pe zero pentru aceste numere Fibonacci. Și cu asta, primele douăsprezece numere Fibonacci sunt:
| 0 | 1 | 1 | Două | 3 | 5 | 8 | 13 | douăzeci și unu | 3. 4 | 55 | 89 |
| 0 | 1 | Două | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | unsprezece |
Al doilea rând din tabel oferă indicii bazați pe zero, fiecare dintre care ar avea variabila n în programare. Primul rând oferă numerele Fibonacci corespunzătoare. Deci, numerele Fibonacci nu sunt orice numere. Definiția de bază începe cu 0, pentru primul număr Fibonacci și 1 pentru al doilea număr Fibonacci. Restul numerelor sunt produse de acolo.
Numerele Fibonacci pot fi produse în timp O(n) și, de asemenea, în timp O(1). Pentru timpul O(n), dacă n este 12, de exemplu, atunci primele douăsprezece numere Fibonacci ar fi produse. Pentru timpul O(1), este produs un singur număr Fibonacci. De exemplu, dacă n este 6, atunci ar fi produs numărul Fibonacci 8.
Acest articol explică aceste două moduri de a produce numere Fibonacci în Java.
Formula pentru un număr Fibonacci
Există o formulă matematică pentru un număr Fibonacci. Această formulă poate fi scrisă pe trei rânduri sau pe o singură linie. În trei rânduri, este scris astfel:
unde F n este numărul Fibonacci la n bazat pe zero th index. Așa este definit numărul Fibonacci.
Producerea numerelor Fibonacci în timp O(n).
Dacă numerele Fibonacci vor fi produse în O(3) ori, numerele, 0, 1, 1 ar fi produse; acestea sunt primele trei numere Fibonacci. Ultimul n bazat pe zero th indicele aici, este 2. Dacă numerele Fibonacci vor fi produse de O(7) ori, numerele, 0, 1, 1, 2, 3, 5, 8 ar fi produse; acestea sunt primele șapte numere Fibonacci. Ultimul n bazat pe zero th indicele aici este 6. Dacă numerele Fibonacci vor fi produse în O(n) ori, s-ar produce numerele, 0, 1, 1, 2, 3, 5, 8 – – -; acestea sunt primele n numere Fibonacci. Ultimul n bazat pe zero th indicele aici este n-1.
Metoda Java într-o clasă pentru a produce primele n numere Fibonacci este:
clasă Fibonacci {gol Fibonacci ( int [ ] P ) {
int n = P. lungime ;
dacă ( n > 0 )
P [ 0 ] = 0 ;
dacă ( n > 1 )
P [ 1 ] = 1 ;
pentru ( int i = Două ; i < n ; i ++ ) { //n=0 și n=2 au fost luate în considerare
int currNr = P [ i - 1 ] + P [ i - Două ] ;
P [ i ] = currNr ;
}
}
}
Clasa, Fibonacci este privată. The Fibonacci() metoda ia tabloul P și returnează void. Metoda începe prin determinarea lungimii matricei. Această lungime a lui n este numărul de numere Fibonacci necesare. Primul și al doilea număr Fibonacci sunt determinate în mod explicit și plasate în prima și a doua poziție din matrice.
Restul numerelor Fibonacci începând cu al treilea (indice, n = 2) sunt determinate într-o buclă for și puse în pozițiile lor în matrice. Așadar, funcția trebuie să revină ca void. Declarația principală din bucla for adaugă cele două numere anterioare.
Variabila index, i, a fost folosită în locul lui n, în scopul clarității.
O clasă Java Main adecvată (cu metoda principală Java) este:
public clasă Principal {public static gol principal ( Şir argumente [ ] ) {
int m = 12 ;
int [ ] arr = nou int [ m ] ;
Fibonacci obj = nou Fibonacci ( ) ;
obj. Fibonacci ( arr ) ;
pentru ( int i = 0 ; i < m ; i ++ )
Sistem . afară . imprimare ( arr [ i ] + ' ' ) ;
Sistem . afară . println ( ) ;
}
}
După ce numerele au fost produse prin metoda Fibonacci(), metoda principală Java le citește.
Producerea unui număr Fibonacci în timp constant
Există o formulă matematică care poate fi folosită pentru a produce un număr Fibonacci, atunci când este dat indicele corespunzător bazat pe zero, n. Formula este:
unde n este indicele bazat pe zero și Fib n este numărul Fibonacci corespunzător. Rețineți că în partea dreaptă a ecuației, nu rădăcina pătrată a lui 5 este ridicată la puterea n; este expresia din paranteze care se ridică la puterea n. Există două astfel de expresii.
Dacă n este 0, Fib n ar fi 0. Dacă n este 1, Fib n ar fi 1. Dacă n este 2, Fib n ar fi 1. Dacă n este 3, Fib n ar fi 2. Dacă n este 4, Fib n ar fi 3 – și așa mai departe. Cititorul poate verifica matematic această formulă, înlocuind diferite valori pentru n și evaluând.
Când este codificată, această formulă ar produce doar un număr Fibonacci pentru n. Dacă sunt necesare mai multe numere Fibonacci, codul formulei trebuie apelat o dată pentru fiecare dintre diferiții indici corespunzători.
În Java, metoda de a produce un singur număr Fibonacci este:
import java.lang.* ;clasă Fib {
dubla fibNr ( int n ) {
dubla FibN = ( Matematică . pow ( ( 1 + Matematică . sqrt ( 5 ) ) / Două , n ) – Matematică . pow ( ( 1 - Matematică . sqrt ( 5 ) ) / Două , n ) ) / Matematică . sqrt ( 5 ) ;
întoarcere FibN ;
}
}
Pachetul java.lang.* a trebuit să fie importat la începutul programului. Acest lucru se datorează faptului că pachetul are clasa Math, care are metodele putere (pow) și rădăcină pătrată (sqrt). Metoda Java personalizată aici implementează formula matematică direct.
Complexitatea de timp pentru această funcție este O(1), imblanzirea constantă a unei operații principale. O clasă Java Main adecvată, cu metoda principală Java pentru metoda de mai sus este:
public clasă Principal {public static gol principal ( Şir argumente [ ] ) {
int N = unsprezece ;
Fib obj = nou Fib ( ) ;
dubla dreapta = obj. fibNr ( N ) ;
Sistem . afară . println ( dreapta ) ;
}
}
Se trimite indicele n = 11 și se returnează numărul Fibonacci, 89. Ieșirea este:
89,00000000000003Cifrele zecimale inutile pot fi eliminate, dar aceasta este o discuție pentru altă dată.
Concluzie
Numerele Fibonacci sunt o anumită succesiune de numere întregi. Pentru a obține numărul curent, adăugați imediat cele două numere corespunzătoare anterioare. Primele două numere Fibonacci, 0 urmat de 1, sunt pre-declarate, pentru întreaga secvență. Restul numerelor Fibonacci sunt produse de acolo.
Pentru a produce numere Fibonacci de la indicele 2, la cel care corespunde indicelui n-1, utilizați o buclă for cu declarația principală:
int currNr = P [ i - 1 ] + P [ eu - Două ] ;unde currNo este numărul actual de Fibonacci și P este matricea pentru stocarea celor n numere.
Pentru a produce un singur număr Fibonacci din orice indice n bazat pe zero, utilizați formula matematică:
