Betydning af Fibonacci-tal
Fibonacci-tal er en bestemt sekvens af positive heltal, begyndende fra 0. Hele tal er positive heltal. Så et Fibonacci-tal er en bestemt sekvens af hele tal eller naturlige tal, der begynder fra 0. I denne sekvens er de første to tal 0 og 1, i den rækkefølge. Resten af tallene udvikles derfra ved at tilføje de to foregående tal. De første tolv Fibonacci-numre opnå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 er de første tolv Fibonacci-tal:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Selvfølgelig ville det trettende tal være: 144 = 55 + 89. Fibonacci-tal kan forestilles at være i en matrix, som sådan:
| 0 | 1 | 1 | to | 3 | 5 | 8 | 13 | enogtyve | 3. 4 | 55 | 89 |
Et array har indekser. I den følgende tabel viser den anden række de tilsvarende nul-baserede indekser for Fibonacci-tallene i en matrix:
| 0 | 1 | 1 | to | 3 | 5 | 8 | 13 | enogtyve | 3. 4 | 55 | 89 |
| 0 | 1 | to | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elleve |
Med nul-baserede indekser, hvis der er tolv elementer, så er det sidste indeks 11.
Fibonacci-tal kan fremstilles i O(n)-tid eller i O(1)-tid. I disse tidskompleksitetsudtryk betyder n n hovedoperationer, og 1 betyder 1 hovedoperation. Med O(n) produceres n Fibonacci-tal, begyndende fra 0. Med O(1) produceres ét Fibonacci-tal ud fra det tilsvarende indeks. Det er derfor, O(1) kun tager én hovedoperation i stedet for n hovedoperationer.
Formålet med denne artikel er at forklare, hvordan man producerer Fibonacci-numre, på begge måder, ved hjælp af JavaScript, som faktisk er ECMAScript i dag.
Kodningsmiljø
Node.js-miljøet vil ikke blive brugt, som læseren måske havde forventet. I stedet vil browseren blive brugt til fortolkning af koden og visning af resultaterne. Scriptet (koden) skal skrives i en tekstredigeringsfil, som skal gemmes med filtypen '.html.' Scriptet skal have som minimum kode:
DOCTYPE HTML >< html >
< hoved >
< titel > Fibonacci-numre med JavaScript titel >
hoved >
< legeme >
< script type = 'tekst/ecmascript' >
manuskript >
legeme >
html >
Dette er en omtrentlig minimumskode, som en webside har brug for. Al kodning for denne artikel går mellem tags, .
For at køre koden skrevet (tilsat), skal du blot dobbeltklikke på ikonet for filnavnet, og computerens browser åbner den.
Definition af et Fibonacci-nummer
Der er en matematisk definition for et Fibonacci-tal. Det er defineret som følger:
Hvor Fn er et Fibonacci-tal svarende til et nul-baseret indeks, n.
De første to tal: 0 og 1, er forud-erklæret i nævnte rækkefølge. Den sidste linje i denne funktion viser, hvordan resten af tallene stammer fra de to første tal i deres rækkefølge.
Denne definition er også en af formlerne for Fibonacci-tallet.
Fremstilling af Fibonacci-tal i O(n)-tid
Hvis n er 1, vil kun 0 blive vist som et Fibonacci-tal. Hvis n er 2, vil 0 og 1 blive vist som Fibonacci-tal i den rækkefølge. Hvis n er 3, vil 0, 1 og 1 blive vist som Fibonacci-tal i den rækkefølge. Hvis n er 4, vil 0, 1, 1 og 2 blive vist som Fibonacci-tal i den rækkefølge. Hvis n er 5, vil 0, 1, 1, 2 og 3 blive vist som Fibonacci-tal i den rækkefølge. Hvis n er 6, vil 0, 1, 1, 2, 3 og 5 blive vist som Fibonacci-tal i den rækkefølge – og så videre.
ECMAscript-funktionen til at generere de første n Fibonacci-heltal (tal) er:
< script type = 'tekst/ecmascript' >fungere fibonacci ( EN ) {
n = EN. længde ;
hvis ( n > 0 )
EN [ 0 ] = 0 ;
hvis ( n > 1 )
EN [ 1 ] = 1 ;
til ( jeg = to ; jeg < n ; jeg ++ ) { //n=0 og n=2 er blevet overvejet
currNo = EN [ jeg - 1 ] + EN [ jeg - to ] ;
EN [ jeg ] = currNo ;
}
}
Det afsluttende script-tag er ikke blevet vist. Funktionen modtager et array. De første to Fibonacci-numre er tildelt på deres position. For-løkken itererer fra det nul-baserede indeks, 2 til lige under n. Det vigtigste udsagn i for-løkken er:
currNo = A[i – 1] + A[i – 2];
Dette tilføjer de umiddelbare to foregående numre i arrayet for at have det aktuelle nummer. På det tidspunkt, hvor fibonacci()-funktionen er færdig med at udføre, er alle elementerne i arrayet de første n Fibonacci-tal. En passende kode til at kalde fibonacci()-funktionen 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 ( '
' ) ;
manuskript >
Denne kode viser det afsluttende script-tag. Koden er skrevet under ovenstående kode. Det output, der vises på websiden, er:
0 1 1 2 3 5 8 13 21 34 55 89
som forventet.
Producerer ét Fibonacci-nummer på O(1)-tid
O(1) er konstant tid. Det refererer til én hovedoperation. En anden matematisk formel til at producere et Fibonacci-tal er:
Bemærk, at på højre side af ligningen er det ikke kvadratroden af 5, der hæves til potensen n; det er udtrykket i parentes, der hæves til potensen n. Der er to sådanne udtryk.
Hvis n er 0, ville Fibn være 0. Hvis n er 1, ville Fibn være 1. Hvis n er 2, ville Fibn være 1. Hvis n er 3, ville Fibn være 2. Hvis n er 4, ville Fibn være 3 – og så videre. Læseren kan verificere denne formel matematisk ved at erstatte n med forskellige værdier og evaluere. n er et nul-baseret indeks i denne formel. Resultatet er det tilsvarende Fibonacci-tal.
ECMAScript (JavaScript) koden for denne formel er:
< script type = 'tekst/ecmascript' >fungere fibNr ( n ) {
FibN = ( Matematik . pow ( ( 1 + Matematik . sqrt ( 5 ) ) / to , n ) - Matematik . pow ( ( 1 - Matematik . sqrt ( 5 ) ) / to , n ) ) / Matematik . sqrt ( 5 ) ;
Vend tilbage FibN ;
}
Det afsluttende script-tag er ikke blevet vist. Bemærk, hvordan de foruddefinerede power (pow) og kvadratrods (sqrt) funktioner er blevet brugt. I ECMAScript (JavaScript) skal Math-modulet ikke importeres. Funktionen fibNo() implementerer formlen direkte. Et passende opkald og display til fibNo()-funktionen på websiden er:
N = elleve ;ret = fibNr ( N ) ;
dokument. skrive ( ret ) ;
manuskript >
Koden viser det afsluttende script-tag. Udgangen er:
89.00000000000003
Det er muligt at fjerne de unødvendige decimaltal fra svaret. Det er dog en diskussion til en anden gang.
Hvis der kræves mere end ét Fibonacci-nummer, skal koden kalde formlen én gang for hvert nulbaseret tilsvarende n-indeks.
Konklusion
Fibonacci-tal er en bestemt sekvens af positive heltal, begyndende fra 0. Hele tal er positive heltal. Så et Fibonacci-tal er en bestemt sekvens af hele tal eller naturlige tal, der begynder fra 0. I denne sekvens er de første to tal 0 og 1, i den rækkefølge. Disse to første tal er bare defineret som sådan. Resten af tallene er udviklet derfra ved at tilføje de umiddelbart foregående to tal.
Efter at have produceret de to første Fibonacci-tal, for at producere resten af Fibonacci-tallene, for at ende med i alt n tal, skal en for-løkke bruges med sætningen:
currNo = A[i – 1] + A[i – 2];
Dette tilføjer de umiddelbart sidste to Fibonacci-numre for at få det aktuelle Fibonacci-nummer.
Når du får et nul-baseret indeks, skal du bruge formlen for at have det tilsvarende Fibonacci-nummer:
