Semnificația numerelor Fibonacci
Numerele Fibonacci sunt o anumită succesiune de numere întregi pozitive, începând cu 0. Numerele întregi sunt numere întregi pozitive. Deci, un număr Fibonacci este o anumită succesiune de numere întregi sau naturale, începând de la 0. În această secvență, primele două numere sunt 0 și 1, în această ordine. Restul numerelor sunt dezvoltate de acolo prin adăugarea celor două numere anterioare. Primele douăsprezece numere Fibonacci se obțin după cum urmează:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Cu alte cuvinte, primele douăsprezece numere Fibonacci sunt:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Desigur, al treisprezecelea număr ar fi: 144 = 55 + 89. Numerele Fibonacci pot fi imaginate ca fiind într-o matrice, astfel:
| 0 | 1 | 1 | Două | 3 | 5 | 8 | 13 | douăzeci și unu | 3. 4 | 55 | 89 |
O matrice are indecși. În următorul tabel, al doilea rând arată indecșii corespunzători pe bază de zero pentru numerele Fibonacci dintr-o matrice:
| 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 |
Cu indici bazați pe zero, dacă există douăsprezece elemente, atunci ultimul indice este 11.
Numerele Fibonacci pot fi produse în timp O(n) sau în timp O(1). În aceste expresii de complexitate temporală, n înseamnă n operații principale, iar 1 înseamnă o operație principală. Cu O(n), se produc n numere Fibonacci, începând de la 0. Cu O(1), se produce un număr Fibonacci din indicele corespunzător. De aceea, O(1) ia doar o operație principală în loc de n operații principale.
Scopul acestui articol este de a explica cum să produci numere Fibonacci, în orice caz, folosind JavaScript, care este de fapt ECMAScript astăzi.
Mediul de codificare
Mediul node.js nu va fi folosit așa cum ar fi anticipat cititorul. În schimb, browserul va fi folosit pentru interpretarea codului și afișarea rezultatelor. Scriptul (codul) trebuie scris într-un fișier editor de text, care ar trebui salvat cu extensia „.html”. Scriptul ar trebui să aibă ca cod minim:
DOCTYPE HTML >< html >
< cap >
< titlu > Numerele Fibonacci cu JavaScript titlu >
cap >
< corp >
< tip de script = „text/ecmascript” >
scenariu >
corp >
html >
Acesta este un cod minim aproximativ de care are nevoie o pagină web. Toată codificarea acestui articol se află între etichete, .
Pentru a rula codul scris (adăugat), faceți dublu clic pe pictograma numelui fișierului, iar browserul computerului îl va deschide.
Definiția unui număr Fibonacci
Există o definiție matematică pentru un număr Fibonacci. Este definit astfel:
Unde Fn este un număr Fibonacci corespunzător unui indice bazat pe zero, n.
Primele două numere: 0 și 1, sunt predeclarate, în această ordine. Ultima linie a acestei funcții arată cum restul numerelor provin din primele două numere în ordinea lor.
Această definiție este, de asemenea, una dintre formulele pentru numărul Fibonacci.
Producerea numerelor Fibonacci în timp O(n).
Dacă n este 1, atunci doar 0 ar fi afișat ca număr Fibonacci. Dacă n este 2, atunci 0 și 1 ar fi afișate ca numere Fibonacci, în această ordine. Dacă n este 3, atunci 0, 1 și 1 vor fi afișate ca numere Fibonacci în această ordine. Dacă n este 4, atunci 0, 1, 1 și 2 vor fi afișate ca numere Fibonacci, în această ordine. Dacă n este 5, atunci 0, 1, 1, 2 și 3 vor fi afișate ca numere Fibonacci, în această ordine. Dacă n este 6, atunci 0, 1, 1, 2, 3 și 5 vor fi afișate ca numere Fibonacci, în această ordine – și așa mai departe.
Funcția ECMAscript pentru a genera primele n numere întregi Fibonacci este:
< tip de script = „text/ecmascript” >funcţie Fibonacci ( A ) {
n = A. lungime ;
dacă ( n > 0 )
A [ 0 ] = 0 ;
dacă ( n > 1 )
A [ 1 ] = 1 ;
pentru ( i = Două ; i < n ; i ++ ) { //n=0 și n=2 au fost luate în considerare
currNr = A [ i - 1 ] + A [ i - Două ] ;
A [ i ] = currNr ;
}
}
Eticheta scriptului de închidere nu a fost afișată. Funcția primește o matrice. Primele două numere Fibonacci sunt atribuite la poziția lor. Bucla for iterează de la indicele bazat pe zero, de la 2 la chiar sub n. Cea mai importantă declarație din bucla for este:
currNo = A[i – 1] + A[i – 2];
Aceasta adaugă cele două numere anterioare imediate din matrice pentru a avea numărul curent. Până la sfârșitul executării funcției fibonacci(), toate elementele matricei sunt primele n numere Fibonacci. Un cod potrivit pentru a apela funcția fibonacci() și pentru a afișa numerele Fibonacci este:
N = 12 ;arr = nou Matrice ( N ) ;
Fibonacci ( arr ) ;
pentru ( i = 0 ; i < N ; i ++ )
document. scrie ( arr [ i ] + ' ' ) ;
document. scrie ( „
” ) ;
scenariu >
Acest cod arată eticheta scriptului de închidere. Codul este introdus sub codul de mai sus. Rezultatul afișat pe pagina web este:
0 1 1 2 3 5 8 13 21 34 55 89
cum era de așteptat.
Producerea unui număr Fibonacci în timp O(1).
O(1) este timp constant. Se referă la o operație principală. O altă formulă matematică pentru a produce un număr Fibonacci este:
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, Fibn ar fi 0. Dacă n este 1, Fibn ar fi 1. Dacă n este 2, Fibn ar fi 1. Dacă n este 3, Fibn ar fi 2. Dacă n este 4, Fibn ar fi 3 - si asa mai departe. Cititorul poate verifica matematic această formulă prin înlocuirea diferitelor valori pentru n și evaluând. n este un indice bazat pe zero în această formulă. Rezultatul este numărul Fibonacci corespunzător.
Codul ECMAScript (JavaScript) pentru această formulă este:
< tip de script = „text/ecmascript” >funcţie fibNr ( n ) {
FibN = ( Matematică . pow ( ( 1 + Matematică . sqrt ( 5 ) ) / Două , n ) - Matematică . pow ( ( 1 - Matematică . sqrt ( 5 ) ) / Două , n ) ) / Matematică . sqrt ( 5 ) ;
întoarcere FibN ;
}
Eticheta scriptului de închidere nu a fost afișată. Observați cum au fost utilizate funcțiile predefinite de putere (pow) și rădăcină pătrată (sqrt). În ECMAScript (JavaScript), modulul Math nu trebuie să fie importat. Funcția fibNo() implementează formula direct. Un apel și afișare adecvate pentru funcția fibNo() de pe pagina web sunt:
N = unsprezece ;dreapta = fibNr ( N ) ;
document. scrie ( dreapta ) ;
scenariu >
Codul arată eticheta scriptului de închidere. Ieșirea este:
89,00000000000003
Este posibil să eliminați cifrele zecimale inutile din răspuns. Cu toate acestea, aceasta este o discuție pentru altă dată.
Dacă este necesar mai mult de un număr Fibonacci, atunci codul trebuie să apeleze formula o dată pentru fiecare indice n corespunzător bazat pe zero.
Concluzie
Numerele Fibonacci sunt o anumită succesiune de numere întregi pozitive, începând cu 0. Numerele întregi sunt numere întregi pozitive. Deci, un număr Fibonacci este o anumită succesiune de numere întregi sau naturale, începând de la 0. În această secvență, primele două numere sunt 0 și 1, în această ordine. Aceste prime două numere sunt doar definite ca atare. Restul numerelor sunt dezvoltate de acolo prin adăugarea celor două numere anterioare imediate.
După producerea primelor două numere Fibonacci, pentru a produce restul numerelor Fibonacci, pentru a obține un total de n numere, trebuie folosită o buclă for cu declarația:
currNo = A[i – 1] + A[i – 2];
Aceasta adaugă imediat ultimele două numere Fibonacci pentru a avea numărul actual Fibonacci.
Când i se oferă un indice pe bază de zero, pentru a avea numărul Fibonacci corespunzător, utilizați formula:
