Fibonacci tall på C -språk

“La n være 0. Fibonacci -nummeret for 0 er:

0

La n være 1. Fibonacci -nummeret for 1 er:

1

La n være 2. Fibonacci -nummeret for 2 er:

1 + 0 = 1

La n være 3. Fibonacci -nummeret for 3 er:

1 + 1 = 2

La n være 4. Fibonacci -nummeret for 4 er:

2 + 1 = 3

La n være 5. Fibonacci -nummeret for 5 er:

3 + 2 = 5

La n være 6. Fibonacci -nummeret for 6 er:

5 + 3 = 8

La n være 7. Fibonacci -nummeret for 7 er:

8 + 5 = 13

La n være 8. Fibonacci -nummeret for 8 er:

13 + 8 = 21

La n være 9. Fibonacci -nummeret for 9 er:

21 + 13 = 34

Følgende tabell viser de første tolv fibonacci -tallene:

Den første raden gir Fibonacci -tallene. Den andre raden gir nullbaserte indekser for den tilsvarende matrisen. Disse indeksene er de forskjellige N -heltallene, som begynner fra null. Det kan sees fra bordet at det tiende fibonacci -tallet er 34 + 21 = 55. Også det ellevte fibonacci -tallet er, 55 + 34 = 89 .

Målet med denne artikkelen er å produsere et fibonacci -nummer i o (n) tid og i konstant tid o (1), ved å bruke dataspråket C.

Fibonacci -tall er heltall, som begynner fra 0.”

Formelen for et fibonacci -nummer

Som det fremgår av tabellen ovenfor, er det nåværende fibonacci -tallet summen av de to foregående tallene. Fibonacci -nummeret for 0 er 0, og fibonacci -tallet for 1 er 1. Disse to første tallene, i deres orden, må aksepteres som sådan. Utvikle følgende fibonacci -tall, begynn derfra, for å gi 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, etc.

Formelen for et bestemt fibonacci -nummer kan gis i tre linjer eller en linje. Formelen i tre linjer er gitt som følger:

Denne formelen er definisjonen av et fibonacci -nummer.

Produserer fibonacci -tall i O (n) tid

Mer enn ett fibonacci -nummer kan produseres fra null for en gitt verdi av n. I dette tilfellet er n den høyeste indeksen pluss 1 for matrisen - antar nullbasert indeksering. Fibonacci -nummeret for i = 0 er produsert (i.e 0). Fibonacci -nummeret for i = 1 produseres deretter (i.e., 1). Fibonacci -nummeret for i = 2 produseres deretter neste (i.e., 1 igjen). Fibonacci -nummeret for i = 3 produseres deretter (i.e., 2). Fibonacci -nummeret for i = 4 produseres deretter (i.e., 3). Dette fortsetter til fibonacci -tallet for det gitte tallet (indeksen) på n, si 12, for den høyeste indeksen på 11, er produsert (89).

Et C -program som tar innspill fra tastaturet og sender det ut til terminalen (skjerm) begynner med:

#inkludere

Med dette forhåndsbehandlingsdirektivet vises tekst på tastaturet på skjermen på skjermen. Programutgangen vises også på skjermen. Fibonacci -funksjonen er:

void fibonacci (int a [], int n)
if (n> 0)
A [0] = 0;
if (n> 1)
A [1] = 1;
for (int i = 2; iint nextno = a [i - 1] + a [i - 2];
A [i] = nextno;

De to første uttalelsene i funksjonen blir betraktet som to operasjoner. Liket av for-loop kan betraktes som en operasjon. Hvis n er 12, fungerer for-loopen 10 ganger fordi den første og andre operasjonen, for indeks 0 og indeks 1, allerede har funnet sted. Dette gir en tidskompleksitet på O (12), skrevet som O (n).

Legg merke til uttalelsen:

int nextno = a [i - 1] + a [i - 2];

I kroppen til for-loop. Den legger til de to foregående Fibonacci -tallene for å oppnå det nåværende Fibonacci -nummeret (NextNo).

En passende C hovedfunksjon for programmet ovenfor er:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
Fibonacci (arr, n);
for (int i = 0; iprintf ("%i,", arr [i]);
printf ("\ n");
retur 0;

Produsere ett fibonacci -nummer i konstant tid

Over er indeksen for Fibonacci-nummeret, 89, 11, og ikke 12, for nullbasert indeksering. La 11 være n. I dette tilfellet er det nåværende Fibonacci -nummeret 89. Hvis n er 10, ville det nåværende fibonacci -tallet være 55. Hvis n er 9, ville det nåværende fibonacci -tallet være 34. Dette fortsetter nedover til når n er 0, fibonacci -tallet vil være 0.

Det er en matematisk formel for å oppnå gjeldende (en) Fibonacci-nummer, gitt den nullbaserte indeksen (nummer), med variabelnavnet n. Formelen 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.

Så når n er 0, fib_n vil være 0. Når n er 1, fib_n vil være 1. Når n er 2, fib_n vil være 1. Når n er 3, fib_n vil være 2 - og så videre.

Denne matematiske funksjonen er en hovedoperasjon, og den returnerer bare ett Fibonacci -nummer og ikke en sekvens av tall som tilsvarer, si, indeks 0 til indeks 11. Dette er en konstant tidskode. Det kan fremdeles brukes til å produsere en sekvens av fibonacci -tall ved bare å kalle det om og om igjen med forskjellige verdier av n, som indekser, i et program.

Tidskompleksiteten for denne matematiske funksjonen for å produsere det ene fibonacci -tallet er o (1), konstant tid.

Nå er denne matematiske funksjonen kodet nedenfor for å produsere 12 fibonacci -tall. Det ville bruke mindre total tid enn den forrige algoritmen.

Koden for denne matematiske funksjonen for å produsere sitt en Fibonacci -nummer er:

#inkludere
#inkludere
dobbel fiBno (int n)
Dobbelt FIBN = (POW ((1+SQRT (5))/2, N) - POW ((1 -SQRT (5))/2, N))/SQRT (5);
Retur Fibn;

Merk at matematikken.H -biblioteket er inkludert denne gangen, som bringer inn Power (POW) og Square Root (SQRT) forhåndsdefinerte funksjoner til programmet. Funksjonen produserer bare ett fibonacci -nummer og ikke en sekvens av dem. En passende hovedfunksjon for denne koden er:

int main (int argc, char ** argv)

int n = 11;
dobbel fiBn = fiBno (n);
printf ("%lf \ n", fiBn);
retur 0;

Med en indeks på 11 er utgangen 89.000000. For å kjøre dette programmet med GCC -kompilatoren, bruk imidlertid en kommandolinje som:

GCC Temp.c -o temp -lm

hvor “temp.C ”er kildekoden, og“ Temp ”er det kompilerte programmet. Legg merke til bruken av bryteren, “-lm”, der “L” er små bokstaver L.

Konklusjon

Det første fibonacci -nummeret er 0. Det andre fibonacci -tallet er 1. Resten blir fått ved å legge til de to foregående fibonacci -tallene. Fibonacci -tall er heltall. For å oppnå sekvensen av fibonacci -tall fra null i o (n) tid, bruk en funksjon med en uttalelse som:

int nextno = a [i - 1] + a [i - 2];

Hvor NextNo er det gjeldende tallet for indeksen I, og “A” er matrisen for å holde Fibonacci -sekvensnumrene. De to første tallene, 0 og 1, produseres uavhengig.

For å få bare ett fibonacci -nummer i O (1) tid, bruk matematikkformelen:

der n er den nullbaserte indeksen.

Fibonacci -tall kan oppnås ved bruk av matematriser. Imidlertid er dette en diskusjon for en annen gang.