Pomen Fibonaccijevih števil
Fibonaccijeva števila so določeno zaporedje pozitivnih celih števil, ki se začnejo z 0. Cela števila so pozitivna cela števila. Torej je Fibonaccijevo število določeno zaporedje celih ali naravnih števil, ki se začnejo z 0. V tem zaporedju sta prvi dve števili 0 in 1, v tem vrstnem redu. Preostale številke se razvijejo od tam z dodajanjem prejšnjih dveh številk. Prvih dvanajst Fibonaccijevih števil dobimo na naslednji način:
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
Z drugimi besedami, prvih dvanajst Fibonaccijevih števil je:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Seveda bi bilo trinajsto število: 144 = 55 + 89. Fibonaccijeva števila si lahko predstavljamo v nizu, takole:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | enaindvajset | 3. 4 | 55 | 89 |
Matrika ima indekse. V naslednji tabeli druga vrstica prikazuje ustrezne indekse na osnovi nič za Fibonaccijeva števila v matriki:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | enaindvajset | 3. 4 | 55 | 89 |
| 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | enajst |
Če je pri indeksih na osnovi nič dvanajst elementov, je zadnji indeks 11.
Fibonaccijeva števila je mogoče ustvariti v O(n) času ali v O(1) času. V teh izrazih za časovno kompleksnost n pomeni n glavnih operacij, 1 pa 1 glavno operacijo. Z O(n) se ustvari n Fibonaccijevih števil, začenši z 0. Z O(1) se iz ustreznega indeksa ustvari eno Fibonaccijevo število. Zato O(1) sprejme samo eno glavno operacijo namesto n glavnih operacij.
Namen tega članka je razložiti, kako ustvariti Fibonaccijeva števila, tako ali drugače, z uporabo JavaScripta, ki je danes pravzaprav ECMAScript.
Okolje kodiranja
Okolje node.js ne bo uporabljeno, kot je bralec morda pričakoval. Namesto tega bo brskalnik uporabljen za interpretacijo kode in prikaz rezultatov. Skript (koda) mora biti zapisana v datoteki urejevalnika besedil, ki naj bo shranjena s pripono “.html.” Skript mora imeti minimalno kodo:
DOCTYPE HTML >< html >
< glavo >
< naslov > Fibonaccijeva števila z JavaScriptom naslov >
glavo >
< telo >
< vrsta skripte = 'text/ecmascript' >
scenarij >
telo >
html >
To je približna minimalna koda, ki jo potrebuje spletna stran. Vse kodiranje za ta članek je vmesno med oznakama .
Za zagon napisane (dodane) kode preprosto dvokliknite ikono imena datoteke in brskalnik računalnika jo bo odprl.
Definicija Fibonaccijevega števila
Obstaja matematična definicija Fibonaccijevega števila. Opredeljen je na naslednji način:
Kjer je Fn Fibonaccijevo število, ki ustreza indeksu na osnovi ničle, n.
Prvi dve številki: 0 in 1 sta vnaprej deklarirani v tem vrstnem redu. Zadnja vrstica te funkcije prikazuje, kako ostale številke izvirajo iz prvih dveh številk v njihovem vrstnem redu.
Ta definicija je tudi ena od formul za Fibonaccijevo število.
Izdelava Fibonaccijevih števil v O(n) času
Če je n 1, bi bila kot Fibonaccijevo število prikazana samo 0. Če je n 2, bi bili 0 in 1 prikazani kot Fibonaccijevi števili v tem vrstnem redu. Če je n 3, bi bile 0, 1 in 1 prikazane kot Fibonaccijeva števila v tem vrstnem redu. Če je n 4, bi bile 0, 1, 1 in 2 prikazane kot Fibonaccijeva števila v tem vrstnem redu. Če je n 5, bi bile 0, 1, 1, 2 in 3 prikazane kot Fibonaccijeva števila v tem vrstnem redu. Če je n 6, bi bile 0, 1, 1, 2, 3 in 5 prikazane kot Fibonaccijeva števila v tem vrstnem redu – in tako naprej.
Funkcija ECMAscript za generiranje prvih n Fibonaccijevih celih števil (števil) je:
< vrsta skripte = 'text/ecmascript' >funkcijo fibonacci ( A ) {
n = A. dolžina ;
če ( n > 0 )
A [ 0 ] = 0 ;
če ( n > 1 )
A [ 1 ] = 1 ;
za ( jaz = dva ; jaz < n ; jaz ++ ) { //upoštevana sta bila n=0 in n=2
št = A [ jaz - 1 ] + A [ jaz - dva ] ;
A [ jaz ] = št ;
}
}
Oznaka zaključnega skripta ni bila prikazana. Funkcija prejme matriko. Prvi dve Fibonaccijevi števili sta dodeljeni na svojem mestu. Zanka for se ponavlja od indeksa, ki temelji na ničli, 2 do tik pod n. Najpomembnejša izjava v for-zanki je:
currNo = A[i – 1] + A[i – 2];
To doda takojšnji dve številki v matriki, da dobi trenutno številko. Ko se funkcija fibonacci() konča z izvajanjem, so vsi elementi matrike prvih n Fibonaccijevih števil. Primerna koda za klic funkcije fibonacci() in prikaz Fibonaccijevih števil je:
n = 12 ;prir = novo Array ( n ) ;
fibonacci ( prir ) ;
za ( jaz = 0 ; jaz < n ; jaz ++ )
dokument. pisati ( prir [ jaz ] + ' ' ) ;
dokument. pisati ( '
' ) ;
scenarij >
Ta koda prikazuje zaključno oznako skripta. Koda je vnesena pod zgornjo kodo. Rezultat, prikazan na spletni strani, je:
0 1 1 2 3 5 8 13 21 34 55 89
kot je bilo pričakovano.
Izdelava enega Fibonaccijevega števila v O(1) času
O(1) je konstanten čas. Nanaša se na eno glavno operacijo. Druga matematična formula za izdelavo Fibonaccijevega števila je:
Upoštevajte, da na desni strani enačbe kvadratni koren iz 5 ni dvignjen na potenco n; to je izraz v oklepaju, ki je dvignjen na potenco n. Obstajata dva taka izraza.
Če je n 0, bi bil Fibn 0. Če je n 1, bi bil Fibn 1. Če je n 2, bi bil Fibn 1. Če je n 3, bi bil Fibn 2. Če je n 4, bi bil Fibn 3 – in tako naprej. Bralec lahko to formulo matematično preveri z zamenjavo različnih vrednosti za n in ovrednotenjem. n je v tej formuli indeks na osnovi nič. Rezultat je ustrezno Fibonaccijevo število.
Koda ECMAScript (JavaScript) za to formulo je:
< vrsta skripte = 'text/ecmascript' >funkcijo fibŠt ( n ) {
FibN = ( matematika . pow ( ( 1 + matematika . sqrt ( 5 ) ) / dva , n ) - matematika . pow ( ( 1 - matematika . sqrt ( 5 ) ) / dva , n ) ) / matematika . sqrt ( 5 ) ;
vrnitev FibN ;
}
Oznaka zaključnega skripta ni bila prikazana. Upoštevajte, kako sta bili uporabljeni vnaprej določeni funkciji moči (pow) in kvadratni koren (sqrt). V ECMAScript (JavaScript) modula Math ni treba uvoziti. Funkcija fibNo() neposredno izvaja formulo. Primeren klic in prikaz za funkcijo fibNo() na spletni strani sta:
n = enajst ;prav = fibŠt ( n ) ;
dokument. pisati ( prav ) ;
scenarij >
Koda prikazuje zaključno oznako skripta. Rezultat je:
89.0000000000003
Iz odgovora je mogoče odstraniti nepotrebne decimalne številke. Vendar je to razprava za kdaj drugič.
Če je zahtevanih več kot eno Fibonaccijevo število, mora koda enkrat poklicati formulo za vsak ustrezen indeks n, ki temelji na ničli.
Zaključek
Fibonaccijeva števila so določeno zaporedje pozitivnih celih števil, ki se začnejo z 0. Cela števila so pozitivna cela števila. Torej je Fibonaccijevo število določeno zaporedje celih ali naravnih števil, ki se začnejo z 0. V tem zaporedju sta prvi dve števili 0 in 1, v tem vrstnem redu. Ti prvi dve številki sta samo definirani kot taki. Preostale številke se razvijejo od tam z dodajanjem neposredno prejšnjih dveh številk.
Po izdelavi prvih dveh Fibonaccijevih števil, da bi izdelali preostala Fibonaccijeva števila, da bi na koncu dobili skupaj n števil, je treba uporabiti for-zanko z izjavo:
currNo = A[i – 1] + A[i – 2];
To doda zadnji dve Fibonaccijevi števili, da dobimo trenutno Fibonaccijevo število.
Če imate indeks, ki temelji na ničli, uporabite formulo za ustrezno Fibonaccijevo število:
