Fibonacci-numre i Python-sprog

Fibonacci-tal er en bestemt sekvens, hvor den første værdi er forud-erklæret som 0, og den anden værdi er forud-erklæret som 1. Resten af ​​tallene er fremstillet ud fra disse to ved at tilføje de to foregående tal. Alle Fibonacci-tal er positive heltal, begyndende fra 0. De første tolv Fibonacci-tal og hvordan de opnå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

Uden sumudtrykkene kan disse Fibonacci-tal sættes i en tabel som følger:

Den første række har Fibonacci-tallene. Den anden række har nul-baserede indekser, forudsat at Fibonacci-tallene er i en matrix.

Fibonacci-tal kan fremstilles i O(n)-tid og 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 et Fibonacci-tal ud fra et tilsvarende indeks. Det er derfor, det kræver kun én hovedoperation i stedet for n hovedoperationer.

Formålet med denne artikel er at forklare, hvordan man producerer Fibonacci-tal, på begge måder, ved hjælp af Python.

Formel for et Fibonacci-nummer

Den formelle definition af et Fibonacci-tal er:

hvor F _n er Fibonacci-tallet ved det nul-baserede n

Fremstilling af Fibonacci-tal i O(n)-tid

Hvis n er 1, vil kun 0 blive udskrevet som et Fibonacci-tal. Hvis n er 2, vil 0 og 1 blive udskrevet som Fibonacci-tal i den rækkefølge. Hvis n er 3, vil 0, 1 og 1 blive udskrevet som Fibonacci-tal i den rækkefølge. Hvis n er 4, vil 0, 1, 1 og 2 blive udskrevet som Fibonacci-tal i den rækkefølge. Hvis n er 5, vil 0, 1, 1, 2 og 3 blive udskrevet som Fibonacci-tal i den rækkefølge. Hvis n er 6, så vil 0, 1, 1, 2, 3 og 5 blive udskrevet som Fibonacci-tal i den rækkefølge – og så videre.

Python-funktionen til at producere de første n Fibonacci-tal er:

Det begynder med at skabe et array af n elementer, alle initialiseret til nuller. Dette array vil indeholde Fibonacci-tallene. Det første Fibonacci-tal, 0, er der allerede. Det andet Fibonacci-tal, 1, tildeles af den næste sætning (i funktionen). Så er der for-løkken, som begynder fra indeks 2 til lige før n. Den har udsagnet:

Dette tilføjer de umiddelbare to foregående numre.

Kode til at kalde funktionen og udskrive de første tolv Fibonacci-numre kan være:

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

Udgangen er:

Producerer ét Fibonacci-nummer i konstant tid

Der er en matematisk formel, der relaterer et nul-baseret indeks til dets tilsvarende Fibonacci-tal. Formlen 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, 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. 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.

Python-koden for denne formel er:

importere matematik

Matematikmodulet blev importeret. Den har kvadratrodsfunktionen. Operatøren, ** bruges til strøm. Funktionen fibNo() implementerer formlen direkte. Et passende opkald og udskrivning til fibNo()-funktionen er:

N = 11
ret = fibNo(N)
print (ret)

Udgangen er:

Det er muligt at fjerne de unødvendige decimaltal fra svaret. Det er dog en diskussion til en anden gang.

Hvis der kræves forskellige Fibonacci-tal for forskellige n-indekser, skal funktionen fibNo() kaldes én gang for hvert af n-indekset for at returnere de forskellige tilsvarende Fibonacci-tal. Følgende program gør dette for de nul-baserede indekser, 7 til 9 (inklusive):

importere matematik

Udgangen er:

Bemærk den måde for-løkken er blevet kodet i Python. Det første indeks er 7. Det næste indeks er 8, og det sidste indeks er 9. 10 i intervalargumentet er 9 + 1. Værdien i positionen 10 skal være det sidste nul-baserede indeks plus 1. Den første argument, 7, er startnul-baseret indeks.

Konklusion

Fibonacci-tal er en bestemt sekvens af hele tal (positive heltal). Det begynder med 0, efterfulgt af 1 ubetinget. Resten af ​​tallene er udviklet derfra ved at tilføje de umiddelbart foregående to tal.

For at opnå de første n Fibonacci-tal, accepter 0 og 1 som de to første, og for resten, brug en for-løkke med en sætning som:

som tilføjer de umiddelbart foregående to tal.

For at få kun ét Fibonacci-tal fra et nul-baseret indeks n, brug formlen: