Fibonacci -tall med JavaScript
Betydning av fibonacci -tall
Fibonacci -tall er en bestemt sekvens av positive heltall, som begynner fra 0. Hele tall er positive heltall. Så et fibonacci -nummer 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 er utviklet 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 ville det trettende tallet være: 144 = 55 + 89. Fibonacci -tall kan tenkes å være i en matrise, slik:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 1. 3 | 21 | 34 | 55 | 89 |
En matrise har indekser. I tabellen nedenfor viser den andre raden de tilsvarende nullbaserte indeksene for Fibonacci-tallene i en matrise:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 1. 3 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
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 -nummer fra den tilsvarende indeksen. Det er grunnen til at O (1) bare tar en hovedoperasjon i stedet for N -hovedoperasjoner.
Målet med denne artikkelen er å forklare hvordan du kan produsere Fibonacci -tall, uansett ved hjelp av JavaScript, som faktisk er ECMASCRIPT i dag.
Kodingsmiljø
Noden.JS -miljø vil ikke bli brukt som leseren kan ha forventet. I stedet vil nettleseren bli brukt til tolkning av koden og vise resultatene. Skriptet (koden) skal skrives i en tekstredigeringsfil, som skal lagres med utvidelsen ".html.”Skriptet skal ha som minimumskode:
Dette er en omtrentlig minimumskode en webside trenger. All koding for denne artikkelen går mellom taggene, og .
For å kjøre koden skrevet (lagt til), bare dobbeltklikk på ikonet for filnavnet, og nettleseren på datamaskinen åpner den.
Definisjon av et fibonacci -nummer
Det er en matematisk definisjon for et fibonacci -nummer. Det er definert som følger:
Der FN er et fibonacci-nummer som tilsvarer en nullbasert indeks, n.
De to første tallene: 0 og 1, er forhåndsklærte, i den rekkefølgen. Den siste linjen i denne funksjonen viser hvordan resten av tallene stammer fra de to første tallene i deres ordre.
Denne definisjonen er også en av formlene for Fibonacci -nummeret.
Produserer fibonacci -tall i O (n) tid
Hvis n er 1, vil bare 0 vises som et fibonacci -nummer. 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:
Denne koden viser det avsluttende skriptetoden. Koden er skrevet under koden ovenfor. Utgangen som vises på websiden er:
0 1 1 2 3 5 8 13 21 34 55 89
som forventet.
Produsere ett fibonacci -nummer i o (1) tid
O (1) er konstant tid. Det refererer til en hovedoperasjon. En annen matematisk formel for å produsere et fibonacci -nummer er:
Legg merke til at det på høyre side av ligningen ikke er kvadratroten til 5 som heves til kraften n; det er uttrykket i parenteser som heves til kraften n. Det er to slike uttrykk.
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. Leseren kan bekrefte denne formelen matematisk ved å erstatte forskjellige verdier med n og evaluere. n er en nullbasert indeks i denne formelen. Resultatet er det tilsvarende Fibonacci -nummeret.
ECMASCRIPT (JavaScript) -koden for denne formelen er:
Koden viser det lukkende skriptetoden. Utgangen er:
89.00000000000003
Det er mulig å fjerne unødvendige desimalsifre fra svaret. Imidlertid er det en diskusjon for en annen gang.
Hvis det kreves mer enn ett Fibonacci -nummer, må koden ringe formelen en 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 -nummer 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 nettopp definert som sådan. Resten av tallene er utviklet derfra ved å legge til de umiddelbare to 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-loop brukes med uttalelsen:
currno = a [i - 1] + a [i - 2];
Dette legger til de umiddelbare de siste to Fibonacci -tallene for å ha det nåværende Fibonacci -nummeret.
Når du får en nullbasert indeks, for å ha det tilsvarende Fibonacci-nummeret, bruk formelen: