Fibonaccijevi brojevi u jeziku Python

Fibonaccijevi brojevi su određeni niz u kojem je prva vrijednost unaprijed deklarirana kao 0, a druga vrijednost je unaprijed deklarirana kao 1. Ostali brojevi se proizvode od ova dva zbrajanjem prethodna dva broja. Svi Fibonaccijevi brojevi su pozitivni cijeli brojevi, počevši od 0. Prvih dvanaest Fibonaccijevih brojeva i kako su dobiveni su sljedeći:

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

Bez izraza zbroja, ovi Fibonaccijevi brojevi mogu se staviti u tablicu na sljedeći način:

Prvi redak sadrži Fibonaccijeve brojeve. Drugi red ima indekse temeljene na nuli, uz pretpostavku da su Fibonaccijevi brojevi u nizu.

Fibonaccijevi brojevi mogu se proizvesti u O(n) vremenu i u O(1) vremenu. U ovim izrazima vremenske složenosti, n znači n glavnih operacija, a 1 znači 1 glavnu operaciju. S O(n), n Fibonaccijevih brojeva se proizvodi, počevši od 0. S O(1), jedan Fibonacci broj se proizvodi iz odgovarajućeg indeksa. Zbog toga je potrebna samo jedna glavna operacija umjesto n glavnih operacija.

Cilj ovog članka je objasniti kako proizvesti Fibonaccijeve brojeve, bilo kako, koristeći Python.

Formula za Fibonaccijev broj

Formalna definicija Fibonaccijevog broja je:

gdje je F _n je Fibonaccijev broj na bazi n

Izrada Fibonaccijevih brojeva u O(n) vremenu

Ako je n 1, tada bi samo 0 bila ispisana kao Fibonaccijev broj. Ako je n 2, tada bi 0 i 1 bili ispisani kao Fibonaccijevi brojevi, tim redoslijedom. Ako je n 3, tada bi 0, 1 i 1 bili ispisani kao Fibonaccijevi brojevi tim redoslijedom. Ako je n 4, tada bi 0, 1, 1 i 2 bili ispisani kao Fibonaccijevi brojevi tim redoslijedom. Ako je n 5, tada bi 0, 1, 1, 2 i 3 bili ispisani kao Fibonaccijevi brojevi, tim redoslijedom. Ako je n 6, tada bi 0, 1, 1, 2, 3 i 5 bili ispisani kao Fibonaccijevi brojevi, tim redoslijedom – i tako dalje.

Python funkcija za proizvodnju prvih n Fibonaccijevih brojeva je:

Započinje stvaranjem niza od n elemenata, svi inicijalizirani na nule. Ovaj niz će sadržavati Fibonaccijeve brojeve. Prvi Fibonaccijev broj, 0, već je tu. Drugi Fibonaccijev broj, 1, dodjeljuje se sljedećom naredbom (u funkciji). Zatim postoji for-petlja, koja počinje od indeksa 2 do neposredno prije n. Ima izjavu:

Ovo zbraja prethodna dva broja.

Kod za pozivanje funkcije i ispis prvih dvanaest Fibonaccijevih brojeva može biti:

N = 12
A = fibonacci(N)
za i u rasponu (N):
ispis (A[i], kraj=’ ‘)
ispis()

Izlaz je:

Izrada jednog Fibonaccijevog broja u konstantnom vremenu

Postoji matematička formula koja povezuje indeks temeljen na nuli s odgovarajućim Fibonaccijevim brojem. Formula je:

Imajte na umu da na desnoj strani jednadžbe kvadratni korijen od 5 nije podignut na potenciju n; to je izraz u zagradama koji se diže na potenciju n. Postoje dva takva izraza.

Ako je n 0, Fibn bi bio 0. Ako je n 1, Fib _n bilo bi 1. Ako je n 2, Fib _n bilo bi 1. Ako je n 3, Fib _n bilo bi 2. Ako je n 4, Fib _n bilo bi 3 – i tako dalje. Čitatelj može matematički provjeriti ovu formulu zamjenom različitih vrijednosti za n i procjenom. n je indeks temeljen na nuli u ovoj formuli.

Python kod za ovu formulu je:

uvozna matematika

Matematički modul je uvezen. Ima funkciju kvadratnog korijena. Operator, ** se koristi za napajanje. Funkcija fibNo() izravno implementira formulu. Prikladan poziv i ispis za funkciju fibNo() je:

N = 11
desno = fibNo(N)
ispis(ret)

Izlaz je:

Moguće je ukloniti nepotrebne decimalne znamenke iz odgovora. No, to je rasprava za neki drugi put.

Ako su za različite n indekse potrebni različiti Fibonaccijevi brojevi, funkcija fibNo() mora se pozvati jednom za svaki od n indeksa da vrati različite odgovarajuće Fibonaccijeve brojeve. Sljedeći program to radi za indekse temeljene na nuli, od 7 do 9 (uključivo):

uvozna matematika

Izlaz je:

Obratite pažnju na način na koji je for-petlja kodirana u Pythonu. Prvi indeks je 7. Sljedeći indeks je 8, a posljednji indeks je 9. 10 u argumentu raspona je 9 + 1. Vrijednost na poziciji 10 mora biti zadnji indeks baziran na nuli plus 1. Prvi argument, 7, je početni indeks baziran na nuli.

Zaključak

Fibonaccijevi brojevi su određeni niz cijelih brojeva (pozitivnih cijelih brojeva). Počinje s 0, nakon čega bezuvjetno slijedi 1. Ostali brojevi se razvijaju odatle dodavanjem neposredno prethodna dva broja.

Da biste dobili prvih n Fibonaccijevih brojeva, prihvatite 0 i 1 kao prva dva, a zatim za ostale upotrijebite for-petlju s izjavom poput:

koji zbraja neposredno prethodna dva broja.

Da biste dobili samo jedan Fibonaccijev broj iz indeksa n temeljenog na nuli, upotrijebite formulu: