Význam Fibonacciho čísel
Fibonacciho čísla jsou konkrétní posloupnost kladných celých čísel, začínající od 0. Celá čísla jsou kladná celá čísla. Fibonacciho číslo je tedy konkrétní posloupnost celých čísel nebo přirozených čísel, začínající od 0. V této posloupnosti jsou první dvě čísla 0 a 1 v tomto pořadí. Zbývající čísla se odtud vyvinou přidáním předchozích dvou čísel. Prvních dvanáct Fibonacciho čísel se získá 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
Jinými slovy, prvních dvanáct Fibonacciho čísel je:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Samozřejmě, třinácté číslo by bylo: 144 = 55 + 89. Fibonacciho čísla si lze představit jako v poli, například takto:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvacet jedna | 3. 4 | 55 | 89 |
Pole má indexy. V následující tabulce druhý řádek ukazuje odpovídající indexy založené na nule pro Fibonacciho čísla v poli:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvacet jedna | 3. 4 | 55 | 89 |
| 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedenáct |
Pokud je u indexů založených na nule dvanáct prvků, pak je poslední index 11.
Fibonacciho čísla lze vytvořit v čase O(n) nebo v čase O(1). V těchto výrazech časové složitosti n znamená n hlavních operací a 1 znamená 1 hlavní operaci. S O(n) se vytvoří n Fibonacciho čísel, počínaje 0. S O(1) se z odpovídajícího indexu vytvoří jedno Fibonacciho číslo. To je důvod, proč O(1) trvá pouze jednu hlavní operaci místo n hlavních operací.
Cílem tohoto článku je vysvětlit, jak vytvářet Fibonacciho čísla v obou směrech pomocí JavaScriptu, což je dnes vlastně ECMAScript.
Kódovací prostředí
Prostředí node.js nebude použito, jak mohl čtenář předvídat. Místo toho bude pro interpretaci kódu a zobrazení výsledků použit prohlížeč. Skript (kód) by měl být napsán v souboru textového editoru, který by měl být uložen s příponou „.html“. Skript by měl mít minimálně kód:
DOCTYPE HTML >< html >
< hlava >
< titul > Fibonacciho čísla s JavaScriptem titul >
hlava >
< tělo >
< typ skriptu = 'text/ecmascript' >
skript >
tělo >
html >
Toto je přibližný minimální kód, který webová stránka potřebuje. Veškeré kódování tohoto článku se nachází mezi značkami .
Chcete-li spustit napsaný (přidaný) kód, stačí dvakrát kliknout na ikonu názvu souboru a prohlížeč počítače jej otevře.
Definice Fibonacciho čísla
Pro Fibonacciho číslo existuje matematická definice. Je definován následovně:
Kde Fn je Fibonacciho číslo odpovídající indexu založenému na nule, n.
První dvě čísla: 0 a 1 jsou předem deklarována v tomto pořadí. Poslední řádek této funkce ukazuje, jak zbytek čísel pochází z prvních dvou čísel v jejich pořadí.
Tato definice je také jedním ze vzorců pro Fibonacciho číslo.
Vytváření Fibonacciho čísel v O(n) čase
Pokud n je 1, pak by se jako Fibonacciho číslo zobrazila pouze 0. Pokud n je 2, pak 0 a 1 budou zobrazeny jako Fibonacciho čísla v tomto pořadí. Pokud n je 3, pak 0, 1 a 1 budou zobrazeny jako Fibonacciho čísla v tomto pořadí. Pokud n je 4, pak 0, 1, 1 a 2 budou zobrazeny jako Fibonacciho čísla v tomto pořadí. Pokud n je 5, pak 0, 1, 1, 2 a 3 budou zobrazeny jako Fibonacciho čísla v tomto pořadí. Pokud n je 6, pak 0, 1, 1, 2, 3 a 5 budou zobrazeny jako Fibonacciho čísla v tomto pořadí – a tak dále.
Funkce ECMAscript pro generování prvních n Fibonacciho celých čísel (čísel) je:
< typ skriptu = 'text/ecmascript' >funkce fibonacci ( A ) {
n = A. délka ;
-li ( n > 0 )
A [ 0 ] = 0 ;
-li ( n > 1 )
A [ 1 ] = 1 ;
pro ( i = dva ; i < n ; i ++ ) { //n=0 a n=2
currNo = A [ i - 1 ] + A [ i - dva ] ;
A [ i ] = currNo ;
}
}
Značka závěrečného skriptu nebyla zobrazena. Funkce přijímá pole. První dvě Fibonacciho čísla jsou přiřazena na jejich pozici. For-loop iteruje od indexu založeného na nule, 2 až těsně pod n. Nejdůležitější příkaz ve smyčce for je:
currNo = A[i – 1] + A[i – 2];
Tím se přidají bezprostředně předchozí dvě čísla v poli, aby se získalo aktuální číslo. V době, kdy funkce fibonacci() dokončí provádění, jsou všechny prvky pole prvních n Fibonacciho čísel. Vhodný kód pro volání funkce fibonacci() a zobrazení Fibonacciho čísel je:
N = 12 ;arr = Nový Pole ( N ) ;
fibonacci ( arr ) ;
pro ( i = 0 ; i < N ; i ++ )
dokument. napsat ( arr [ i ] + ' ' ) ;
dokument. napsat ( '
' ) ;
skript >
Tento kód zobrazuje značku závěrečného skriptu. Kód je napsán pod výše uvedeným kódem. Výstup zobrazený na webové stránce je:
0 1 1 2 3 5 8 13 21 34 55 89
podle očekávání.
Vytváření jednoho Fibonacciho čísla za O(1) čas
O(1) je konstantní čas. Vztahuje se k jedné hlavní operaci. Další matematický vzorec pro vytvoření Fibonacciho čísla je:
Všimněte si, že na pravé straně rovnice to není druhá odmocnina z 5, která je umocněna n; právě výraz v závorce je umocněn n. Existují dva takové výrazy.
Pokud n je 0, Fibn by bylo 0. Pokud n je 1, Fibn by bylo 1. Pokud n je 2, Fibn by bylo 1. Pokud n je 3, Fibn by bylo 2. Pokud n je 4, Fibn by bylo 3 – a tak dále. Čtenář si může tento vzorec ověřit matematicky dosazením různých hodnot za n a vyhodnocením. n je v tomto vzorci index založený na nule. Výsledkem je odpovídající Fibonacciho číslo.
ECMAScript (JavaScript) kód pro tento vzorec je:
< typ skriptu = 'text/ecmascript' >funkce fibNo ( n ) {
FibN = ( Matematika . pow ( ( 1 + Matematika . sqrt ( 5 ) ) / dva , n ) - Matematika . pow ( ( 1 - Matematika . sqrt ( 5 ) ) / dva , n ) ) / Matematika . sqrt ( 5 ) ;
vrátit se FibN ;
}
Značka závěrečného skriptu nebyla zobrazena. Všimněte si, jak byly použity předdefinované funkce mocniny (pow) a druhé odmocniny (sqrt). V ECMAScript (JavaScript) není nutné importovat modul Math. Funkce fibNo() implementuje vzorec přímo. Vhodné volání a zobrazení funkce fibNo() na webové stránce jsou:
N = jedenáct ;že jo = fibNo ( N ) ;
dokument. napsat ( že jo ) ;
skript >
Kód zobrazuje značku závěrečného skriptu. Výstup je:
89.00000000000003
Z odpovědi je možné odstranit nepotřebné desetinné číslice. To je však diskuse na jindy.
Je-li požadováno více než jedno Fibonacciho číslo, musí kód volat vzorec jednou pro každý odpovídající n index založený na nule.
Závěr
Fibonacciho čísla jsou konkrétní posloupnost kladných celých čísel, začínající od 0. Celá čísla jsou kladná celá čísla. Fibonacciho číslo je tedy konkrétní posloupnost celých čísel nebo přirozených čísel, začínající od 0. V této posloupnosti jsou první dvě čísla 0 a 1 v tomto pořadí. Tato první dvě čísla jsou definována jako taková. Zbývající čísla se odtud vyvinou přidáním bezprostředně předchozích dvou čísel.
Po vytvoření prvních dvou Fibonacciho čísel, aby se vytvořil zbytek Fibonacciho čísel, abychom skončili s celkem n čísly, je třeba použít for-loop s příkazem:
currNo = A[i – 1] + A[i – 2];
Tím se sečtou bezprostředně poslední dvě Fibonacciho čísla a získáte aktuální Fibonacciho číslo.
Když dostanete index založený na nule, abyste získali odpovídající Fibonacciho číslo, použijte vzorec:
