Fibonacciho čísla- toto je séria čísel, v ktorej sa každé ďalšie číslo rovná súčtu dvoch predchádzajúcich: 1, 1, 2, 3, 5, 8, 13, .... Niekedy séria začína od nuly: 0, 1, 1, 2, 3, 5, .... V tomto prípade sa budeme držať prvej možnosti.

Vzorec:

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

Prí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 radu pomocou while cyklu

1. Priraďte premenným fib1 a fib2 hodnoty prvých dvoch prvkov série, to znamená priraďte k premenným jednotky.
2. Opýtajte sa užívateľa na číslo prvku, ktorého hodnotu chce získať. Priraďte číslo premennej n .
3. Vykonajte nasledujúce kroky n - 2 krát, pretože prvé dva prvky už boli zohľadnené:
   1. Pridajte fib1 a fib2 a výsledok priraďte k premennej dočasného úložiska, ako je fib_sum .
   2. Nastavte fib1 na fib2.
   3. Nastavte fib2 na fib_sum .
4. Zobrazte hodnotu fib2.

Poznámka. Ak používateľ zadá 1 alebo 2, telo cyklu sa nikdy nevykoná a zobrazí sa pôvodná hodnota fib2.

fib1=1 fib2=1 n=vstup() n=int(n) i=0, zatiaľ čo i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

Kompaktná verzia kódu:

fib1 = fib2 = 1 n = int(vstup( "Číslo prvku série Fibonacci: ") ) - 2, pričom n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 tlač (fib2)

Výstup Fibonacciho čísel pomocou slučky for

V tomto prípade sa zobrazí nielen hodnota požadovaného prvku Fibonacciho série, ale aj všetky čísla až po ňu. Na tento účel sa výstup hodnoty fib2 umiestni do slučky.

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

Príklad vykonania:

10 1 1 2 3 5 8 13 21 34 55

Rekurzívny výpočet n-tého čísla Fibonacciho radu

1. Ak n = 1 alebo n = 2, vráťte jednotku do volajúcej vetvy, pretože prvý a druhý prvok Fibonacciho série sa rovnajú jednej.
2. Vo všetkých ostatných prípadoch volajte rovnakú funkciu s argumentmi n - 1 a n - 2. Pridajte výsledok dvoch volaní a vráťte ho do volajúcej vetvy programu.

def fibonacci(n) : ak n v (1 , 2 ): návrat 1 návrat fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10) )

Povedzme, že n = 4. Potom budeme volať Fibonacci(3) a Fibonacci(2) rekurzívne. Druhá vráti jednu a prvá bude mať za následok ďalšie dve volania funkcie: Fibonacci(2) a Fibonacci(1). Oba hovory vrátia jeden, spolu teda dva. Volanie Fibonacciho(3) teda vráti číslo 2, ktoré sa pripočíta k číslu 1 z volania Fibonacciho(2). Výsledok 3 sa vráti do hlavnej vetvy programu. Štvrtý prvok Fibonacciho série sú tri: 1 1 2 3.

Programátori Fibonacciho čísel by už mali mať dosť. Príklady ich výpočtu sa používajú všade. Všetko z toho, čo poskytujú tieto čísla najjednoduchší príklad rekurzia. A tiež sú dobrý príklad dynamické programovanie. Je však potrebné ich takto počítať v reálnom projekte? Netreba. Ani rekurzia, ani dynamické programovanie nie sú ideálne možnosti. A nie uzavretý vzorec používajúci čísla s pohyblivou rádovou čiarkou. Teraz vám poviem správnu cestu. Najprv si však prejdime všetky známe riešenia.

Kód je pre Python 3, aj keď by mal fungovať aj pre Python 2.

Najprv mi dovoľte pripomenúť definíciu:

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

A F 1 \u003d F 2 \u003d 1.

uzavretý vzorec

Preskočíme detaily, ale kto chce, môže sa zoznámiť s odvodením vzorca. Myšlienkou je predpokladať, že existuje nejaké x, pre ktoré F n = x n , a potom nájsť x.

Čo robí

Zmenšíme x n-2

Riešime kvadratickú rovnicu:

Odkiaľ vyrastá „zlatý rez“ ϕ=(1+√5)/2. Nahradením pôvodných hodnôt a vykonaním ďalších výpočtov dostaneme:

To je to, čo používame na výpočet F n .

Z __future__ importnej divízie importujte matematiku def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int (PHI ** n / SQRT5 + 0,5)

dobre:
Rýchlo a jednoducho pre malé n
zlé:
Vyžadujú sa operácie s pohyblivou rádovou čiarkou. Väčšie n bude vyžadovať väčšiu presnosť.
zlo:
Použitie komplexných čísel na výpočet F n je krásne z matematického hľadiska, ale škaredé z počítačového.

rekurzia

Najzrejmejšie riešenie, ktoré ste už mnohokrát videli - pravdepodobne ako príklad toho, čo je rekurzia. Pre úplnosť to ešte raz zopakujem. V Pythone to môže byť napísané v jednom riadku:

fib = lambda n: fib(n - 1) + fib(n - 2), ak n > 2 inak 1

dobre:
Veľmi jednoduchá implementácia, ktorá opakuje matematickú definíciu
zlé:
Exponenciálny beh. Pre veľké n veľmi pomaly
zlo:
Pretečenie zásobníka

zapamätanie

Rekurzívne riešenie má veľký problém: prekrývajúce sa výpočty. Keď sa volá fib(n), počítajú sa fib(n-1) a fib(n-2). Ale keď sa počíta fib(n-1), nezávisle znova započíta fib(n-2) - to znamená, že fib(n-2) sa započíta dvakrát. Ak budeme pokračovať v úvahách, uvidíme, že fib(n-3) sa započíta trikrát atď. Príliš veľa križovatiek.

Preto si stačí zapamätať výsledky, aby ste ich znova nepočítali. Toto riešenie spotrebúva čas a pamäť lineárnym spôsobom. V riešení používam slovník, ale dalo by sa použiť aj jednoduché pole.

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

(V Pythone to možno urobiť aj pomocou dekorátora, functools.lru_cache.)

dobre:
Stačí premeniť rekurziu na riešenie na zapamätanie. Premení exponenciálny čas vykonávania na lineárny čas vykonávania, ktorý spotrebuje viac pamäte.
zlé:
Plýtva veľa pamäťou
zlo:
Možné pretečenie zásobníka, napríklad rekurzia

Dynamické programovanie

Po vyriešení s memorovaním je jasné, že nepotrebujeme všetky predchádzajúce výsledky, ale iba posledné dva. Namiesto toho, aby ste začali na fib(n) a šli späť, môžete začať na fib(0) a ísť vpred. Nasledujúci kód má lineárny čas vykonávania a pevné využitie pamäte. V praxi bude rýchlosť riešenia ešte rýchlejšia, keďže neexistujú žiadne rekurzívne volania funkcií a súvisiaca práca. A kód vyzerá jednoduchšie.

Toto riešenie sa často uvádza ako príklad dynamického programovania.

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

dobre:
Rýchly pre malé n, jednoduchý kód
zlé:
Stále lineárny beh
zlo:
Áno, nič zvláštne.

Maticová algebra

A nakoniec najmenej pokryté, ale najsprávnejšie riešenie, ktoré inteligentne využíva čas aj pamäť. Môže sa tiež rozšíriť na akúkoľvek homogénnu lineárnu sekvenciu. Cieľom je použiť matice. Stačí to len vidieť

A toto je zovšeobecnenie

Dve hodnoty pre x, ktoré sme získali skôr, z ktorých jedna bol zlatý rez, sú vlastné hodnoty matice. Preto ďalším spôsobom odvodenia uzavretého vzorca je použitie maticovej rovnice a lineárnej algebry.

Prečo je teda táto fráza užitočná? Skutočnosť, že umocňovanie možno vykonať v logaritmickom čase. To sa vykonáva pomocou kvadratúry. Pointa je taká

Kde sa prvý výraz používa pre párne A, druhý pre nepárne. Zostáva len zorganizovať násobenie matíc a všetko je pripravené. Ukazuje sa nasledujúci kód. Zorganizoval som rekurzívnu implementáciu pow, pretože je ľahšie pochopiť. Pozrite si iteračnú verziu tu.

Def pow(x, n, I, mult): """ Vracia x na mocninu n. Predpokladajme, že I je matica identity, ktorá sa násobí hodnotou mult a n je kladné celé číslo """, ak 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áti n x n maticu identity""" r = zoznam(rozsah(n)) return [pre j v r] def matrix_multiply(A, B): BT = zoznam(zip(*B) ) return [ pre riadok_a v A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F

dobre:
Pevná veľkosť pamäte, logaritmický čas
zlé:
Kód je zložitejší
zlo:
Musíte pracovať s matrikami, hoci nie sú až také zlé

Porovnanie výkonu

Stojí za to porovnať iba variant dynamického programovania a maticu. Ak ich porovnáme podľa počtu znakov v čísle n, potom sa ukáže, že matricový roztok lineárne, zatiaľ čo riešenie dynamického programovania je exponenciálne. Praktickým príkladom je výpočet fib(10 ** 6), čísla, ktoré bude mať viac ako dvestotisíc znakov.

N=10**6
Vypočítajte fib_matrix: fib(n) má celkovo 208988 číslic, výpočet trval 0,24993 sekundy.
Vypočítajte fib_dynamic: fib(n) má celkovo 208988 číslic, výpočet trval 11,83377 sekúnd.

Teoretické poznámky

Táto poznámka, ktorá priamo nesúvisí s vyššie uvedeným kódom, je stále zaujímavá. Zvážte nasledujúci graf:

Spočítajme počet ciest dĺžky n od A do B. Napríklad pre n = 1 máme jednu cestu, 1. Pre n = 2 máme opäť jednu cestu, 01. Pre n = 3 máme dve cesty , 001 a 101 Dá sa celkom jednoducho ukázať, že počet ciest dĺžky n z A do B je práve F n . Po napísaní matice susednosti pre graf dostaneme rovnakú maticu, ktorá bola opísaná vyššie. Z teórie grafov je známy výsledok, že pre danú maticu susednosti A sú výskyty v A n počet dráh dĺžky n v grafe (jeden z problémov spomínaných vo filme Dobrý Will Hunting).

Prečo sú na okrajoch také označenia? Ukazuje sa, že keď vezmete do úvahy nekonečnú postupnosť symbolov na nekonečnej postupnosti ciest v oboch smeroch v grafe, dostanete niečo, čo sa nazýva „podposuny konečného typu“, čo je typ systému symbolickej dynamiky. Tento konkrétny posun konečný typ známy ako „posun zlatého pomeru“ a je daný súborom „zakázaných slov“ (11). Inými slovami, dostaneme binárne postupnosti, ktoré sú nekonečné v oboch smeroch a žiadne z nich nebudú susediť. Topologická entropia tohto dynamického systému sa rovná zlatému rezu ϕ. Je zaujímavé, ako sa toto číslo periodicky objavuje v rôznych oblastiach matematiky.

Veľmi často sa na rôznych olympiádach vyskytujú takéto problémy, ktoré sa na prvý pohľad dajú vyriešiť jednoduchým vymenovaním. Ale ak spočítame číslo možnosti, potom okamžite uvidíme neefektívnosť tohto prístupu: napríklad jednoduchá rekurzívna funkcia nižšie spotrebuje značné zdroje už pri 30. Fibonacciho čísle, kým pri olympiádach je čas riešenia často obmedzený na 1-5 sekúnd.

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

Zamyslime sa nad tým, prečo sa to deje. Napríklad na výpočet fibo(30) najskôr vypočítame fibo(29) a fibo(28). Náš program však zároveň „zabúda“, že fibo(28) my už vypočítané pri hľadaní fibo(29).

Hlavnou chybou tohto priameho prístupu je, že rovnaké hodnoty argumentov funkcie sa počítajú mnohokrát – a to sú operácie dosť náročné na zdroje. Metóda dynamického programovania nám pomôže zbaviť sa opakujúcich sa výpočtov – ide o techniku, pri ktorej je úloha rozdelená na všeobecné a opakujúce sa podúlohy, pričom každá z nich je riešená len 1 krát – to výrazne zvyšuje efektivitu programu. Táto metóda je podrobne popísaná v, sú tam aj príklady riešenia iných problémov.

Najjednoduchší spôsob, ako zlepšiť našu funkciu, je zapamätať si, ktoré hodnoty sme už vypočítali. Aby sme to dosiahli, musíme zaviesť dodatočné pole, ktoré bude slúžiť ako akási „vyrovnávacia pamäť“ pre naše výpočty: pred výpočtom novej hodnoty skontrolujeme, či už bola vypočítaná. Ak sme vypočítali, potom vezmeme hotovú hodnotu z poľa a ak sme ju nevypočítali, budeme ju musieť vypočítať na základe predchádzajúcich a zapamätať si ju pre budúcnosť:

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átiť vyrovnávaciu pamäť[n]; )

Keďže v tejto úlohe zaručene potrebujeme (N-1)-tu hodnotu na výpočet N-tej hodnoty, nebude ťažké prepísať vzorec do iteratívnej formy - jednoducho vyplníme naše pole v riadku, kým nedosiahneme požadovaná bunka:

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

Teraz si môžeme všimnúť, že keď vypočítame hodnotu F(N) , tak hodnota F(N-3) je nám už zaručená nikdy nebude potrebovať. To znamená, že nám stačí uložiť do pamäte iba dve hodnoty - F(N-1) a F(N-2) . Navyše, akonáhle sme vypočítali F(N) , ukladanie F(N-2) stráca zmysel. Skúsme napísať tieto myšlienky vo forme kódu:

//Dve predchádzajúce hodnoty: int cache1 = 1; int cache2 = 1; //Nová hodnota int cache3; pre (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>iteráciou stratí cache2 svoju relevanciu, t.j. mala by sa stať cache1 //Inými slovami, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //Nech N=n+1 (číslo, ktoré vypočítame v ďalšej iterácii). Potom n-2=N-3, n-1=N-2, n=N-1. //V súlade s novou realitou prepisujeme hodnoty našich premenných: cache1 = cache2; cache2 = cache3; ) rez<< cache3;

Skúsený programátor chápe, že vyššie uvedený kód je vo všeobecnosti nezmysel, pretože cache3 sa nikdy nepoužíva (okamžite sa zapíše do cache2) a celú iteráciu je možné prepísať iba pomocou jedného výrazu:

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

Pre tých, ktorí nevedia prísť na to, ako funguje kúzlo modulo, alebo len chcú vidieť menej zrejmý vzorec, existuje ďalšie riešenie:

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

Pokúste sa sledovať vykonávanie tohto programu: budete presvedčení o správnosti algoritmu.

P.S. Vo všeobecnosti existuje jeden vzorec na výpočet akéhokoľvek Fibonacciho čísla, ktorý nevyžaduje žiadnu iteráciu ani rekurziu:

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

Ale, ako asi tušíte, háčik je v tom, že cena za výpočet mocnín neceločíselných čísel je dosť veľká, rovnako ako ich chyba.