Fibonacci numbrite tähendus
Fibonacci arvud on teatud positiivsete täisarvude jada, mis algab 0-st. Täisarvud on positiivsed täisarvud. Seega on Fibonacci arv teatud täisarvude või naturaalarvude jada, mis algab nullist. Selles jadas on kaks esimest numbrit 0 ja 1, selles järjekorras. Ülejäänud numbrid arendatakse sealt edasi, liites kaks eelmist numbrit. Esimesed kaksteist Fibonacci arvu saadakse järgmiselt:
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
Teisisõnu on esimesed kaksteist Fibonacci numbrit:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Loomulikult oleks kolmeteistkümnes arv: 144 = 55 + 89. Fibonacci numbreid võib kujutada massiivina, näiteks:
| 0 | 1 | 1 | kaks | 3 | 5 | 8 | 13 | kakskümmend üks | 3. 4 | 55 | 89 |
Massiivil on indeksid. Järgmises tabelis on teisel real näidatud vastavad nullipõhised indeksid massiivi Fibonacci numbrite jaoks:
| 0 | 1 | 1 | kaks | 3 | 5 | 8 | 13 | kakskümmend üks | 3. 4 | 55 | 89 |
| 0 | 1 | kaks | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | üksteist |
Nullipõhiste indeksite puhul, kui elemente on kaksteist, on viimane indeks 11.
Fibonacci numbreid saab luua O(n) aja või O(1) aja järgi. Nendes aja keerukuse avaldistes tähendab n n põhitoimingut ja 1 tähendab 1 põhitoimingut. O(n) korral saadakse n Fibonacci arvu, alustades 0-st. O(1) korral saadakse vastavast indeksist üks Fibonacci arv. Seetõttu võtab O(1) vaid ühe põhitehte n põhitehte asemel.
Selle artikli eesmärk on selgitada, kuidas toota Fibonacci numbreid mõlemal juhul JavaScripti abil, mis tänapäeval on tegelikult ECMAScript.
Kodeerimiskeskkond
Keskkonda node.js ei kasutata nii, nagu lugeja oleks võinud eeldada. Selle asemel kasutatakse koodi tõlgendamiseks ja tulemuste kuvamiseks brauserit. Skript (kood) tuleks kirjutada tekstiredaktori faili, mis tuleks salvestada laiendiga .html. Skriptil peaks olema minimaalne kood:
DOCTYPE HTML >< html >
< pea >
< pealkiri > Fibonacci numbrid JavaScriptiga pealkiri >
pea >
< keha >
< skripti tüüp = 'text/ecmascript' >
stsenaarium >
keha >
html >
See on ligikaudne miinimumkood, mida veebileht vajab. Kogu selle artikli kodeerimine toimub märgendite vahel.
Kirjutatud (lisatud) koodi käivitamiseks topeltklõpsake failinime ikoonil ja arvuti brauser avab selle.
Fibonacci arvu määratlus
Fibonacci arvu jaoks on matemaatiline määratlus. See on määratletud järgmiselt:
Kui Fn on Fibonacci arv, mis vastab nullipõhisele indeksile, siis n.
Esimesed kaks numbrit: 0 ja 1 on eeldeklareeritud selles järjekorras. Selle funktsiooni viimane rida näitab, kuidas ülejäänud numbrid pärinevad kahest esimesest numbrist nende järjekorras.
See määratlus on ka üks Fibonacci arvu valemeid.
Fibonacci arvude tootmine O(n) ajas
Kui n on 1, kuvatakse Fibonacci arvuna ainult 0. Kui n on 2, siis kuvatakse 0 ja 1 Fibonacci numbritena selles järjekorras. Kui n on 3, siis 0, 1 ja 1 kuvatakse Fibonacci numbritena selles järjekorras. Kui n on 4, kuvatakse 0, 1, 1 ja 2 Fibonacci arvudena selles järjekorras. Kui n on 5, siis 0, 1, 1, 2 ja 3 kuvatakse Fibonacci numbritena selles järjekorras. Kui n on 6, siis 0, 1, 1, 2, 3 ja 5 kuvatakse Fibonacci numbritena, selles järjekorras – ja nii edasi.
ECMAscripti funktsioon esimese n Fibonacci täisarvu (arvu) genereerimiseks on:
< skripti tüüp = 'text/ecmascript' >funktsiooni fibonacci ( A ) {
n = A. pikkus ;
kui ( n > 0 )
A [ 0 ] = 0 ;
kui ( n > 1 )
A [ 1 ] = 1 ;
jaoks ( i = kaks ; i < n ; i ++ ) { //n=0 ja n=2 on arvesse võetud
CurrNo = A [ i - 1 ] + A [ i - kaks ] ;
A [ i ] = CurrNo ;
}
}
Sulgevat skripti silti pole näidatud. Funktsioon võtab vastu massiivi. Esimesed kaks Fibonacci numbrit määratakse nende asukohale. For-silmus itereerub nullipõhisest indeksist, 2 kuni veidi alla n. For-tsükli kõige olulisem väide on:
currNo = A[i – 1] + A[i – 2];
See lisab massiivi kaks vahetult eelmist numbrit, et saada praegune number. Selleks ajaks, kui funktsioon fibonacci() on täitmise lõpetanud, on kõik massiivi elemendid esimesed n Fibonacci numbrit. Sobiv kood funktsiooni fibonacci() kutsumiseks ja Fibonacci numbrite kuvamiseks on:
N = 12 ;arr = uus Massiiv ( N ) ;
fibonacci ( arr ) ;
jaoks ( i = 0 ; i < N ; i ++ )
dokument. kirjutada ( arr [ i ] + '' ) ;
dokument. kirjutada ( '
' ) ;
stsenaarium >
See kood näitab sulgemisskripti silti. Kood sisestatakse ülaltoodud koodi alla. Veebilehel kuvatav väljund on:
0 1 1 2 3 5 8 13 21 34 55 89
ootuspäraselt.
Ühe Fibonacci numbri loomine O(1) aja jooksul
O(1) on konstantne aeg. See viitab ühele põhitoimingule. Teine matemaatiline valem Fibonacci arvu saamiseks on:
Pange tähele, et võrrandi paremal küljel ei ole 5 ruutjuur, mis on tõstetud astmeni n; see on sulgudes olev avaldis, mis tõstetakse astmeni n. Selliseid väljendeid on kaks.
Kui n on 0, oleks Fibn 0. Kui n on 1, oleks Fibn 1. Kui n on 2, oleks Fibn 1. Kui n on 3, oleks Fibn 2. Kui n on 4, oleks Fibn 3 – ja nii edasi. Lugeja saab seda valemit matemaatiliselt kontrollida, asendades n-i erinevate väärtustega ja hinnates. n on selles valemis nullipõhine indeks. Tulemuseks on vastav Fibonacci arv.
Selle valemi ECMAScript (JavaScript) kood on:
< skripti tüüp = 'text/ecmascript' >funktsiooni fibNo ( n ) {
FibN = ( matemaatika . pow ( ( 1 + matemaatika . sqrt ( 5 ) ) / kaks , n ) - matemaatika . pow ( ( 1 - matemaatika . sqrt ( 5 ) ) / kaks , n ) ) / matemaatika . sqrt ( 5 ) ;
tagasi FibN ;
}
Sulgevat skripti silti pole näidatud. Pange tähele, kuidas on kasutatud võimsuse (pow) ja ruutjuure (sqrt) eelmääratletud funktsioone. ECMAScriptis (JavaScript) ei pea matemaatikamoodulit importima. Funktsioon fibNo() rakendab valemi otse. Sobivad väljakutsed ja kuvad funktsiooni fibNo() jaoks veebilehel on:
N = üksteist ;õige = fibNo ( N ) ;
dokument. kirjutada ( õige ) ;
stsenaarium >
Kood näitab sulgemisskripti silti. Väljund on:
89.00000000000003
Vastusest on võimalik eemaldada mittevajalikud kümnendkohad. See on aga mõne teise korra arutelu.
Kui nõutakse rohkem kui ühte Fibonacci numbrit, peab kood iga nullipõhise vastava n-indeksi jaoks valemit üks kord kutsuma.
Järeldus
Fibonacci arvud on teatud positiivsete täisarvude jada, mis algab 0-st. Täisarvud on positiivsed täisarvud. Seega on Fibonacci arv teatud täisarvude või naturaalarvude jada, mis algab nullist. Selles jadas on kaks esimest numbrit 0 ja 1, selles järjekorras. Need kaks esimest numbrit on lihtsalt sellistena määratletud. Ülejäänud arvud arendatakse sealt edasi, liites kaks vahetult eelnevat numbrit.
Pärast kahe esimese Fibonacci arvu loomist tuleb ülejäänud Fibonacci arvude saamiseks, et saada kokku n arvu, kasutada lausega for-tsüklit:
currNo = A[i – 1] + A[i – 2];
See lisab kaks viimast Fibonacci numbrit, et saada praegune Fibonacci number.
Nullipõhise indeksi korral kasutage vastava Fibonacci numbri saamiseks järgmist valemit:
