Fibonacci-tall på Python-språket

Fibonacci-tall er en bestemt sekvens der den første verdien er forhåndserklært som 0 og den andre verdien er forhåndserklært som 1. Resten av tallene produseres 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:

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-tall fra en tilsvarende indeks. Det er derfor det tar bare én hovedoperasjon i stedet for n hovedoperasjoner.

Målet med denne artikkelen er å forklare hvordan man produserer Fibonacci-tall, uansett, ved hjelp av Python.

Formel for et Fibonacci-nummer

Den formelle definisjonen av et Fibonacci-tall er:

hvor F _n er Fibonacci-tallet ved den nullbaserte n

Produserer Fibonacci-tall på O(n)-tid

Hvis n er 1, vil bare 0 bli skrevet ut som et Fibonacci-tall. Hvis n er 2, vil 0 og 1 bli skrevet ut som Fibonacci-tall, i den rekkefølgen. Hvis n er 3, vil 0, 1 og 1 bli skrevet ut som Fibonacci-tall i den rekkefølgen. Hvis n er 4, vil 0, 1, 1 og 2 bli skrevet ut som Fibonacci-tall i den rekkefølgen. Hvis n er 5, vil 0, 1, 1, 2 og 3 bli skrevet ut som Fibonacci-tall, i den rekkefølgen. Hvis n er 6, vil 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:

Det begynner med å lage en rekke av n elementer, alle initialisert til null. Denne matrisen vil inneholde Fibonacci-tallene. Det første Fibonacci-tallet, 0, er der allerede. Det andre Fibonacci-tallet, 1, tildeles av neste setning (i funksjonen). Så er det for-løkken, som begynner fra indeks 2 til like før n. Den har uttalelsen:

Dette legger til de umiddelbare to foregående tallene.

Koden for å kalle opp funksjonen og skrive ut de første tolv Fibonacci-numrene kan være:

N = 12
A = fibonacci(N)
for i i området (N):
print (A[i], end=' ')
skrive ut()

Utgangen er:

Produserer ett Fibonacci-nummer i konstant tid

Det er en matematisk formel som relaterer en null-basert indeks til dets tilsvarende Fibonacci-nummer. Formelen 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 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 verifisere denne formelen matematisk ved å erstatte n med forskjellige verdier og evaluere. n er en nullbasert indeks i denne formelen.

Python-koden for denne formelen er:

importere matematikk

Matematikkmodulen ble importert. Den har kvadratrotfunksjonen. Operatøren, ** brukes til strøm. Funksjonen fibNo() implementerer formelen direkte. Et passende kall og utskrift for fibNo()-funksjonen er:

N = 11
høyre = fibNo(N)
print (ret)

Utgangen er:

Det er mulig å fjerne de unødvendige desimalsifrene fra svaret. Det er imidlertid en diskusjon for en annen gang.

Hvis forskjellige Fibonacci-tall kreves for forskjellige n-indekser, må funksjonen fibNo() kalles én gang for hver av n-indeksene for å returnere de forskjellige tilsvarende Fibonacci-tallene. Følgende program gjør dette for de nullbaserte indeksene, 7 til 9 (inklusive):

importere matematikk

Utgangen er:

Legg merke til måten for-løkken har blitt kodet i Python. Den første indeksen er 7. Den neste indeksen er 8, og den siste indeksen er 9. 10 i range-argumentet er 9 + 1. Verdien i posisjonen 10 må være den siste nullbaserte indeksen pluss 1. Den første argument, 7, er startnull-basert indeks.

Konklusjon

Fibonacci-tall er en bestemt sekvens av hele tall (positive heltall). Den begynner med 0, etterfulgt av 1 ubetinget. Resten av tallene utvikles derfra ved å legge til de to umiddelbart foregående tallene.

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

som legger til de to umiddelbart foregående tallene.

For å få bare ett Fibonacci-tall fra en null-basert indeks n, bruk formelen: