Betydelsen av Fibonacci-tal
Fibonacci-tal är en speciell sekvens av positiva heltal, med början från 0. Hela tal är positiva heltal. Så, ett Fibonacci-tal är en speciell sekvens av heltal eller naturliga tal, som börjar från 0. I denna sekvens är de två första talen 0 och 1, i den ordningen. Resten av siffrorna utvecklas därifrån genom att lägga till de två föregående talen. De första tolv Fibonacci-talen erhålls enligt följande:
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
Med andra ord är de första tolv Fibonacci-talen:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Naturligtvis skulle det trettonde talet vara: 144 = 55 + 89. Fibonacci-tal kan föreställas vara i en array, så här:
| 0 | 1 | 1 | två | 3 | 5 | 8 | 13 | tjugoett | 3. 4 | 55 | 89 |
En array har index. I följande tabell visar den andra raden motsvarande nollbaserade index för Fibonacci-talen i en array:
| 0 | 1 | 1 | två | 3 | 5 | 8 | 13 | tjugoett | 3. 4 | 55 | 89 |
| 0 | 1 | två | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elva |
Med nollbaserade index, om det finns tolv element, är det sista indexet 11.
Fibonacci-tal kan produceras i O(n)-tid eller i O(1)-tid. I dessa tidskomplexitetsuttryck betyder n n huvudoperationer och 1 betyder 1 huvudoperation. Med O(n) produceras n Fibonacci-tal, med början från 0. Med O(1) produceras ett Fibonacci-tal från motsvarande index. Det är därför O(1) bara tar en huvudoperation istället för n huvudoperationer.
Syftet med den här artikeln är att förklara hur man producerar Fibonacci-nummer, oavsett hur, med hjälp av JavaScript, som faktiskt är ECMAScript idag.
Kodningsmiljö
Miljön node.js kommer inte att användas som läsaren kan ha förutsett. Istället kommer webbläsaren att användas för tolkning av koden och visning av resultaten. Skriptet (koden) ska skrivas i en textredigeringsfil, som ska sparas med tillägget '.html.' Skriptet bör ha som minsta kod:
DOCTYPE HTML >< html >
< huvud >
< titel > Fibonacci-nummer med JavaScript titel >
huvud >
< kropp >
< skripttyp = 'text/ecmascript' >
manus >
kropp >
html >
Detta är en ungefärlig minimikod som en webbsida behöver. All kodning för den här artikeln går mellan taggarna .
För att köra koden skriven (tillagd), dubbelklicka bara på ikonen för filnamnet, så öppnas den av datorns webbläsare.
Definition av ett Fibonacci-nummer
Det finns en matematisk definition för ett Fibonacci-tal. Den definieras enligt följande:
Där Fn är ett Fibonacci-tal som motsvarar ett nollbaserat index, n.
De två första siffrorna: 0 och 1, är fördeklarerade, i den ordningen. Den sista raden i denna funktion visar hur resten av siffrorna kommer från de två första talen i deras ordning.
Denna definition är också en av formlerna för Fibonacci-talet.
Producera Fibonacci-tal i O(n)-tid
Om n är 1, skulle endast 0 visas som ett Fibonacci-tal. Om n är 2, så skulle 0 och 1 visas som Fibonacci-tal, i den ordningen. Om n är 3, så skulle 0, 1 och 1 visas som Fibonacci-tal i den ordningen. Om n är 4, så skulle 0, 1, 1 och 2 visas som Fibonacci-tal, i den ordningen. Om n är 5, så skulle 0, 1, 1, 2 och 3 visas som Fibonacci-tal, i den ordningen. Om n är 6, så skulle 0, 1, 1, 2, 3 och 5 visas som Fibonacci-tal, i den ordningen – och så vidare.
ECMAscript-funktionen för att generera de första n Fibonacci-heltalen (tal) är:
< skripttyp = 'text/ecmascript' >fungera fibonacci ( A ) {
n = A. längd ;
om ( n > 0 )
A [ 0 ] = 0 ;
om ( n > 1 )
A [ 1 ] = 1 ;
för ( i = två ; i < n ; i ++ ) { //n=0 och n=2 har beaktats
currNo = A [ i - 1 ] + A [ i - två ] ;
A [ i ] = currNo ;
}
}
Den avslutande skripttaggen har inte visats. Funktionen tar emot en array. De två första Fibonacci-numren tilldelas vid sin position. For-loopen itererar från det nollbaserade indexet, 2 till strax under n. Det viktigaste uttalandet i for-loopen är:
currNo = A[i – 1] + A[i – 2];
Detta lägger till de omedelbart föregående två numren i arrayen för att få det aktuella numret. När fibonacci()-funktionen avslutas, är alla element i arrayen de första n Fibonacci-talen. En lämplig kod för att anropa fibonacci()-funktionen och visa Fibonacci-talen är:
N = 12 ;arr = ny Array ( N ) ;
fibonacci ( arr ) ;
för ( i = 0 ; i < N ; i ++ )
dokumentera. skriva ( arr [ i ] + ' ' ) ;
dokumentera. skriva ( '
' ) ;
manus >
Den här koden visar den avslutande skripttaggen. Koden skrivs in under ovanstående kod. Utdata som visas på webbsidan är:
0 1 1 2 3 5 8 13 21 34 55 89
som förväntat.
Producerar ett Fibonacci-nummer på O(1)-tid
O(1) är konstant tid. Det hänvisar till en huvudoperation. En annan matematisk formel för att producera ett Fibonacci-tal är:
Observera att på höger sida av ekvationen är det inte kvadratroten ur 5 som höjs till potensen n; det är uttrycket inom parentes som höjs till potensen n. Det finns två sådana uttryck.
Om n är 0, skulle Fibn vara 0. Om n är 1, skulle Fibn vara 1. Om n är 2, skulle Fibn vara 1. Om n är 3, skulle Fibn vara 2. Om n är 4, skulle Fibn vara 3 – och så vidare. Läsaren kan verifiera denna formel matematiskt genom att ersätta n med olika värden och utvärdera. n är ett nollbaserat index i denna formel. Resultatet är motsvarande Fibonacci-tal.
ECMAScript (JavaScript)-koden för denna formel är:
< skripttyp = 'text/ecmascript' >fungera fibNr ( n ) {
FibN = ( Matematik . pow ( ( 1 + Matematik . sqrt ( 5 ) ) / två , n ) - Matematik . pow ( ( 1 - Matematik . sqrt ( 5 ) ) / två , n ) ) / Matematik . sqrt ( 5 ) ;
lämna tillbaka FibN ;
}
Den avslutande skripttaggen har inte visats. Notera hur de fördefinierade funktionerna power (pow) och kvadratroten (sqrt) har använts. I ECMAScript (JavaScript) behöver Math-modulen inte importeras. Funktionen fibNo() implementerar formeln direkt. Ett lämpligt anrop och display för fibNo()-funktionen på webbsidan är:
N = elva ;höger = fibNr ( N ) ;
dokumentera. skriva ( höger ) ;
manus >
Koden visar den avslutande skripttaggen. Utgången är:
89,00000000000003
Det är möjligt att ta bort de onödiga decimalsiffrorna från svaret. Det är dock en diskussion för en annan gång.
Om mer än ett Fibonacci-nummer krävs, måste koden anropa formeln en gång för varje nollbaserat motsvarande n-index.
Slutsats
Fibonacci-tal är en speciell sekvens av positiva heltal, med början från 0. Hela tal är positiva heltal. Så, ett Fibonacci-tal är en speciell sekvens av heltal eller naturliga tal, som börjar från 0. I denna sekvens är de två första talen 0 och 1, i den ordningen. Dessa två första siffror är bara definierade som sådana. Resten av siffrorna utvecklas därifrån genom att lägga till de två närmast föregående talen.
Efter att ha producerat de två första Fibonacci-talen, för att producera resten av Fibonacci-talen, för att sluta med totalt n tal, måste en for-loop användas med påståendet:
currNo = A[i – 1] + A[i – 2];
Detta lägger till de två sista Fibonacci-numren för att få det aktuella Fibonacci-numret.
När du får ett nollbaserat index, för att ha motsvarande Fibonacci-nummer, använd formeln:
