Fibonačio skaičių reikšmė
Fibonačio skaičiai yra tam tikra teigiamų sveikųjų skaičių seka, prasidedanti nuo 0. Sveiki skaičiai yra teigiami sveikieji skaičiai. Taigi, Fibonačio skaičius yra tam tikra sveikųjų arba natūraliųjų skaičių seka, prasidedanti nuo 0. Šioje sekoje pirmieji du skaičiai yra 0 ir 1 tokia tvarka. Likę skaičiai sukuriami sudedant du ankstesnius skaičius. Pirmieji dvylika Fibonačio skaičių gaunami taip:
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
Kitaip tariant, pirmieji dvylika Fibonačio skaičių yra:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Žinoma, tryliktas skaičius būtų: 144 = 55 + 89. Galima įsivaizduoti, kad Fibonačio skaičiai yra masyve, pavyzdžiui:
| 0 | 1 | 1 | du | 3 | 5 | 8 | 13 | dvidešimt vienas | 3. 4 | 55 | 89 |
Masyvas turi indeksus. Toliau pateiktoje lentelėje antroje eilutėje rodomi atitinkami nuliu pagrįsti masyvo Fibonačio skaičių indeksai:
| 0 | 1 | 1 | du | 3 | 5 | 8 | 13 | dvidešimt vienas | 3. 4 | 55 | 89 |
| 0 | 1 | du | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienuolika |
Su nuliniais indeksais, jei yra dvylika elementų, paskutinis indeksas yra 11.
Fibonačio skaičiai gali būti sukurti per O (n) laiką arba per O (1) laiką. Šiose laiko sudėtingumo išraiškose n reiškia n pagrindinių operacijų, o 1 reiškia 1 pagrindinę operaciją. Su O(n) sukuriama n Fibonačio skaičių, pradedant nuo 0. Esant O(1), iš atitinkamo indekso gaunamas vienas Fibonačio skaičius. Štai kodėl O(1) atlieka tik vieną pagrindinę operaciją, o ne n pagrindinių operacijų.
Šio straipsnio tikslas yra paaiškinti, kaip sukurti Fibonacci skaičius bet kuriuo atveju naudojant JavaScript, kuris šiandien iš tikrųjų yra ECMAScript.
Kodavimo aplinka
Aplinka node.js nebus naudojama, kaip skaitytojas galėjo tikėtis. Vietoj to, naršyklė bus naudojama kodui interpretuoti ir rezultatams rodyti. Scenarijus (kodas) turi būti parašytas teksto rengyklės faile, kuris turi būti išsaugotas su plėtiniu „.html“. Scenarijus turi turėti minimalų kodą:
DOCTYPE HTML >< html >
< galva >
< titulą > Fibonačio skaičiai su JavaScript titulą >
galva >
< kūnas >
< scenarijaus tipas = 'tekstas/ekmascript'as >
scenarijus >
kūnas >
html >
Tai apytikslis minimalus kodas, kurio reikia tinklalapiui. Visas šio straipsnio kodavimas yra tarp žymų .
Norėdami paleisti parašytą (pridėtą) kodą, tiesiog dukart spustelėkite failo pavadinimo piktogramą ir kompiuterio naršyklė ją atidarys.
Fibonačio skaičiaus apibrėžimas
Yra matematinis Fibonačio skaičiaus apibrėžimas. Jis apibrėžiamas taip:
Kur Fn yra Fibonačio skaičius, atitinkantis nulinį indeksą, n.
Pirmieji du skaičiai: 0 ir 1 yra iš anksto deklaruoti tokia tvarka. Paskutinė šios funkcijos eilutė rodo, kaip likusieji skaičiai atsiranda iš pirmųjų dviejų skaičių jų tvarka.
Šis apibrėžimas taip pat yra viena iš Fibonačio skaičiaus formulių.
Fibonačio skaičių generavimas per O(n) laiką
Jei n yra 1, tada tik 0 būtų rodomas kaip Fibonačio skaičius. Jei n yra 2, tada 0 ir 1 būtų rodomi kaip Fibonačio skaičiai tokia tvarka. Jei n yra 3, tada 0, 1 ir 1 būtų rodomi kaip Fibonačio skaičiai tokia tvarka. Jei n yra 4, tada 0, 1, 1 ir 2 būtų rodomi kaip Fibonačio skaičiai tokia tvarka. Jei n yra 5, tada 0, 1, 1, 2 ir 3 būtų rodomi kaip Fibonačio skaičiai tokia tvarka. Jei n yra 6, tada 0, 1, 1, 2, 3 ir 5 būtų rodomi kaip Fibonačio skaičiai, tokia tvarka ir pan.
ECMAscript funkcija pirmiesiems n Fibonačio sveikiesiems skaičiams (skaičiams) generuoti yra:
< scenarijaus tipas = 'tekstas/ekmascript'as >funkcija Fibonacci ( A ) {
n = A. ilgio ;
jeigu ( n > 0 )
A [ 0 ] = 0 ;
jeigu ( n > 1 )
A [ 1 ] = 1 ;
dėl ( i = du ; i < n ; i ++ ) { //n=0 ir n=2 buvo atsižvelgta
CurrNr = A [ i - 1 ] + A [ i - du ] ;
A [ i ] = CurrNr ;
}
}
Uždarymo scenarijaus žyma nerodoma. Funkcija gauna masyvą. Pirmieji du Fibonačio skaičiai priskiriami jų vietoje. For-ciklas kartojasi nuo nulinio indekso, 2 iki šiek tiek žemiau n. Svarbiausias teiginys for-kilpoje yra:
currNo = A[i – 1] + A[i – 2];
Taip masyve pridedami du ankstesni skaičiai, kad būtų dabartinis skaičius. Kai funkcija fibonačio () baigia vykdyti, visi masyvo elementai yra pirmieji n Fibonačio skaičiai. Tinkamas kodas norint iškviesti fibonačio () funkciją ir rodyti Fibonačio skaičius:
N = 12 ;arr = naujas Masyvas ( N ) ;
Fibonacci ( arr ) ;
dėl ( i = 0 ; i < N ; i ++ )
dokumentas. rašyti ( arr [ i ] + '' ) ;
dokumentas. rašyti ( '
' ) ;
scenarijus >
Šis kodas rodo uždarymo scenarijaus žymą. Kodas įvedamas po aukščiau nurodytu kodu. Tinklalapyje rodoma išvestis:
0 1 1 2 3 5 8 13 21 34 55 89
kaip tikėtasi.
Vieno Fibonačio skaičiaus generavimas per O(1) laiką
O(1) yra pastovus laikas. Tai reiškia vieną pagrindinę operaciją. Kita matematinė formulė Fibonačio skaičiui gauti yra:
Atkreipkite dėmesį, kad dešinėje lygties pusėje ne kvadratinė šaknis iš 5 yra pakelta į laipsnį n; tai skliausteliuose esanti išraiška pakeliama iki laipsnio n. Yra dvi tokios išraiškos.
Jei n yra 0, Fibn būtų 0. Jei n yra 1, Fibn būtų 1. Jei n yra 2, Fibn būtų 1. Jei n yra 3, Fibn būtų 2. Jei n yra 4, Fibn būtų 3 – ir taip toliau. Skaitytojas gali patikrinti šią formulę matematiškai, pakeisdamas n skirtingomis reikšmėmis ir įvertindamas. n šioje formulėje yra nulinis indeksas. Rezultatas yra atitinkamas Fibonačio skaičius.
Šios formulės ECMAScript (JavaScript) kodas yra:
< scenarijaus tipas = 'tekstas/ekmascript'as >funkcija fibNr ( n ) {
FibN = ( Matematika . pow ( ( 1 + Matematika . kv ( 5 ) ) / du , n ) - Matematika . pow ( ( 1 - Matematika . kv ( 5 ) ) / du , n ) ) / Matematika . kv ( 5 ) ;
grąžinti FibN ;
}
Uždarymo scenarijaus žyma nerodoma. Atkreipkite dėmesį, kaip buvo naudojamos galios (pow) ir kvadratinės šaknies (sqrt) iš anksto nustatytos funkcijos. ECMAScript (JavaScript) matematikos modulio importuoti nereikia. Funkcija fibNo() formulę įgyvendina tiesiogiai. Tinkamas iškvietimas ir funkcijos fibNo() rodymas tinklalapyje yra:
N = vienuolika ;teisingai = fibNr ( N ) ;
dokumentas. rašyti ( teisingai ) ;
scenarijus >
Kodas rodo uždarymo scenarijaus žymą. Išvestis yra:
89.00000000000003
Iš atsakymo galima pašalinti nereikalingus dešimtainius skaitmenis. Tačiau tai bus diskusija kitam kartui.
Jei reikia daugiau nei vieno Fibonačio skaičiaus, kodas turi vieną kartą iškviesti formulę kiekvienam nuliu pagrįstam atitinkamam n indeksui.
Išvada
Fibonačio skaičiai yra tam tikra teigiamų sveikųjų skaičių seka, prasidedanti nuo 0. Sveiki skaičiai yra teigiami sveikieji skaičiai. Taigi, Fibonačio skaičius yra tam tikra sveikųjų arba natūraliųjų skaičių seka, prasidedanti nuo 0. Šioje sekoje pirmieji du skaičiai yra 0 ir 1 tokia tvarka. Šie pirmieji du skaičiai tiesiog apibrėžiami kaip tokie. Likę skaičiai sukuriami iš ten pridedant du ankstesnius skaičius.
Sukūrus pirmuosius du Fibonačio skaičius, norint gauti likusius Fibonačio skaičius ir gauti iš viso n skaičių, su teiginiu reikia naudoti for-ciklą:
currNo = A[i – 1] + A[i – 2];
Tai prideda du paskutinius Fibonačio skaičius, kad būtų dabartinis Fibonačio skaičius.
Kai pateikiamas nulinis indeksas, kad gautumėte atitinkamą Fibonačio skaičių, naudokite formulę:
