Fibonacci tall på python språk

“Hvis 0 blir lagt til 1, vil svaret være 1. Hvis svaret 1 og tillegget (ikke Augend) blir lagt sammen, vil det nye svaret være 2. Hvis dette nye svaret og dets tillegg blir lagt sammen, vil svaret være 3. Hvis dette nye svaret og dets tillegg blir lagt sammen, vil svaret være 5.”

Fibonacci-tall er en bestemt sekvens der den første verdien er forhåndsklær som 0 og den andre verdien er forhåndsklær som 1. Resten av tallene er produsert fra disse to ved å legge til de to foregående tallene. Alle fibonacci -tall er positive heltall, som begynner fra 0. De første tolv fibonacci -tallene og hvordan de oppnås er 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

Uten sumuttrykkene kan disse fibonacci -tallene settes i en tabell som følger:

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

Den første raden har Fibonacci -tallene. Den andre raden har nullbaserte indekser, forutsatt at Fibonacci-tallene er i en matrise.

Fibonacci -tall kan produseres i O (n) tid og 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 en tilsvarende indeks. Det er grunnen til at det bare tar en hovedoperasjon i stedet for n hovedoperasjoner.

Målet med denne artikkelen er å forklare hvordan du kan produsere fibonacci -tall, uansett ved å bruke Python.

Formel for et fibonacci -nummer

Den formelle definisjonen av et fibonacci -nummer er:

hvor f_n er fibonacci-nummeret på nullbasert n

Produserer fibonacci -tall i O (n) tid

Hvis n er 1, vil bare 0 bli skrevet ut som et fibonacci -nummer. Hvis n er 2, ville 0 og 1 bli skrevet ut som fibonacci -tall, i den rekkefølgen. Hvis n er 3, ville 0, 1 og 1 bli skrevet ut som fibonacci -tall i den rekkefølgen. Hvis n er 4, ville 0, 1, 1 og 2 bli skrevet ut som fibonacci -tall i den rekkefølgen. Hvis n er 5, ville 0, 1, 1, 2 og 3 bli skrevet ut som fibonacci -tall, i den rekkefølgen. Hvis n er 6, ville 0, 1, 1, 2, 3 og 5 bli skrevet ut som fibonacci -tall, i den rekkefølgen - og så videre.

Python -funksjonen for å produsere de første n fibonacci -tallene er:

def fibonacci (n):
arr = [0] * (n)
arr [1] = 1
for i i rekkevidde (2, n):
arr [i] = arr [i - 1] + arr [i - 2]
Returner arr

Det begynner med å lage en rekke N -elementer, alle initialisert til nuller. Denne matrisen vil inneholde Fibonacci -tallene. Det første fibonacci -nummeret, 0, er allerede der. Det andre Fibonacci -nummeret, 1, er tildelt av neste uttalelse (i funksjonen). Så er det for-loop, som begynner fra indeks 2 til rett før n. Den har uttalelsen:

arr [i] = arr [i - 1] + arr [i - 2]

Dette legger til de umiddelbare foregående to tallene.

Kode for å ringe funksjonen og skrive ut de første tolv fibonacci -tallene kan være:

N = 12
A = fibonacci (n)
for jeg i rekkevidde (n):
print (a [i], end = ")
skrive ut()

Utgangen er:

0 1 1 2 3 5 8 13 21 34 55 89

Produsere ett fibonacci -nummer i konstant tid

Det er en matematisk formel som knytter en nullbasert indeks til det tilsvarende Fibonacci-nummeret. 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.

Hvis n er 0, ville Fibn være 0. Hvis n er 1, fib_n ville være 1. Hvis n er 2, fib_n ville være 1. Hvis n er 3, fib_n ville være 2. Hvis n er 4, fib_n ville 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.

Python -koden for denne formelen er:

Importer matematikk

def fiBno (n):
Fibn = (((1+matematikk.SQRT (5))/2) ** N - ((1 -MATH.SQRT (5)) / 2) ** N) / MATH.SQRT (5)
Return Fibn

Matemodulen ble importert. Den har kvadratrotfunksjonen. Operatøren, ** brukes til strøm. Funksjonen Fibno () implementerer formelen direkte. En passende samtale og utskrift for Fibno () -funksjonen er:

N = 11
Ret = Fibno (n)
Print (RET)

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 forskjellige fibonacci -tall for forskjellige N -indekser, må funksjonsfibno () kalles en gang for hver av N -indeksen for å returnere de forskjellige tilsvarende Fibonacci -tallene. Følgende program gjør dette for de nullbaserte indeksene, 7 til 9 (inkluderende):

Importer matematikk

def fiBno (n):
Fibn = (((1+matematikk.SQRT (5))/2) ** N - ((1 -MATH.SQRT (5)) / 2) ** N) / MATH.SQRT (5)
Return Fibn
for jeg i rekkevidde (7, 10):
trykk (Fibno (i), end = ")
skrive ut()

Utgangen er:

1. 3.00000000000000002 21.000000000000004 34.00000000000001

Legg merke til hvordan for-loopen er kodet i Python. Den første indeksen er 7. Neste indeks er 8, og den siste indeksen er 9. 10 I rekkevidden er argumentet 9 + 1. Verdien i plassering av 10 må være den siste nullbaserte indeksen pluss 1. Det første argumentet, 7, er Start Zero-Based Index.

Konklusjon

Fibonacci -tall er en bestemt sekvens av hele tall (positive heltall). Det begynner med 0, etterfulgt av 1 ubetinget. Resten av tallene er utviklet derfra ved å legge til de umiddelbare to tallene.

For å få de første N Fibonacci-tallene, godta 0 og 1 som de to første, og bruk for resten en for-loop med en uttalelse som:

arr [i] = arr [i - 1] + arr [i - 2]

som legger til de umiddelbare foregående to tallene.

For å få bare ett fibonacci-nummer fra en nullbasert indeks n, bruk formelen: