Význam Fibonacciho čísel
Fibonacciho čísla sú konkrétnou postupnosťou kladných celých čísel, ktoré začínajú od 0. Celé čísla sú kladné celé čísla. Takže Fibonacciho číslo je konkrétna postupnosť celých čísel alebo prirodzených čísel, začínajúca od 0. V tejto postupnosti sú prvé dve čísla 0 a 1 v tomto poradí. Odtiaľ sa odvíjajú ostatné čísla pridaním predchádzajúcich dvoch čísel. Prvých dvanásť Fibonacciho čísel sa získa takto:
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
Inými slovami, prvých dvanásť Fibonacciho čísel je:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Samozrejme, trináste číslo by bolo: 144 = 55 + 89. Fibonacciho čísla si možno predstaviť v poli, napríklad takto:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvadsaťjeden | 3. 4 | 55 | 89 |
Pole má indexy. V nasledujúcej tabuľke druhý riadok zobrazuje zodpovedajúce indexy založené na nule pre Fibonacciho čísla v poli:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvadsaťjeden | 3. 4 | 55 | 89 |
| 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedenásť |
Pri indexoch založených na nule, ak existuje dvanásť prvkov, potom posledný index je 11.
Fibonacciho čísla môžu byť produkované v O(n) čase alebo v O(1) čase. V týchto výrazoch časovej zložitosti n znamená n hlavných operácií a 1 znamená 1 hlavnú operáciu. S O(n) sa vytvorí n Fibonacciho čísel, začínajúc od 0. S O(1) sa zo zodpovedajúceho indexu vytvorí jedno Fibonacciho číslo. To je dôvod, prečo O(1) vyžaduje iba jednu hlavnú operáciu namiesto n hlavných operácií.
Cieľom tohto článku je vysvetliť, ako vytvárať Fibonacciho čísla v oboch smeroch pomocou JavaScriptu, čo je dnes vlastne ECMAScript.
Kódovacie prostredie
Prostredie node.js sa nepoužije, ako by čitateľ mohol očakávať. Namiesto toho sa na interpretáciu kódu a zobrazenie výsledkov použije prehliadač. Skript (kód) by mal byť napísaný v súbore textového editora, ktorý by mal byť uložený s príponou „.html“. Skript by mal mať minimálny kód:
DOCTYPE HTML >< html >
< hlavu >
< titul > Fibonacciho čísla s JavaScriptom titul >
hlavu >
< telo >
< typ skriptu = 'text/ecmascript' >
skript >
telo >
html >
Toto je približný minimálny kód, ktorý webová stránka potrebuje. Všetky kódy pre tento článok sú medzi značkami .
Ak chcete spustiť napísaný (pridaný) kód, stačí dvakrát kliknúť na ikonu názvu súboru a prehliadač počítača ho otvorí.
Definícia Fibonacciho čísla
Existuje matematická definícia Fibonacciho čísla. Definuje sa takto:
Kde Fn je Fibonacciho číslo zodpovedajúce indexu založenému na nule, n.
Prvé dve čísla: 0 a 1 sú vopred uvedené v tomto poradí. Posledný riadok tejto funkcie ukazuje, ako zvyšok čísel pochádza z prvých dvoch čísel v ich poradí.
Táto definícia je tiež jedným zo vzorcov pre Fibonacciho číslo.
Vytváranie Fibonacciho čísel v O(n) čase
Ak n je 1, potom sa ako Fibonacciho číslo zobrazí iba 0. Ak n je 2, potom 0 a 1 budú zobrazené ako Fibonacciho čísla v tomto poradí. Ak n je 3, potom 0, 1 a 1 budú zobrazené ako Fibonacciho čísla v tomto poradí. Ak n je 4, potom 0, 1, 1 a 2 sa zobrazia ako Fibonacciho čísla v tomto poradí. Ak n je 5, potom 0, 1, 1, 2 a 3 sa zobrazia ako Fibonacciho čísla v tomto poradí. Ak n je 6, potom 0, 1, 1, 2, 3 a 5 sa zobrazia ako Fibonacciho čísla v tomto poradí – a tak ďalej.
Funkcia ECMAscript na generovanie prvých n Fibonacciho celých čísel (čísel) je:
< typ skriptu = 'text/ecmascript' >funkciu fibonacciho ( A ) {
n = A. dĺžka ;
ak ( n > 0 )
A [ 0 ] = 0 ;
ak ( n > 1 )
A [ 1 ] = 1 ;
pre ( i = dva ; i < n ; i ++ ) { //n=0 a n=2
currNo = A [ i - 1 ] + A [ i - dva ] ;
A [ i ] = currNo ;
}
}
Značka záverečného skriptu sa nezobrazila. Funkcia prijíma pole. Prvé dve Fibonacciho čísla sú priradené na ich pozícii. Slučka for iteruje od indexu založeného na nule, 2 až tesne pod n. Najdôležitejšie vyhlásenie v slučke for je:
currNo = A[i – 1] + A[i – 2];
Toto pridá bezprostredne predchádzajúce dve čísla do poľa, aby sa získalo aktuálne číslo. V čase, keď funkcia fibonacci() skončí vykonávanie, všetky prvky poľa sú prvých n Fibonacciho čísel. Vhodný kód na volanie funkcie Fibonacci() a zobrazenie Fibonacciho čísel je:
N = 12 ;arr = Nový Pole ( N ) ;
fibonacciho ( arr ) ;
pre ( i = 0 ; i < N ; i ++ )
dokument. písať ( arr [ i ] + ' ' ) ;
dokument. písať ( '
' ) ;
skript >
Tento kód zobrazuje značku záverečného skriptu. Kód je napísaný pod vyššie uvedeným kódom. Výstup zobrazený na webovej stránke je:
0 1 1 2 3 5 8 13 21 34 55 89
podľa očakávania.
Vytvorenie jedného Fibonacciho čísla za O(1) čas
O(1) je konštantný čas. Vzťahuje sa na jednu hlavnú operáciu. Ďalší matematický vzorec na vytvorenie Fibonacciho čísla je:
Všimnite si, že na pravej strane rovnice to nie je druhá odmocnina z 5, ktorá je umocnená na n; práve výraz v zátvorke je umocnený n. Existujú dva takéto výrazy.
Ak n je 0, Fibn by bolo 0. Ak n je 1, Fibn by bolo 1. Ak n je 2, Fibn by bolo 1. Ak n je 3, Fibn by bolo 2. Ak n je 4, Fibn by bolo 3 – a tak ďalej. Čitateľ si môže tento vzorec overiť matematicky dosadením rôznych hodnôt za n a vyhodnotením. n je v tomto vzorci index založený na nule. Výsledkom je zodpovedajúce Fibonacciho číslo.
Kód ECMAScript (JavaScript) pre tento vzorec je:
< typ skriptu = 'text/ecmascript' >funkciu fibNo ( n ) {
FibN = ( Matematika . pow ( ( 1 + Matematika . sqrt ( 5 ) ) / dva , n ) - Matematika . pow ( ( 1 - Matematika . sqrt ( 5 ) ) / dva , n ) ) / Matematika . sqrt ( 5 ) ;
vrátiť FibN ;
}
Značka záverečného skriptu sa nezobrazila. Všimnite si, ako sa použili preddefinované funkcie sily (pow) a druhej odmocniny (sqrt). V ECMAScript (JavaScript) sa modul Math nemusí importovať. Funkcia fibNo() implementuje vzorec priamo. Vhodné volanie a zobrazenie funkcie fibNo() na webovej stránke sú:
N = jedenásť ;správny = fibNo ( N ) ;
dokument. písať ( správny ) ;
skript >
Kód zobrazuje značku záverečného skriptu. Výstupom je:
89,00000000000003
Z odpovede je možné odstrániť nepotrebné desatinné číslice. To je však diskusia na inokedy.
Ak sa vyžaduje viac ako jedno Fibonacciho číslo, kód musí volať vzorec raz pre každý zodpovedajúci n index založený na nule.
Záver
Fibonacciho čísla sú konkrétnou postupnosťou kladných celých čísel, ktoré začínajú od 0. Celé čísla sú kladné celé čísla. Takže Fibonacciho číslo je konkrétna postupnosť celých čísel alebo prirodzených čísel, začínajúca od 0. V tejto postupnosti sú prvé dve čísla 0 a 1 v tomto poradí. Tieto prvé dve čísla sú definované ako také. Odtiaľ sa odvíjajú ostatné čísla pridaním bezprostredne predchádzajúcich dvoch čísel.
Po vytvorení prvých dvoch Fibonacciho čísel, aby sa vytvorili zvyšné Fibonacciho čísla, aby sme skončili s celkovým počtom n čísel, sa musí použiť slučka for s príkazom:
currNo = A[i – 1] + A[i – 2];
Týmto sa sčítajú bezprostredné posledné dve Fibonacciho čísla, aby sa získalo aktuálne Fibonacciho číslo.
Keď dostanete index založený na nule, aby ste získali zodpovedajúce Fibonacciho číslo, použite vzorec:
