Fibonacciho čísla v jazyku Python

Fibonacciho čísla sú konkrétnou postupnosťou, kde prvá hodnota je vopred deklarovaná ako 0 a druhá hodnota je vopred deklarovaná ako 1. Ostatné čísla sú vytvorené z týchto dvoch sčítaním predchádzajúcich dvoch čísel. Všetky Fibonacciho čísla sú kladné celé čísla začínajúce od 0. Prvých dvanásť Fibonacciho čísel a spôsob ich získania sú nasledovné:

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 súčtových výrazov možno tieto Fibonacciho čísla vložiť do tabuľky takto:

Prvý riadok obsahuje Fibonacciho čísla. Druhý riadok má indexy založené na nule za predpokladu, že Fibonacciho čísla sú v poli.

Fibonacciho čísla možno vytvoriť v čase O(n) a v čase O(1). V týchto výrazoch časovej zložitosti n znamená n hlavných operácií a 1 znamená 1 hlavnú operáciu. S O(n) sa vytvorí n Fibonacciho čísel, začínajúc od 0. S O(1) sa zo zodpovedajúceho indexu vytvorí jedno Fibonacciho číslo. To je dôvod, prečo to vyžaduje iba jednu hlavnú operáciu namiesto n hlavných operácií.

Cieľom tohto článku je vysvetliť, ako vytvárať Fibonacciho čísla v oboch smeroch pomocou Pythonu.

Vzorec pre Fibonacciho číslo

Formálna definícia Fibonacciho čísla je:

kde F _n je Fibonacciho číslo na n

Vytváranie Fibonacciho čísel v O(n) čase

Ak n je 1, potom sa ako Fibonacciho číslo vytlačí iba 0. Ak n je 2, potom 0 a 1 budú vytlačené ako Fibonacciho čísla v tomto poradí. Ak n je 3, potom 0, 1 a 1 budú vytlačené ako Fibonacciho čísla v tomto poradí. Ak n je 4, potom 0, 1, 1 a 2 budú vytlačené ako Fibonacciho čísla v tomto poradí. Ak n je 5, potom 0, 1, 1, 2 a 3 budú vytlačené ako Fibonacciho čísla v tomto poradí. Ak n je 6, potom 0, 1, 1, 2, 3 a 5 budú vytlačené ako Fibonacciho čísla v tomto poradí – a tak ďalej.

Funkcia Pythonu na vytvorenie prvých n Fibonacciho čísel je:

Začína sa vytvorením poľa n prvkov, pričom všetky sú inicializované na nuly. Toto pole bude obsahovať Fibonacciho čísla. Prvé Fibonacciho číslo, 0, už existuje. Druhé Fibonacciho číslo, 1, je priradené nasledujúcim príkazom (vo funkcii). Potom je tu cyklus for, ktorý začína od indexu 2 tesne pred n. Má vyhlásenie:

Tým sa pridajú bezprostredne predchádzajúce dve čísla.

Kód na volanie funkcie a vytlačenie prvých dvanástich Fibonacciho čísel môže byť:

N = 12
A = Fibonacci(N)
pre i v rozsahu (N):
vytlačiť (A[i], koniec=' ‘)
tlačiť ()

Výstupom je:

Vytvorenie jedného Fibonacciho čísla v konštantnom čase

Existuje matematický vzorec, ktorý spája index založený na nule s príslušným Fibonacciho číslom. Vzorec je:

Všimnite si, že na pravej strane rovnice to nie je druhá odmocnina z 5, ktorá je umocnená na n; práve výraz v zátvorke je umocnený n. Existujú dva takéto výrazy.

Ak n je 0, Fibn by bolo 0. Ak n je 1, Fib _n by bolo 1. Ak n je 2, Fib _n by bolo 1. Ak n je 3, Fib _n by bolo 2. Ak n je 4, Fib _n bude 3 – a tak ďalej. Čitateľ si môže tento vzorec overiť matematicky dosadením rôznych hodnôt za n a vyhodnotením. n je v tomto vzorci index založený na nule.

Kód Pythonu pre tento vzorec je:

importovať matematiku

Bol importovaný matematický modul. Má funkciu druhej odmocniny. Operátor ** sa používa na napájanie. Funkcia fibNo() implementuje vzorec priamo. Vhodné volanie a tlač funkcie fibNo() je:

N = 11
vpravo = fibNo (N)
tlačiť (ret)

Výstupom je:

Z odpovede je možné odstrániť nepotrebné desatinné číslice. To je však diskusia na inokedy.

Ak sú pre rôzne n indexy potrebné rôzne Fibonacciho čísla, funkcia fibNo() sa musí zavolať raz pre každý z n indexov, aby sa vrátili rôzne zodpovedajúce Fibonacciho čísla. Nasledujúci program to robí pre indexy založené na nule, 7 až 9 (vrátane):

importovať matematiku

Výstupom je:

Všimnite si spôsob, akým bola for-loop kódovaná v Pythone. Prvý index je 7. Ďalší index je 8 a posledný index je 9. 10 v argumente rozsahu je 9 + 1. Hodnota na pozícii 10 musí byť posledným indexom založeným na nule plus 1. Prvý argument, 7, je počiatočný index založený na nule.

Záver

Fibonacciho čísla sú konkrétnou postupnosťou celých čísel (kladných celých čísel). Začína sa 0, po ktorej nasleduje 1 bezpodmienečne. Odtiaľ sa odvíjajú ostatné čísla pridaním bezprostredne predchádzajúcich dvoch čísel.

Ak chcete získať prvých n Fibonacciho čísel, prijmite 0 a 1 ako prvé dve, potom pre zvyšok použite for-loop s výrokom ako:

ktorý pridáva bezprostredne predchádzajúce dve čísla.

Ak chcete získať len jedno Fibonacciho číslo z indexu n založeného na nule, použite vzorec: