Betekenis van Fibonacci-getallen
Fibonacci-getallen zijn een bepaalde reeks positieve gehele getallen, beginnend bij 0. Gehele getallen zijn positieve gehele getallen. Een Fibonacci-getal is dus een bepaalde reeks gehele getallen of natuurlijke getallen, beginnend bij 0. In deze reeks zijn de eerste twee getallen 0 en 1, in die volgorde. De rest van de nummers worden van daaruit ontwikkeld door de vorige twee nummers op te tellen. De eerste twaalf Fibonacci-getallen worden als volgt verkregen:
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
Met andere woorden, de eerste twaalf Fibonacci-getallen zijn:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Natuurlijk zou het dertiende getal zijn: 144 = 55 + 89. Men kan zich voorstellen dat Fibonacci-getallen in een array staan, zoals:
| 0 | 1 | 1 | twee | 3 | 5 | 8 | 13 | eenentwintig | 3. 4 | 55 | 89 |
Een array heeft indexen. In de volgende tabel toont de tweede rij de overeenkomstige op nul gebaseerde indexen voor de Fibonacci-getallen in een array:
| 0 | 1 | 1 | twee | 3 | 5 | 8 | 13 | eenentwintig | 3. 4 | 55 | 89 |
| 0 | 1 | twee | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf |
Bij op nul gebaseerde indexen, als er twaalf elementen zijn, is de laatste index 11.
Fibonacci-getallen kunnen worden geproduceerd in O(n)-tijd of in O(1)-tijd. In deze uitdrukkingen van tijdcomplexiteit betekent n n hoofdbewerkingen en 1 betekent 1 hoofdbewerking. Met O(n) worden n Fibonacci-getallen geproduceerd, beginnend bij 0. Met O(1) wordt één Fibonacci-getal geproduceerd uit de overeenkomstige index. Daarom voert O(1) slechts één hoofdbewerking uit in plaats van n hoofdbewerkingen.
Het doel van dit artikel is om uit te leggen hoe je Fibonacci-getallen kunt maken, hoe dan ook, met JavaScript, wat tegenwoordig ECMAScript is.
Codeeromgeving
De node.js-omgeving zal niet worden gebruikt zoals de lezer misschien had verwacht. In plaats daarvan wordt de browser gebruikt voor de interpretatie van de code en het weergeven van de resultaten. Het script (code) moet worden geschreven in een teksteditorbestand, dat moet worden opgeslagen met de extensie '.html'. Het script moet als minimum code hebben:
DOCTYPE HTML >< html >
< hoofd >
< titel > Fibonacci-nummers met JavaScript titel >
hoofd >
< lichaam >
< scripttype = 'tekst/ecmascript' >
script >
lichaam >
html >
Dit is een geschatte minimale code die een webpagina nodig heeft. Alle codering voor dit artikel zit tussen de tags, .
Om de geschreven (toegevoegde) code uit te voeren, dubbelklikt u gewoon op het pictogram van de bestandsnaam en de browser van de computer zal deze openen.
Definitie van een Fibonacci-getal
Er is een wiskundige definitie voor een Fibonacci-getal. Het is als volgt gedefinieerd:
Waar Fn een Fibonacci-getal is dat overeenkomt met een op nul gebaseerde index, n.
De eerste twee cijfers: 0 en 1, zijn vooraf aangegeven, in die volgorde. De laatste regel van deze functie laat zien hoe de rest van de nummers afkomstig zijn van de eerste twee nummers in hun volgorde.
Deze definitie is ook een van de formules voor het Fibonacci-getal.
Fibonacci-getallen produceren in O(n)-tijd
Als n 1 is, wordt alleen 0 weergegeven als een Fibonacci-getal. Als n 2 is, dan worden 0 en 1 weergegeven als Fibonacci-getallen, in die volgorde. Als n 3 is, dan worden 0, 1 en 1 weergegeven als Fibonacci-getallen in die volgorde. Als n 4 is, dan worden 0, 1, 1 en 2 weergegeven als Fibonacci-getallen, in die volgorde. Als n 5 is, dan worden 0, 1, 1, 2 en 3 weergegeven als Fibonacci-getallen, in die volgorde. Als n 6 is, dan worden 0, 1, 1, 2, 3 en 5 weergegeven als Fibonacci-getallen, in die volgorde - enzovoort.
De ECMAscript-functie om de eerste n Fibonacci-getallen (getallen) te genereren is:
< scripttype = 'tekst/ecmascript' >functie fibonacci ( EEN ) {
n = A. lengte ;
als ( n > 0 )
EEN [ 0 ] = 0 ;
als ( n > 1 )
EEN [ 1 ] = 1 ;
voor ( i = twee ; i < n ; i ++ ) { //n=0 en n=2 zijn overwogen
currNee = EEN [ i - 1 ] + EEN [ i - twee ] ;
EEN [ i ] = currNee ;
}
}
De afsluitende scripttag is niet weergegeven. De functie krijgt een array. De eerste twee Fibonacci-nummers worden op hun positie toegewezen. De for-lus itereert van de op nul gebaseerde index, 2 tot net onder n. De belangrijkste uitspraak in de for-loop is:
currNo = A[i – 1] + A[i – 2];
Dit voegt de twee onmiddellijk voorafgaande getallen in de array toe om het huidige nummer te krijgen. Tegen de tijd dat de functie fibonacci() is uitgevoerd, zijn alle elementen van de array de eerste n Fibonacci-getallen. Een geschikte code om de functie fibonacci() aan te roepen en de Fibonacci-getallen weer te geven is:
N = 12 ;arr = nieuwe Array ( N ) ;
fibonacci ( arr ) ;
voor ( i = 0 ; i < N ; i ++ )
document. schrijven ( arr [ i ] + ' ' ) ;
document. schrijven ( '
' ) ;
script >
Deze code toont de afsluitende scripttag. De code wordt getypt onder de bovenstaande code. De uitvoer die op de webpagina wordt weergegeven, is:
0 1 1 2 3 5 8 13 21 34 55 89
zoals verwacht.
Eén Fibonacci-getal produceren in O(1) tijd
O(1) is constante tijd. Het verwijst naar één hoofdbewerking. Een andere wiskundige formule om een Fibonacci-getal te produceren is:
Merk op dat aan de rechterkant van de vergelijking niet de vierkantswortel van 5 wordt verheven tot de macht n; het is de uitdrukking tussen haakjes die wordt verheven tot de macht n. Er zijn twee van dergelijke uitdrukkingen.
Als n 0 is, zou Fibn 0 zijn. Als n 1 is, zou Fibn 1 zijn. Als n 2 is, zou Fibn 1 zijn. Als n 3 is, zou Fibn 2 zijn. Als n 4 is, zou Fibn 3 zijn – enzovoort. De lezer kan deze formule wiskundig verifiëren door verschillende waarden voor n te vervangen en te evalueren. n is een op nul gebaseerde index in deze formule. Het resultaat is het bijbehorende Fibonacci-getal.
De ECMAScript (JavaScript)-code voor deze formule is:
< scripttype = 'tekst/ecmascript' >functie fibNee ( n ) {
FibN = ( Wiskunde . pow ( ( 1 + Wiskunde . sqrt ( 5 ) ) / twee , n ) - Wiskunde . pow ( ( 1 - Wiskunde . sqrt ( 5 ) ) / twee , n ) ) / Wiskunde . sqrt ( 5 ) ;
opbrengst FibN ;
}
De afsluitende scripttag is niet weergegeven. Merk op hoe de vooraf gedefinieerde functies power (pow) en vierkantswortel (sqrt) zijn gebruikt. In ECMAScript (JavaScript) hoeft de Math-module niet geïmporteerd te worden. De functie fibNo() implementeert de formule direct. Een geschikte aanroep en weergave voor de fibNo()-functie op de webpagina zijn:
N = elf ;Rechtsaf = fibNee ( N ) ;
document. schrijven ( Rechtsaf ) ;
script >
De code toont de afsluitende scripttag. De uitvoer is:
89.00000000000003
Het is mogelijk om de onnodige decimale cijfers uit het antwoord te verwijderen. Maar dat is een discussie voor een andere keer.
Als er meer dan één Fibonacci-getal is vereist, moet de code de formule één keer aanroepen voor elke op nul gebaseerde overeenkomstige n-index.
Conclusie
Fibonacci-getallen zijn een bepaalde reeks positieve gehele getallen, beginnend bij 0. Gehele getallen zijn positieve gehele getallen. Een Fibonacci-getal is dus een bepaalde reeks gehele getallen of natuurlijke getallen, beginnend bij 0. In deze reeks zijn de eerste twee getallen 0 en 1, in die volgorde. Deze eerste twee nummers zijn gewoon als zodanig gedefinieerd. De rest van de nummers worden van daaruit ontwikkeld door de twee direct daaraan voorafgaande nummers toe te voegen.
Na het produceren van de eerste twee Fibonacci-getallen, om de rest van de Fibonacci-getallen te produceren, om te eindigen met een totaal van n-getallen, moet een for-lus worden gebruikt met de instructie:
currNo = A[i – 1] + A[i – 2];
Dit voegt de onmiddellijk laatste twee Fibonacci-getallen toe om het huidige Fibonacci-getal te hebben.
Als u een op nul gebaseerde index krijgt, gebruikt u de formule om het bijbehorende Fibonacci-getal te krijgen:
