Betydningen av Fibonacci-tall
Fibonacci-tall er en bestemt sekvens av positive heltall, som begynner fra 0. Hele tall er positive heltall. Så, et Fibonacci-tall er en bestemt sekvens av hele tall eller naturlige tall, som begynner fra 0. I denne sekvensen er de to første tallene 0 og 1, i den rekkefølgen. Resten av tallene utvikles derfra ved å legge til de to foregående tallene. De første tolv Fibonacci-tallene oppnås som følger:
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 andre ord, de første tolv Fibonacci-tallene er:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Selvfølgelig vil det trettende tallet være: 144 = 55 + 89. Fibonacci-tall kan tenkes å være i en matrise, slik:
| 0 | 1 | 1 | to | 3 | 5 | 8 | 1. 3 | tjueen | 3. 4 | 55 | 89 |
En matrise har indekser. I den følgende tabellen viser den andre raden de tilsvarende nullbaserte indeksene for Fibonacci-tallene i en matrise:
| 0 | 1 | 1 | to | 3 | 5 | 8 | 1. 3 | tjueen | 3. 4 | 55 | 89 |
| 0 | 1 | to | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elleve |
Med nullbaserte indekser, hvis det er tolv elementer, er den siste indeksen 11.
Fibonacci-tall kan produseres i O(n)-tid eller i O(1)-tid. I disse tidskompleksitetsuttrykkene betyr n n hovedoperasjoner, og 1 betyr 1 hovedoperasjon. Med O(n) produseres n Fibonacci-tall, fra 0. Med O(1) produseres ett Fibonacci-tall fra den tilsvarende indeksen. Det er derfor O(1) tar bare én hovedoperasjon i stedet for n hovedoperasjoner.
Målet med denne artikkelen er å forklare hvordan man produserer Fibonacci-tall, uansett, ved å bruke JavaScript, som faktisk er ECMAScript i dag.
Kodemiljø
Node.js-miljøet vil ikke bli brukt slik leseren kanskje hadde forventet. I stedet vil nettleseren brukes til å tolke koden og vise resultatene. Skriptet (koden) skal skrives i en tekstredigeringsfil, som skal lagres med filtypen '.html.' Skriptet bør ha som minimumskode:
DOCTYPE HTML >< html >
< hode >
< tittel > Fibonacci-tall med JavaScript tittel >
hode >
< kropp >
< skripttype = 'tekst/ecmascript' >
manus >
kropp >
html >
Dette er en omtrentlig minimumskode en nettside trenger. All koding for denne artikkelen går mellom taggene, .
For å kjøre koden skrevet (lagt til), bare dobbeltklikk på ikonet for filnavnet, og nettleseren på datamaskinen vil åpne den.
Definisjon av et Fibonacci-nummer
Det er en matematisk definisjon for et Fibonacci-tall. Det er definert som følger:
Der Fn er et Fibonacci-tall som tilsvarer en nullbasert indeks, n.
De to første tallene: 0 og 1, er forhåndserklært, i den rekkefølgen. Den siste linjen i denne funksjonen viser hvordan resten av tallene stammer fra de to første tallene i deres rekkefølge.
Denne definisjonen er også en av formlene for Fibonacci-tallet.
Produserer Fibonacci-tall på O(n)-tid
Hvis n er 1, vil bare 0 bli vist som et Fibonacci-tall. Hvis n er 2, vil 0 og 1 vises som Fibonacci-tall, i den rekkefølgen. Hvis n er 3, vil 0, 1 og 1 vises som Fibonacci-tall i den rekkefølgen. Hvis n er 4, vil 0, 1, 1 og 2 vises som Fibonacci-tall, i den rekkefølgen. Hvis n er 5, vil 0, 1, 1, 2 og 3 vises som Fibonacci-tall, i den rekkefølgen. Hvis n er 6, vil 0, 1, 1, 2, 3 og 5 vises som Fibonacci-tall, i den rekkefølgen – og så videre.
ECMAscript-funksjonen for å generere de første n Fibonacci-heltallene (tall) er:
< skripttype = 'tekst/ecmascript' >funksjon fibonacci ( EN ) {
n = EN. lengde ;
hvis ( n > 0 )
EN [ 0 ] = 0 ;
hvis ( n > 1 )
EN [ 1 ] = 1 ;
til ( Jeg = to ; Jeg < n ; Jeg ++ ) { //n=0 og n=2 har blitt vurdert
currNo = EN [ Jeg - 1 ] + EN [ Jeg - to ] ;
EN [ Jeg ] = currNo ;
}
}
Den avsluttende skriptkoden har ikke blitt vist. Funksjonen mottar en matrise. De to første Fibonacci-numrene tildeles på deres posisjon. For-løkken itererer fra den nullbaserte indeksen, 2 til like under n. Det viktigste utsagnet i for-løkken er:
currNo = A[i – 1] + A[i – 2];
Dette legger til de umiddelbare to foregående tallene i matrisen for å ha det gjeldende nummeret. Når fibonacci()-funksjonen er ferdig utført, er alle elementene i matrisen de første n Fibonacci-tallene. En passende kode for å kalle fibonacci()-funksjonen og vise Fibonacci-tallene er:
N = 12 ;arr = ny Array ( N ) ;
fibonacci ( arr ) ;
til ( Jeg = 0 ; Jeg < N ; Jeg ++ )
dokument. skrive ( arr [ Jeg ] + ' ' ) ;
dokument. skrive ( «
» ) ;
manus >
Denne koden viser den avsluttende skriptkoden. Koden skrives inn under koden ovenfor. Utdataene som vises på nettsiden er:
0 1 1 2 3 5 8 13 21 34 55 89
som forventet.
Produserer ett Fibonacci-nummer på O(1)-tid
O(1) er konstant tid. Det refererer til én hovedoperasjon. En annen matematisk formel for å produsere et Fibonacci-tall er:
Merk at på høyre side av ligningen er det ikke kvadratroten av 5 som heves til potensen n; det er uttrykket i parentes som heves til potensen n. Det er to slike uttrykk.
Hvis n er 0, vil Fibn være 0. Hvis n er 1, vil Fibn være 1. Hvis n er 2, vil Fibn være 1. Hvis n er 3, vil Fibn være 2. Hvis n er 4, vil Fibn være 3 – og så videre. Leseren kan verifisere denne formelen matematisk ved å erstatte n med forskjellige verdier og evaluere. n er en nullbasert indeks i denne formelen. Resultatet er det tilsvarende Fibonacci-tallet.
ECMAScript (JavaScript)-koden for denne formelen er:
< skripttype = 'tekst/ecmascript' >funksjon fibNo ( n ) {
FibN = ( Matte . pow ( ( 1 + Matte . sqrt ( 5 ) ) / to , n ) - Matte . pow ( ( 1 - Matte . sqrt ( 5 ) ) / to , n ) ) / Matte . sqrt ( 5 ) ;
komme tilbake FibN ;
}
Den avsluttende skriptkoden har ikke blitt vist. Legg merke til hvordan de forhåndsdefinerte funksjonene kraft (pow) og kvadratrot (sqrt) har blitt brukt. I ECMAScript (JavaScript) trenger ikke Math-modulen å importeres. Funksjonen fibNo() implementerer formelen direkte. Et passende kall og visning for fibNo()-funksjonen på nettsiden er:
N = elleve ;Ikke sant = fibNo ( N ) ;
dokument. skrive ( Ikke sant ) ;
manus >
Koden viser den avsluttende skriptkoden. Utgangen er:
89.00000000000003
Det er mulig å fjerne de unødvendige desimalsifrene fra svaret. Det er imidlertid en diskusjon for en annen gang.
Hvis det kreves mer enn ett Fibonacci-nummer, må koden kalle formelen én gang for hver nullbasert tilsvarende n-indeks.
Konklusjon
Fibonacci-tall er en bestemt sekvens av positive heltall, som begynner fra 0. Hele tall er positive heltall. Så, et Fibonacci-tall er en bestemt sekvens av hele tall eller naturlige tall, som begynner fra 0. I denne sekvensen er de to første tallene 0 og 1, i den rekkefølgen. Disse to første tallene er bare definert som sådan. Resten av tallene utvikles derfra ved å legge til de to umiddelbart foregående tallene.
Etter å ha produsert de to første Fibonacci-tallene, for å produsere resten av Fibonacci-tallene, for å ende opp med totalt n tall, må en for-løkke brukes med setningen:
currNo = A[i – 1] + A[i – 2];
Dette legger til de to siste Fibonacci-tallene for å ha det gjeldende Fibonacci-nummeret.
Når du får en null-basert indeks, for å ha det tilsvarende Fibonacci-nummeret, bruk formelen:
