Fibonacci numbrid Pythoni keeles

Fibonacci numbrid on konkreetne jada, kus esimene väärtus on eeldeklareeritud kui 0 ja teine ​​väärtus on 1. Ülejäänud arvud saadakse nendest kahest kahe eelmise numbri liitmise teel. Kõik Fibonacci arvud on positiivsed täisarvud, mis algavad 0-st. Esimesed kaksteist Fibonacci arvu ja nende saamine on järgmised:

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

Ilma summaavaldisteta saab need Fibonacci arvud tabelisse panna järgmiselt:

Esimesel real on Fibonacci numbrid. Teisel real on nullipõhised indeksid, eeldades, et Fibonacci numbrid on massiivis.

Fibonacci arve saab koostada O(n) aja ja O(1) aja jooksul. Nendes aja keerukuse avaldistes tähendab n n põhitoimingut ja 1 tähendab 1 põhitoimingut. O(n) korral saadakse n Fibonacci arvu, alustades 0-st. O(1) korral saadakse vastavast indeksist üks Fibonacci arv. Seetõttu kulub n põhitoimingu asemel vaid üks põhitehte.

Selle artikli eesmärk on selgitada, kuidas Pythoni abil Fibonacci numbreid mõlemal juhul luua.

Fibonacci arvu valem

Fibonacci numbri ametlik määratlus on:

kus F _n on Fibonacci arv nullipõhise n

Fibonacci arvude tootmine O(n) ajas

Kui n on 1, trükitakse Fibonacci arvuna ainult 0. Kui n on 2, siis 0 ja 1 trükitakse Fibonacci numbritena selles järjekorras. Kui n on 3, siis 0, 1 ja 1 trükitakse Fibonacci arvudena selles järjekorras. Kui n on 4, siis 0, 1, 1 ja 2 trükitakse Fibonacci arvudena selles järjekorras. Kui n on 5, siis 0, 1, 1, 2 ja 3 trükitakse Fibonacci arvudena selles järjekorras. Kui n on 6, siis 0, 1, 1, 2, 3 ja 5 trükitakse Fibonacci arvudena, selles järjekorras – ja nii edasi.

Pythoni funktsioon esimese n Fibonacci numbri saamiseks on:

See algab n-st elemendist koosneva massiivi loomisega, mis kõik nullitakse. See massiiv sisaldab Fibonacci numbreid. Esimene Fibonacci arv 0 on juba olemas. Teine Fibonacci arv, 1, määratakse järgmise lausega (funktsioonis). Siis on for-silmus, mis algab indeksist 2 kuni vahetult enne n. Sellel on avaldus:

See lisab kohe kaks eelmist numbrit.

Kood funktsiooni kutsumiseks ja esimese kaheteistkümne Fibonacci numbri printimiseks võib olla:

N = 12
A = fibonacci (N)
i jaoks vahemikus (N):
print (A[i], end=’ ‘)
print()

Väljund on:

Ühe Fibonacci numbri tootmine pideva aja jooksul

On olemas matemaatiline valem, mis seob nullpõhise indeksi sellele vastava Fibonacci numbriga. Valem on:

Pange tähele, et võrrandi paremal küljel ei ole 5 ruutjuur, mis on tõstetud astmeni n; see on sulgudes olev avaldis, mis tõstetakse astmeni n. Selliseid väljendeid on kaks.

Kui n on 0, oleks Fibn 0. Kui n on 1, siis Fib _n oleks 1. Kui n on 2, siis Fib _n oleks 1. Kui n on 3, siis Fib _n oleks 2. Kui n on 4, Fib _n oleks 3 – ja nii edasi. Lugeja saab seda valemit matemaatiliselt kontrollida, asendades n-i erinevate väärtustega ja hinnates. n on selles valemis nullipõhine indeks.

Selle valemi Pythoni kood on:

importida matemaatikat

Matemaatikamoodul imporditi. Sellel on ruutjuure funktsioon. Toiteallikaks kasutatakse operaatorit **. Funktsioon fibNo() rakendab valemi otse. Sobiv väljakutse ja printimine funktsiooni fibNo() jaoks on:

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

Väljund on:

Vastusest on võimalik eemaldada mittevajalikud kümnendkohad. See on aga mõne teise korra arutelu.

Kui erinevate n indeksi jaoks on vaja erinevaid Fibonacci numbreid, tuleb erinevate vastavate Fibonacci arvude tagastamiseks iga n indeksi jaoks üks kord välja kutsuda funktsioon fibNo(). Järgmine programm teeb seda nullpõhiste indeksite puhul 7 kuni 9 (kaasa arvatud):

importida matemaatikat

Väljund on:

Pange tähele, kuidas for-silmus on Pythonis kodeeritud. Esimene indeks on 7. Järgmine indeks on 8 ja viimane indeks on 9. 10 vahemiku argumendis on 9 + 1. Väärtus positsioonis 10 peab olema viimane nullipõhine indeks pluss 1. Esimene argument 7 on algus nullipõhine indeks.

Järeldus

Fibonacci numbrid on teatud täisarvude (positiivsete täisarvude) jada. See algab 0-ga, millele järgneb tingimusteta 1. Ülejäänud arvud arendatakse sealt edasi, liites kaks vahetult eelnevat numbrit.

Esimese n Fibonacci arvu saamiseks aktsepteerige kahe esimesena 0 ja 1, seejärel kasutage ülejäänud jaoks for-silmust järgmise lausega:

mis liidab vahetult eelnevad kaks numbrit.

Nullil põhinevast indeksist n ainult ühe Fibonacci arvu saamiseks kasutage valemit: