Fibonacci számok Python nyelven

A Fibonacci-számok egy bizonyos sorozat, ahol az első érték 0-nak, a második érték pedig 1-nek van előre deklarálva. A többi szám ebből a kettőből jön létre az előző két szám összeadásával. Az összes Fibonacci-szám pozitív egész szám, 0-tól kezdődően. Az első tizenkét Fibonacci-szám és azok beszerzési módja a következő:

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

Az összegkifejezések nélkül ezek a Fibonacci-számok táblázatba helyezhetők a következőképpen:

Az első sorban a Fibonacci-számok vannak. A második sor nulla alapú indexeket tartalmaz, feltételezve, hogy a Fibonacci-számok egy tömbben vannak.

Fibonacci-számok előállíthatók O(n) idővel és O(1) idővel. Ezekben az időbonyolultsági kifejezésekben n n fő műveletet, 1 pedig 1 fő műveletet jelent. O(n) esetén n Fibonacci-szám jön létre, 0-tól kezdve. O(1) esetén egy Fibonacci-szám jön létre a megfelelő indexből. Éppen ezért n fő művelet helyett csak egy főműveletre van szükség.

Ennek a cikknek az a célja, hogy elmagyarázza, hogyan lehet Fibonacci-számokat előállítani Python használatával.

A Fibonacci-szám képlete

A Fibonacci-szám formális meghatározása a következő:

ahol F _n a Fibonacci-szám a nulla alapú n

Fibonacci számok előállítása O(n) idő alatt

Ha n 1, akkor Fibonacci-számként csak 0 kerül kinyomtatásra. Ha n 2, akkor a 0 és az 1 Fibonacci-számként kerül kinyomtatásra, ebben a sorrendben. Ha n 3, akkor a 0, 1 és 1 Fibonacci-számként jelennek meg ebben a sorrendben. Ha n 4, akkor a 0, 1, 1 és 2 Fibonacci-számként jelennek meg ebben a sorrendben. Ha n 5, akkor a 0, 1, 1, 2 és 3 Fibonacci-számként kerül kinyomtatásra, ebben a sorrendben. Ha n 6, akkor a 0, 1, 1, 2, 3 és 5 Fibonacci-számként kerül kinyomtatásra, ebben a sorrendben – és így tovább.

Az első n Fibonacci-számot létrehozó Python-függvény a következő:

Egy n elemből álló tömb létrehozásával kezdődik, amelyek mindegyike nullára van inicializálva. Ez a tömb tartalmazza a Fibonacci-számokat. Az első Fibonacci-szám, a 0, már megvan. A második Fibonacci-számot, az 1-et a következő utasítás (a függvényben) rendeli hozzá. Aztán ott van a for ciklus, amely a 2. indextől az n előtti pontig kezdődik. A következő kijelentés van benne:

Ez hozzáadja az előző két számot.

A függvény meghívásához és az első tizenkét Fibonacci-szám nyomtatásához szükséges kód lehet:

N = 12
A = fibonacci (N)
i tartományban (N):
nyomtatás (A[i], end=’ ‘)
nyomtatás()

A kimenet a következő:

Egy Fibonacci szám előállítása állandó időben

Van egy matematikai képlet, amely egy nulla alapú indexet a megfelelő Fibonacci-számhoz kapcsol. A képlet a következő:

Figyeljük meg, hogy az egyenlet jobb oldalán nem az 5 négyzetgyökét emeljük n hatványra; a zárójelben lévő kifejezés az n hatványra emelkedik. Két ilyen kifejezés létezik.

Ha n 0, Fibn 0 lenne. Ha n 1, Fib _n 1 lenne. Ha n 2, Fib _n 1 lenne. Ha n 3, Fib _n 2 lenne. Ha n értéke 4, Fib _n 3 lenne – és így tovább. Az olvasó ezt a képletet matematikailag ellenőrizheti, ha n-t különböző értékekkel helyettesít, és kiértékeli. n egy nulla alapú index ebben a képletben.

A képlet Python kódja a következő:

import matematika

A matematikai modul importálva lett. Négyzetgyök függvénye van. A ** operátor tápellátásra szolgál. A fibNo() függvény közvetlenül valósítja meg a képletet. A fibNo() függvény megfelelő hívása és nyomtatása a következő:

N = 11
jobb = fibNo(N)
nyomtatás (ret)

A kimenet a következő:

Lehetőség van a felesleges decimális számjegyek eltávolítására a válaszból. Ez azonban máskor vita tárgya.

Ha különböző n indexhez különböző Fibonacci-számokra van szükség, a fibNo() függvényt egyszer meg kell hívni minden n indexhez, hogy a különböző megfelelő Fibonacci-számokat adjuk vissza. A következő program teszi ezt a nulla alapú indexekhez, 7-től 9-ig (beleértve):

import matematika

A kimenet a következő:

Figyelje meg a for ciklus kódolási módját a Pythonban. Az első index a 7. A következő index a 8, az utolsó index pedig a 9. A 10 a tartomány argumentumban 9 + 1. A 10 pozícióban lévő értéknek az utolsó nulla alapú indexnek plusz 1-nek kell lennie. argumentum, 7, a kezdő nulla alapú index.

Következtetés

A Fibonacci-számok egész számok (pozitív egész számok) meghatározott sorozata. 0-val kezdődik, amit feltétel nélkül 1 követ. A többi számot innen fejlesztjük a közvetlen előző két szám összeadásával.

Az első n Fibonacci-szám megszerzéséhez fogadja el a 0-t és az 1-et az első kettőnek, majd a többihez használjon for-hurkot egy ilyen utasítással:

amely összeadja a közvetlen előző két számot.

Ha csak egy Fibonacci-számot szeretne kapni egy nulla alapú n indexből, használja a következő képletet: