Fibonacciho čísla v jazyce Python

Fibonacciho čísla jsou zvláštní posloupnost, kde první hodnota je předem deklarována jako 0 a druhá hodnota je předem deklarována jako 1. Zbývající čísla jsou vytvořena z těchto dvou sečtením předchozích dvou čísel. Všechna Fibonacciho čísla jsou kladná celá čísla, začínající od 0. Prvních dvanáct Fibonacciho čísel a způsob jejich získání jsou následující:

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 součtových výrazů lze tato Fibonacciho čísla vložit do tabulky takto:

První řádek obsahuje Fibonacciho čísla. Druhý řádek má indexy založené na nule za předpokladu, že Fibonacciho čísla jsou v poli.

Fibonacciho čísla lze vytvořit v čase O(n) a v čase O(1). V těchto výrazech časové složitosti n znamená n hlavních operací a 1 znamená 1 hlavní operaci. S O(n) se vytvoří n Fibonacciho čísel počínaje 0. S O(1) se z odpovídajícího indexu vytvoří jedno Fibonacciho číslo. To je důvod, proč to vyžaduje pouze jednu hlavní operaci místo n hlavních operací.

Cílem tohoto článku je vysvětlit, jak vytvářet Fibonacciho čísla v obou směrech pomocí Pythonu.

Vzorec pro Fibonacciho číslo

Formální definice Fibonacciho čísla je:

kde F _n je Fibonacciho číslo na n

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

Pokud n je 1, pak se jako Fibonacciho číslo vytiskne pouze 0. Pokud n je 2, pak 0 a 1 budou vytištěny jako Fibonacciho čísla v tomto pořadí. Pokud n je 3, pak 0, 1 a 1 budou vytištěny jako Fibonacciho čísla v tomto pořadí. Pokud n je 4, pak 0, 1, 1 a 2 budou vytištěny jako Fibonacciho čísla v tomto pořadí. Pokud n je 5, pak 0, 1, 1, 2 a 3 budou vytištěny jako Fibonacciho čísla v tomto pořadí. Pokud n je 6, pak 0, 1, 1, 2, 3 a 5 budou vytištěny jako Fibonacciho čísla v tomto pořadí – a tak dále.

Funkce Pythonu pro vytvoření prvních n Fibonacciho čísel je:

Začíná vytvořením pole n prvků, všechny inicializované na nuly. Toto pole bude obsahovat Fibonacciho čísla. První Fibonacciho číslo, 0, již existuje. Druhé Fibonacciho číslo, 1, je přiřazeno dalším příkazem (ve funkci). Pak je tu smyčka for, která začíná od indexu 2 těsně před n. Má prohlášení:

Tím se přidají bezprostředně předchozí dvě čísla.

Kód pro volání funkce a tisk prvních dvanácti Fibonacciho čísel může být:

N = 12
A = Fibonacci(N)
pro i v rozsahu (N):
tisknout (A[i], end=' ‘)
tisk()

Výstup je:

Vytváření jednoho Fibonacciho čísla v konstantním čase

Existuje matematický vzorec, který dává do vztahu index založený na nule a odpovídající Fibonacciho číslo. Vzorec je:

Všimněte si, že na pravé straně rovnice to není druhá odmocnina z 5, která je umocněna n; právě výraz v závorce je umocněn n. Existují dva takové výrazy.

Pokud n je 0, Fibn by bylo 0. Pokud n je 1, Fib _n by bylo 1. Pokud n je 2, Fib _n by bylo 1. Pokud n je 3, Fib _n by bylo 2. Pokud n je 4, Fib _n bude 3 – a tak dále. Čtenář si může tento vzorec ověřit matematicky dosazením různých hodnot za n a vyhodnocením. n je v tomto vzorci index založený na nule.

Kód Pythonu pro tento vzorec je:

importovat matematiku

Matematický modul byl importován. Má funkci druhé odmocniny. Operátor ** se používá pro napájení. Funkce fibNo() implementuje vzorec přímo. Vhodné volání a tisk funkce fibNo() je:

N = 11
vpravo = fibNo (N)
tisknout (ret)

Výstup je:

Z odpovědi je možné odstranit nepotřebné desetinné číslice. To je však diskuse na jindy.

Pokud jsou pro různé n indexy vyžadována různá Fibonacciho čísla, musí být funkce fibNo() volána jednou pro každý z n indexů, aby se vrátila různá odpovídající Fibonacciho čísla. Následující program to dělá pro indexy založené na nule, 7 až 9 (včetně):

importovat matematiku

Výstup je:

Všimněte si způsobu, jakým byla for-loop kódována v Pythonu. První index je 7. Další index je 8 a poslední index je 9. 10 v argumentu rozsahu je 9 + 1. Hodnota na pozici 10 musí být posledním indexem založeným na nule plus 1. První argument, 7, je počáteční index založený na nule.

Závěr

Fibonacciho čísla jsou zvláštní posloupnost celých čísel (kladných celých čísel). Začíná 0, následuje 1 bezpodmínečně. Zbývající čísla se odtud vyvinou přidáním bezprostředně předchozích dvou čísel.

Chcete-li získat prvních n Fibonacciho čísel, přijměte 0 a 1 jako první dvě, pak pro zbytek použijte for-loop s příkazem jako:

který sčítá bezprostředně předchozí dvě čísla.

Chcete-li získat pouze jedno Fibonacciho číslo z indexu n založeného na nule, použijte vzorec: