Fibonacciho čísla- jedná se o řadu čísel, ve které se každé další číslo rovná součtu dvou předchozích: 1, 1, 2, 3, 5, 8, 13, .... Někdy série začíná od nuly: 0, 1, 1, 2, 3, 5, .... V tomto případě se budeme držet první možnosti.

Vzorec:

F1=1
F2 = 1
F n \u003d F n-1 + F n-2

Příklad výpočtu:

F 3 \u003d F 2 + F 1 \u003d 1 + 1 \u003d 2
F 4 \u003d F 3 + F 2 \u003d 2 + 1 \u003d 3
F 5 \u003d F 4 + F 3 \u003d 3 + 2 \u003d 5
F 6 \u003d F 5 + F 4 \u003d 5 + 3 \u003d 8
...

Výpočet n-tého čísla Fibonacciho řady se smyčkou while

1. Přiřaďte proměnným fib1 a fib2 hodnoty prvních dvou prvků řady, to znamená přiřaďte proměnným jednotky.
2. Zeptejte se uživatele na číslo prvku, jehož hodnotu chce získat. Přiřaďte číslo proměnné n .
3. Proveďte následující kroky n - 2krát, protože první dva prvky již byly vzaty v úvahu:
   1. Přidejte fib1 a fib2 a přiřaďte výsledek proměnné dočasného úložiště, jako je fib_sum .
   2. Nastavte fib1 na fib2.
   3. Nastavte fib2 na fib_sum .
4. Zobrazte hodnotu fib2.

Poznámka. Pokud uživatel zadá 1 nebo 2, tělo smyčky se nikdy neprovede a zobrazí se původní hodnota fib2.

fib1=1 fib2=1 n=vstup() n=int(n) i=0, zatímco i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

Kompaktní verze kódu:

fib1 = fib2 = 1 n = int(vstup( "Číslo prvku řady Fibonacci: ") ) - 2 zatímco n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 tisk (fib2)

Výstup Fibonacciho čísel pomocí smyčky for

V tomto případě se zobrazí nejen hodnota požadovaného prvku Fibonacciho řady, ale také všechna čísla až do ní včetně. K tomu je výstup hodnoty fib2 umístěn do smyčky.

fib1 = fib2 = 1 n = int (vstup () ), pokud n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

Příklad provedení:

10 1 1 2 3 5 8 13 21 34 55

Rekurzivní výpočet n-tého čísla Fibonacciho řady

1. Pokud n = 1 nebo n = 2, vraťte jedničku do volající větve, protože první a druhý prvek Fibonacciho řady se rovnají jedné.
2. Ve všech ostatních případech volejte stejnou funkci s argumenty n - 1 a n - 2. Sečtěte výsledek dvou volání a vraťte jej do volající větve programu.

def fibonacci(n) : if n in (1 , 2 ): return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10) )

Řekněme n = 4. Potom budeme volat rekurzivně fibonacci(3) a fibonacci(2). Druhý vrátí jedničku a první bude mít za následek další dvě volání funkce: Fibonacci(2) a fibonacci(1). Oba hovory vrátí jeden, celkem tedy dva. Volání fibonacciho(3) tedy vrátí číslo 2, které se přičte k číslu 1 z volání fibonacciho(2). Výsledek 3 se vrátí do hlavní větve programu. Čtvrtým prvkem Fibonacciho řady jsou tři: 1 1 2 3.

Programátoři Fibonacciho čísel by už měli mít dost. Všude se používají příklady jejich výpočtu. Vše z toho, co tato čísla poskytují nejjednodušší příklad rekurze. A také jsou dobrý příklad dynamické programování. Je ale nutné je takto počítat v reálném projektu? Není třeba. Ani rekurze, ani dynamické programování nejsou ideální možnosti. A ne uzavřený vzorec používající čísla s plovoucí desetinnou čárkou. Nyní vám řeknu správnou cestu. Nejprve si ale projdeme všechna známá řešení.

Kód je pro Python 3, i když by měl fungovat i pro Python 2.

Nejprve mi dovolte připomenout definici:

F n \u003d F n-1 + F n-2

A F 1 \u003d F 2 \u003d 1.

uzavřený vzorec

Podrobnosti přeskočíme, ale kdo chce, může se seznámit s odvozením vzorce. Cílem je předpokládat, že existuje nějaké x, pro které F n = x n , a pak najít x.

Co dělá

Zmenšíme x n-2

Řešíme kvadratickou rovnici:

Odkud roste "zlatý řez" ϕ=(1+√5)/2. Nahrazením původních hodnot a provedením dalších výpočtů získáme:

Což je to, co používáme k výpočtu F n .

Z __future__ import Division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int (PHI ** n / SQRT5 + 0,5)

Dobrý:
Rychlé a snadné pro malé n
Špatný:
Jsou vyžadovány operace s pohyblivou řádovou čárkou. Větší n bude vyžadovat větší přesnost.
Zlo:
Použití komplexních čísel k výpočtu F n je krásné z matematického hlediska, ale ošklivé z počítačového.

rekurze

Nejzřetelnější řešení, které jste již mnohokrát viděli – nejspíš jako příklad toho, co je rekurze. Pro úplnost to ještě zopakuji. V Pythonu to lze napsat na jeden řádek:

fib = lambda n: fib(n - 1) + fib(n - 2), pokud n > 2 jinak 1

Dobrý:
Velmi jednoduchá implementace, která opakuje matematickou definici
Špatný:
Exponenciální doba běhu. Pro velké n velmi pomalu
Zlo:
Přetečení zásobníku

zapamatování

Rekurzivní řešení má velký problém: překrývající se výpočty. Když se volá fib(n), počítají se fib(n-1) a fib(n-2). Ale když se počítá fib(n-1), bude to nezávisle počítat znovu fib(n-2) - to znamená, že fib(n-2) bude počítáno dvakrát. Pokud budeme pokračovat v uvažování, uvidíme, že fib(n-3) bude počítáno třikrát a tak dále. Příliš mnoho křižovatek.

Proto si stačí výsledky zapamatovat, abyste je znovu nepočítali. Toto řešení spotřebovává čas a paměť lineárním způsobem. V řešení používám slovník, ale lze použít i jednoduché pole.

M = (0: 0, 1: 1) def fib(n): pokud n v M: návrat M[n] M[n] = fib(n - 1) + fib(n - 2) návrat M[n]

(V Pythonu to lze provést také pomocí dekorátoru functools.lru_cache.)

Dobrý:
Prostě přeměňte rekurzi na řešení pro zapamatování. Proměňuje exponenciální dobu provádění na lineární dobu provádění, která spotřebovává více paměti.
Špatný:
Plýtvá spoustou paměti
Zlo:
Možné přetečení zásobníku, jako je rekurze

Dynamické programování

Po vyřešení s memorováním je jasné, že nepotřebujeme všechny předchozí výsledky, ale pouze dva poslední. Také místo toho, abyste začínali na fib(n) a šli zpět, můžete začít na fib(0) a jít vpřed. Následující kód má lineární dobu provádění a pevné využití paměti. V praxi bude rychlost řešení ještě rychlejší, protože nedochází k rekurzivnímu volání funkcí a související práci. A kód vypadá jednodušeji.

Toto řešení je často uváděno jako příklad dynamického programování.

Def fib(n): a = 0 b = 1 pro __ v rozsahu (n): a, b = b, a + b návrat a

Dobrý:
Rychlý pro malé n, jednoduchý kód
Špatný:
Stále lineární běh
Zlo:
Ano, nic zvláštního.

Maticová algebra

A nakonec nejméně pokryté, ale nejsprávnější řešení, které inteligentně využívá čas i paměť. Může být také rozšířen na jakoukoli homogenní lineární sekvenci. Cílem je použít matice. Stačí to jen vidět

A zobecnění tohoto je takové

Dvě hodnoty pro x, které jsme získali dříve, z nichž jedna byl zlatý řez, jsou vlastními hodnotami matice. Dalším způsobem, jak odvodit uzavřený vzorec, je proto použít maticovou rovnici a lineární algebru.

Proč je tedy tato fráze užitečná? Skutečnost, že umocňování lze provést v logaritmickém čase. To se provádí pomocí kvadratury. Pointa je taková

Kde se první výraz používá pro sudé A, druhý pro liché. Zbývá pouze zorganizovat násobení matic a vše je připraveno. Ukazuje se následující kód. Uspořádal jsem rekurzivní implementaci pow, protože je snazší pochopit. Viz iterativní verze zde.

Def pow(x, n, I, mult): """ Vrátí x na mocninu n. Předpokládejme, že I je matice identity, která se násobí násobkem a n je kladné celé číslo """, pokud n == 0: návrat I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix (n): """Vrátí matici identity n x n""" r = seznam(rozsah(n)) return [pro j v r] def matrix_multiply(A, B): BT = seznam(zip(*B) ) return [ pro řádek_a v A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F

Dobrý:
Pevná velikost paměti, logaritmický čas
Špatný:
Kód je složitější
Zlo:
Musíte pracovat s matricemi, i když nejsou tak špatné

Porovnání výkonu

Vyplatí se porovnat pouze variantu dynamického programování a matice. Pokud je porovnáme podle počtu znaků v čísle n, pak se ukáže, že matricový roztok lineárně, zatímco řešení dynamického programování je exponenciální. Praktickým příkladem je výpočet fib(10 ** 6), čísla, které bude mít více než dvě stě tisíc znaků.

N=10**6
Compute fib_matrix: fib(n) má celkem 208988 číslic, výpočet trval 0,24993 sekund.
Vypočítat fib_dynamic: fib(n) má celkem 208988 číslic, výpočet trval 11,83377 sekund.

Teoretické poznámky

Tato poznámka, která přímo nesouvisí s výše uvedeným kódem, je stále zajímavá. Zvažte následující graf:

Spočítejme počet cest délky n od A do B. Například pro n = 1 máme jednu cestu, 1. Pro n = 2 máme opět jednu cestu, 01. Pro n = 3 máme dvě cesty , 001 a 101 Zcela jednoduše lze ukázat, že počet cest délky n z A do B je právě F n . Po napsání matice sousednosti pro graf dostaneme stejnou matici, která byla popsána výše. Z teorie grafů je známý výsledek, že pro danou matici sousednosti A jsou výskyty v A n počet cest délky n v grafu (jeden z problémů zmíněných ve filmu Dobrý Will Hunting).

Proč jsou na okrajích taková označení? Ukazuje se, že když vezmete v úvahu nekonečnou posloupnost symbolů na nekonečné posloupnosti cest v obou směrech v grafu, dostanete něco, čemu se říká „podposuny konečného typu“, což je typ systému symbolické dynamiky. Tento konkrétní posun konečný typ známý jako „posun zlatého poměru“ a je dán souborem „zakázaných slov“ (11). Jinými slovy, dostaneme binární posloupnosti, které jsou nekonečné v obou směrech a žádné z nich nebudou sousedit. Topologická entropie tohoto dynamického systému je rovna zlatému řezu ϕ. Je zajímavé, jak se toto číslo periodicky objevuje v různých oblastech matematiky.

Velmi často se na různých olympiádách vyskytují takové problémy, které se na první pohled dají vyřešit jednoduchým výčtem. Ale když počítáme číslo možnosti, pak okamžitě uvidíme neefektivnost tohoto přístupu: například jednoduchá rekurzivní funkce níže bude spotřebovávat značné zdroje již na 30. Fibonacciho čísle, zatímco na olympiádách je čas řešení často omezen na 1-5 sekund.

int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )

Zamysleme se nad tím, proč se to děje. Například pro výpočet fibo(30) nejprve vypočítáme fibo(29) a fibo(28). Náš program ale zároveň „zapomíná“, že fibo(28) my již vypočítané při hledání fibo(29).

Hlavní chybou tohoto přímého přístupu je, že stejné hodnoty argumentů funkce se počítají mnohokrát – a to jsou operace poměrně náročné na zdroje. Metoda dynamického programování nám pomůže zbavit se opakujících se výpočtů - jedná se o techniku, při které se úloha dělí na obecné a opakující se dílčí úlohy, z nichž každá je řešena pouze 1x - to výrazně zvyšuje efektivitu programu. Tato metoda je podrobně popsána v, jsou zde uvedeny i příklady řešení dalších problémů.

Nejjednodušší způsob, jak zlepšit naši funkci, je zapamatovat si, které hodnoty jsme již vypočítali. K tomu musíme zavést dodatečné pole, které nám poslouží jako jakási „mezipaměť“ pro naše výpočty: před výpočtem nové hodnoty zkontrolujeme, zda již byla spočítána dříve. Pokud jsme počítali, vezmeme připravenou hodnotu z pole, a pokud jsme ji nevypočítali, budeme ji muset vypočítat na základě předchozích a zapamatovat si ji pro budoucnost:

Int cache; int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) ( cache[n] = 1; ) else ( cache[n] = fibo(n - 1) + fibo(n - 2); ) ) vrátit mezipaměť[n]; )

Vzhledem k tomu, že v této úloze zaručeně potřebujeme (N-1)-tou hodnotu pro výpočet N-té hodnoty, nebude těžké vzorec přepsat do iterativní formy - jednoduše vyplníme naše pole v řadě, dokud nedosáhneme požadovaného buňka:

<= n; i++) { cache[i] = cache + cache; } cout << cache;

Nyní si můžeme všimnout, že když počítáme hodnotu F(N) , pak je nám již zaručena hodnota F(N-3) nikdy nebude potřebovat. To znamená, že nám stačí uložit do paměti pouze dvě hodnoty - F(N-1) a F(N-2) . Navíc, jakmile jsme vypočítali F(N) , ukládání F(N-2) ztrácí smysl. Zkusme napsat tyto myšlenky ve formě kódu:

//Dvě předchozí hodnoty: int cache1 = 1; int cache2 = 1; //Nová hodnota int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>iterací ztratí cache2 svou relevanci, tzn. měla by se stát cache1 //Jinými slovy, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //Nechť N=n+1 (číslo, které vypočítáme v další iteraci). Potom n-2=N-3, n-1=N-2, n=N-1. //V souladu s novou realitou přepisujeme hodnoty našich proměnných: cache1 = cache2; cache2 = cache3; ) střih<< cache3;

Zkušený programátor chápe, že výše uvedený kód je obecně nesmysl, protože cache3 se nikdy nepoužívá (okamžitě se zapíše do cache2) a celou iteraci lze přepsat pomocí jediného výrazu:

cache=1; cache=1; for (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Pro ty, kteří nemohou přijít na to, jak kouzlo modulo funguje, nebo jen chtějí vidět nejasnější vzorec, existuje další řešení:

int x = 1; int y = 1; for (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

Pokuste se sledovat provádění tohoto programu: budete přesvědčeni o správnosti algoritmu.

P.S. Obecně existuje jediný vzorec pro výpočet jakéhokoli Fibonacciho čísla, který nevyžaduje žádnou iteraci nebo rekurzi:

Const double SQRT5 = sqrt(5); const double PHI = (SQRT5 + 1) / 2; int fibo(int n)( return int(pow(PHI, n) / SQRT5 + 0,5); )

Ale, jak asi tušíte, háček je v tom, že cena výpočtu mocnin neceločíselných čísel je poměrně velká, stejně jako jejich chyba.