Fibonacci-lukujen merkitys
Fibonacci-luvut ovat tietty positiivisten kokonaislukujen sarja, joka alkaa nollasta. Kokonaisluvut ovat positiivisia kokonaislukuja. Joten Fibonacci-luku on tietty kokonaislukujen tai luonnollisten lukujen sarja, joka alkaa 0:sta. Tässä sarjassa kaksi ensimmäistä numeroa ovat 0 ja 1 tässä järjestyksessä. Loput luvut kehitetään sieltä lisäämällä kaksi edellistä numeroa. Ensimmäiset kaksitoista Fibonacci-lukua saadaan seuraavasti:
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
Toisin sanoen ensimmäiset kaksitoista Fibonaccin numeroa ovat:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Tietenkin kolmastoista luku olisi: 144 = 55 + 89. Fibonacci-luvut voidaan kuvitella olevan taulukossa, kuten näin:
| 0 | 1 | 1 | kaksi | 3 | 5 | 8 | 13 | kaksikymmentäyksi | 3. 4 | 55 | 89 |
Taulukossa on indeksit. Seuraavan taulukon toisella rivillä näkyy vastaavat nollaperusteiset indeksit Fibonacci-luvuille taulukossa:
| 0 | 1 | 1 | kaksi | 3 | 5 | 8 | 13 | kaksikymmentäyksi | 3. 4 | 55 | 89 |
| 0 | 1 | kaksi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista |
Nollapohjaisilla indekseillä, jos elementtejä on kaksitoista, viimeinen indeksi on 11.
Fibonacci-luvut voidaan tuottaa O(n)-ajassa tai O(1)-ajassa. Näissä aikakompleksisuuslausekkeissa n tarkoittaa n pääoperaatiota ja 1 tarkoittaa 1 pääoperaatiota. O(n:lla) tuotetaan n Fibonacci-lukua alkaen 0:sta. O(1:llä) tuotetaan yksi Fibonacci-luku vastaavasta indeksistä. Tästä syystä O(1) ottaa vain yhden pääoperaation n:n pääoperaation sijaan.
Tämän artikkelin tarkoituksena on selittää, kuinka Fibonacci-lukuja tuotetaan kummallakin tavalla JavaScriptillä, joka on nykyään ECMAScript.
Koodausympäristö
Node.js-ympäristöä ei käytetä, kuten lukija olisi voinut odottaa. Sen sijaan selainta käytetään koodin tulkintaan ja tulosten näyttämiseen. Skripti (koodi) tulee kirjoittaa tekstieditoritiedostoon, joka tulee tallentaa tunnisteella '.html'. Skriptissä tulee olla vähintään koodi:
DOCTYPE HTML >< html >
< pää >
< otsikko > Fibonacci-numerot JavaScriptillä otsikko >
pää >
< kehon >
< skriptityyppi = 'text/ecmascript' >
käsikirjoitus >
kehon >
html >
Tämä on likimääräinen vähimmäiskoodi, jonka verkkosivu tarvitsee. Kaikki tämän artikkelin koodaus menee tunnisteiden väliin.
Suorita kirjoitettu (lisätty) koodi kaksoisnapsauttamalla tiedostonimen kuvaketta ja tietokoneen selain avaa sen.
Fibonacci-luvun määritelmä
Fibonacci-luvulle on olemassa matemaattinen määritelmä. Se määritellään seuraavasti:
Missä Fn on Fibonacci-luku, joka vastaa nollapohjaista indeksiä, n.
Kaksi ensimmäistä numeroa: 0 ja 1, on ennalta ilmoitettu tässä järjestyksessä. Tämän funktion viimeinen rivi näyttää, kuinka loput luvut ovat peräisin kahdesta ensimmäisestä numerosta niiden järjestyksessä.
Tämä määritelmä on myös yksi Fibonacci-luvun kaavoista.
Fibonacci-lukujen tuottaminen O(n) ajassa
Jos n on 1, vain 0 näytetään Fibonacci-lukuna. Jos n on 2, 0 ja 1 näytetään Fibonacci-lukuina tässä järjestyksessä. Jos n on 3, 0, 1 ja 1 näytetään Fibonacci-lukuina tässä järjestyksessä. Jos n on 4, 0, 1, 1 ja 2 näytetään Fibonacci-lukuina tässä järjestyksessä. Jos n on 5, niin 0, 1, 1, 2 ja 3 näytetään Fibonacci-lukuina tässä järjestyksessä. Jos n on 6, niin 0, 1, 1, 2, 3 ja 5 näytetään Fibonacci-lukuina tässä järjestyksessä – ja niin edelleen.
Ensimmäiset n Fibonacci-kokonaislukua (lukua) luova ECMAscript-funktio on:
< skriptityyppi = 'text/ecmascript' >toiminto fibonacci ( A ) {
n = A. pituus ;
jos ( n > 0 )
A [ 0 ] = 0 ;
jos ( n > 1 )
A [ 1 ] = 1 ;
varten ( i = kaksi ; i < n ; i ++ ) { //n=0 ja n=2 on otettu huomioon
CurrNo = A [ i - 1 ] + A [ i - kaksi ] ;
A [ i ] = CurrNo ;
}
}
Päättävä komentosarjatunniste ei ole näkyvissä. Funktio vastaanottaa taulukon. Kaksi ensimmäistä Fibonacci-numeroa määritetään niiden sijainnissa. For-silmukka iteroituu nollapohjaisesta indeksistä, 2:sta juuri n:n alapuolelle. Tärkein lause for-silmukassa on:
currNo = A[i – 1] + A[i – 2];
Tämä lisää taulukon kaksi välitöntä edellistä numeroa nykyisen numeron saamiseksi. Kun fibonacci()-funktio on suoritettu loppuun, kaikki taulukon elementit ovat ensimmäiset n Fibonacci-lukua. Sopiva koodi fibonacci()-funktion kutsumiseen ja Fibonacci-lukujen näyttämiseen on:
N = 12 ;arr = Uusi Array ( N ) ;
fibonacci ( arr ) ;
varten ( i = 0 ; i < N ; i ++ )
asiakirja. kirjoittaa ( arr [ i ] + '' ) ;
asiakirja. kirjoittaa ( '
' ) ;
käsikirjoitus >
Tämä koodi näyttää sulkevan komentosarjatunnisteen. Koodi kirjoitetaan yllä olevan koodin alle. Verkkosivulla näkyvä tulos on:
0 1 1 2 3 5 8 13 21 34 55 89
odotetusti.
Yhden Fibonacci-luvun tuottaminen O(1)-ajassa
O(1) on vakioaika. Se viittaa yhteen päätoimintoon. Toinen matemaattinen kaava Fibonacci-luvun tuottamiseksi on:
Huomaa, että yhtälön oikealla puolella ei ole 5:n neliöjuuri, joka korotetaan potenssiin n; se on suluissa oleva lauseke, joka nostetaan potenssiin n. Tällaisia ilmaisuja on kaksi.
Jos n on 0, Fibn olisi 0. Jos n on 1, Fibn olisi 1. Jos n on 2, Fibn olisi 1. Jos n on 3, Fibn olisi 2. Jos n on 4, Fibn olisi 3 – ja niin edelleen. Lukija voi tarkistaa tämän kaavan matemaattisesti korvaamalla n:n eri arvoilla ja arvioimalla. n on nollaperusteinen indeksi tässä kaavassa. Tuloksena on vastaava Fibonacci-luku.
Tämän kaavan ECMAScript (JavaScript) -koodi on:
< skriptityyppi = 'text/ecmascript' >toiminto fibNo ( n ) {
FibN = ( Matematiikka . pow ( ( 1 + Matematiikka . sqrt ( 5 ) ) / kaksi , n ) - Matematiikka . pow ( ( 1 - Matematiikka . sqrt ( 5 ) ) / kaksi , n ) ) / Matematiikka . sqrt ( 5 ) ;
palata FibN ;
}
Päättävä komentosarjatunniste ei ole näkyvissä. Huomaa, kuinka teho (pow) ja neliöjuuri (sqrt) ennalta määritettyjä funktioita on käytetty. ECMAScriptissä (JavaScript) Math-moduulia ei tarvitse tuoda. Funktio fibNo() toteuttaa kaavan suoraan. Sopiva kutsu ja näyttö fibNo()-funktiolle verkkosivulla ovat:
N = yksitoista ;oikein = fibNo ( N ) ;
asiakirja. kirjoittaa ( oikein ) ;
käsikirjoitus >
Koodi näyttää sulkevan komentosarjan tunnisteen. Lähtö on:
89.00000000000003
Tarpeettomat desimaaliluvut on mahdollista poistaa vastauksesta. Tämä on kuitenkin keskustelua toisen kerran.
Jos tarvitaan useampi kuin yksi Fibonacci-luku, koodin on kutsuttava kaava kerran jokaiselle nollapohjaiselle vastaavalle n-indeksille.
Johtopäätös
Fibonacci-luvut ovat tietty positiivisten kokonaislukujen sarja, joka alkaa nollasta. Kokonaisluvut ovat positiivisia kokonaislukuja. Joten Fibonacci-luku on tietty kokonaislukujen tai luonnollisten lukujen sarja, joka alkaa 0:sta. Tässä sarjassa kaksi ensimmäistä numeroa ovat 0 ja 1 tässä järjestyksessä. Nämä kaksi ensimmäistä numeroa on vain määritelty sellaisiksi. Loput luvut kehitetään sieltä lisäämällä välittömästi edelliset kaksi numeroa.
Kun kaksi ensimmäistä Fibonacci-lukua on tuotettu, jotta loput Fibonacci-luvut saadaan, jotta saadaan yhteensä n numeroa, on käytettävä for-silmukkaa lauseen kanssa:
currNo = A[i – 1] + A[i – 2];
Tämä lisää välittömästi kaksi viimeistä Fibonacci-lukua nykyisen Fibonacci-luvun saamiseksi.
Kun sinulle annetaan nollapohjainen indeksi, käytä kaavaa saadaksesi vastaavan Fibonacci-luvun:
