Fibonačio skaičiai yra tam tikra seka, kurioje pirmoji reikšmė iš anksto deklaruojama kaip 0, o antroji – kaip 1. Likę skaičiai gaunami iš šių dviejų, sudedant du ankstesnius skaičius. Visi Fibonačio skaičiai yra teigiami sveikieji skaičiai, prasidedantys nuo 0. Pirmieji dvylika Fibonačio skaičių ir jų gavimo būdai yra tokie:
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
Be sumos išraiškų šiuos Fibonačio skaičius galima sudėti į lentelę taip:
| 0 | 1 | 1 | du | 3 | 5 | 8 | 13 | dvidešimt vienas | 3. 4 | 55 | 89 |
| 0 | 1 | du | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienuolika |
Pirmoje eilutėje yra Fibonačio skaičiai. Antroje eilutėje yra nuliu pagrįsti indeksai, darant prielaidą, kad Fibonačio skaičiai yra masyve.
Fibonačio skaičius gali būti sudarytas per O (n) laiką ir per O (1) laiką. Šiose laiko sudėtingumo išraiškose n reiškia n pagrindinių operacijų, o 1 reiškia 1 pagrindinę operaciją. Su O(n) sukuriama n Fibonačio skaičių, pradedant nuo 0. Esant O(1), iš atitinkamo indekso gaunamas vienas Fibonačio skaičius. Štai kodėl reikia tik vienos pagrindinės operacijos, o ne n pagrindinių operacijų.
Šio straipsnio tikslas yra paaiškinti, kaip sukurti Fibonačio skaičius bet kuriuo atveju naudojant Python.
Fibonačio skaičiaus formulė
Formalus Fibonačio skaičiaus apibrėžimas yra toks:
kur F n yra Fibonačio skaičius esant nuliui pagrįsto n Jei n yra 1, tada tik 0 būtų atspausdintas kaip Fibonačio skaičius. Jei n yra 2, tada 0 ir 1 būtų atspausdinti kaip Fibonačio skaičiai tokia tvarka. Jei n yra 3, tada 0, 1 ir 1 būtų atspausdinti kaip Fibonačio skaičiai tokia tvarka. Jei n yra 4, tada 0, 1, 1 ir 2 būtų atspausdinti kaip Fibonačio skaičiai tokia tvarka. Jei n yra 5, tada 0, 1, 1, 2 ir 3 būtų atspausdinti kaip Fibonačio skaičiai tokia tvarka. Jei n yra 6, tai 0, 1, 1, 2, 3 ir 5 būtų spausdinami kaip Fibonačio skaičiai, tokia tvarka – ir t.t. Python funkcija pirmiesiems n Fibonačio skaičiams sukurti yra: Jis pradedamas sukuriant n elementų masyvą, kurie visi inicijuojami iki nulių. Šiame masyve bus Fibonačio skaičiai. Pirmasis Fibonačio skaičius 0 jau yra. Antrasis Fibonačio skaičius 1 priskiriamas kitame sakinyje (funkcijoje). Tada yra for-ciklas, kuris prasideda nuo 2 indekso iki prieš pat n. Jame yra pareiškimas: Taip pridedami du ankstesni skaičiai. Kodas, skirtas iškviesti funkciją ir išspausdinti pirmuosius dvylika Fibonačio skaičių, gali būti: N = 12 Išvestis yra: Yra matematinė formulė, kuri nulinį indeksą susieja su atitinkamu Fibonačio skaičiumi. Formulė yra tokia: Atkreipkite dėmesį, kad dešinėje lygties pusėje ne kvadratinė šaknis iš 5 yra pakelta į laipsnį n; tai skliausteliuose esanti išraiška pakeliama iki laipsnio n. Yra dvi tokios išraiškos. Jei n yra 0, Fibn būtų 0. Jei n yra 1, Fib n būtų 1. Jei n yra 2, Fib n būtų 1. Jei n yra 3, Fib n būtų 2. Jei n yra 4, Fib n būtų 3 – ir taip toliau. Skaitytojas gali patikrinti šią formulę matematiškai, pakeisdamas n skirtingomis reikšmėmis ir įvertindamas. n šioje formulėje yra nulinis indeksas. Šios formulės Python kodas yra: importo matematika Matematikos modulis buvo importuotas. Jis turi kvadratinės šaknies funkciją. Operatorius ** naudojamas maitinimui. Funkcija fibNo() formulę įgyvendina tiesiogiai. Tinkamas iškvietimas ir spausdinimas funkcijai fibNo() yra: N = 11 Išvestis yra: Iš atsakymo galima pašalinti nereikalingus dešimtainius skaitmenis. Tačiau tai bus diskusija kitam kartui. Jei skirtingiems n indeksams reikalingi skirtingi Fibonačio skaičiai, funkcija fibNo() turi būti iškviesta vieną kartą kiekvienam n indeksui, kad būtų pateikti skirtingi atitinkami Fibonačio skaičiai. Ši programa tai daro su nuliniais indeksais, nuo 7 iki 9 (imtinai): importo matematika Išvestis yra: Atkreipkite dėmesį į tai, kaip „Python“ užkoduotas ciklas. Pirmasis indeksas yra 7. Kitas indeksas yra 8, o paskutinis indeksas yra 9. 10 diapazono argumente yra 9 + 1. Reikšmė 10 pozicijoje turi būti paskutinis nuliu pagrįstas indeksas plius 1. Pirmasis argumentas, 7, yra pradžios nulinis indeksas. Fibonačio skaičiai yra tam tikra sveikųjų skaičių (teigiamų sveikųjų skaičių) seka. Jis prasideda 0, po to besąlygiškai seka 1. Likę skaičiai sukuriami iš ten pridedant du ankstesnius skaičius. Norėdami gauti pirmuosius n Fibonačio skaičių, priimkite 0 ir 1 kaip pirmuosius du, tada likusiems naudokite for-ciklą su tokiu teiginiu: kuri prideda tiesioginius du ankstesnius skaičius. Norėdami gauti tik vieną Fibonačio skaičių iš nulinio indekso n, naudokite formulę: Fibonačio skaičių generavimas per O(n) laiką
arr = [ 0 ] * ( n )
arr [ 1 ] = 1
dėl i in diapazonas ( du , n ) :
arr [ i ] = arr [ aš - 1 ] + arr [ aš - du ]
grąžinti arr
A = fibonačio (N)
i diapazone (N):
spausdinti (A[i], pabaiga='')
spausdinti () Vieno Fibonačio skaičiaus generavimas pastoviu laiku
FibN = ( ( ( 1 +matematika.kv ( 5 ) ) / du ) ** n - ( ( 1 -matematika.kv ( 5 ) ) / du ) ** n ) / math.sqrt ( 5 )
grąžinti FibN
dešinė = fibNo (N)
spausdinti (ret)
FibN = ( ( ( 1 +matematika.kv ( 5 ) ) / du ) ** n - ( ( 1 -matematika.kv ( 5 ) ) / du ) ** n ) / math.sqrt ( 5 )
grąžinti FibN
dėl i in diapazonas ( 7 , 10 ) :
spausdinti ( fibNr ( i ) , pabaiga = '' )
spausdinti ( )
Išvada
