streamalism.org

1. Prehľad

V tomto tutoriále sa pozrieme na sériu Fibonacci.

Konkrétne implementujeme tri spôsoby výpočtu n-té z Fibonacciho radu, posledným z nich je riešenie v konštantnom čase.

2. Fibonacciho séria

Fibonacciho séria je séria čísel, v ktorých je každý výraz súčtom dvoch predchádzajúcich výrazov. Sú to prvé dva pojmy 0 a 1.

Napríklad prvých 11 volebných období zo série je 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, a 55.

Z matematického hľadiska postupnosť S_n Fibonacciho čísel je definovaný vzťahom rekurencie:

S (n) = S (n-1) + S (n-2), s S (0) = 0 a S (1) = 1

Teraz sa pozrime na to, ako vypočítať n-té termín série Fibonacci. Tri metódy, na ktoré sa zameriame, sú rekurzívne, iteratívne a používajú Binetov vzorec.

2.1. Rekurzívna metóda

Pri našom prvom riešení si jednoducho vyjadríme vzťah opakovania priamo v Jave:

public static int nthFibonacciTerm (int n) {if (n == 1 || n == 0) {return n; } návrat nthFibonacciTerm (n-1) + nthFibonacciTerm (n-2); }

Ako vidíme, kontrolujeme či n rovná sa 0 alebo 1. Ak je to pravda, potom túto hodnotu vrátime. V každom inom prípade rekurzívne voláme funkciu na výpočet (n-1) th termín a (n-2) th a vrátiť ich sumu.

Aj keď je rekurzívna metóda ľahko implementovateľná, vidíme, že táto metóda robí veľa opakovaných výpočtov. Napríklad za účelom výpočtu 6. termínu, uskutočňujeme hovory na výpočet 5 a 4 termín. Okrem toho výzva na výpočet 5 termín zavolá na výpočet 4 opäť termín. Z tohto dôvodu robí rekurzívna metóda veľa nadbytočnej práce.

Ako sa ukázalo, toto robí jeho časová zložitosť exponenciálna; O (Φn) byť presný.

2.2. Iteratívna metóda

V iteračnej metóde sa môžeme vyhnúť opakovaným výpočtom vykonaným v rekurzívnej metóde. Namiesto toho vypočítame členy série a predchádzajúce dva termíny uložíme, aby sme mohli vypočítať ďalší.

Pozrime sa na jeho implementáciu:

public static int nthFibonacciTerm (int n) {if (n == 0 || n == 1) {return n; } int n0 = 0, n1 = 1; int tempNthTerm; pre (int i = 2; i <= n; i ++) {tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } návrat n1; }

Najskôr skontrolujeme, či je výrazom, ktorý sa má vypočítať 0 termín alebo 1 termín. Ak je to tak, vrátime počiatočné hodnoty. V opačnom prípade vypočítame 2 termín použitie n0 a n1. Potom upravíme hodnoty n0 a n1 premenné na uloženie 1 termín a 2 termín resp. Pokračujeme v opakovaní, kým nevypočítame požadovaný termín.

Iteratívna metóda zabráni opakovanej práci uložením posledných dvoch Fibonacciho výrazov do premenných. Časová a priestorová zložitosť iteračnej metódy je O (n) a O (1) resp.

2.3. Binetov vzorec

Definovali sme iba n-té Fibonacciho číslo z hľadiska dvoch pred ním. Teraz sa pozrieme na Binetov vzorec na výpočet n-té Fibonacciho číslo v konštantnom čase.

Fibonacciho výrazy udržiavajú pomer nazývaný Zlatý pomer označené Φ, grécky znak sa vyslovuje „phi“.

Najprv sa pozrime na to, ako Zlatý pomer sa počíta:

Φ = (1 + √5) / 2 = 1,6180339887 ...

Teraz sa pozrime na Binetov vzorec:

Sn = Φⁿ - (- Φ⁻ⁿ) / √5

V skutočnosti to znamená mali by sme byť schopní získať n-té Fibonacciho číslo iba s nejakou aritmetikou.

Vyjadríme to v Jave:

public static int nthFibonacciTerm (int n) {double squareRootOf5 = Math.sqrt (5); dvojité phi = (1 + štvorcovýRootOf5) / 2; int nthTerm = (int) ((Math.pow (phi, n) - Math.pow (-phi, -n)) / squareRootOf5); návrat nthTerm; }

Najprv vypočítame squareRootof5 a phi a ukladať ich do premenných. Neskôr použijeme Binetov vzorec na získanie požadovaného výrazu.

Pretože tu máme do činenia s iracionálnymi číslami, získame iba približnú hodnotu. Preto budeme musieť držať viac desatinných miest pre vyššie čísla Fibonacci, aby sme zohľadnili chybu zaokrúhľovania.

Vidíme, že vyššie uvedená metóda počíta n-té Fibonacciho výraz v konštantnom čase, príp O (1).

3. Záver

V tomto krátkom článku sme sa pozreli na sériu Fibonacci. Pozreli sme sa na rekurzívne a iteračné riešenie. Potom sme pomocou Binetovho vzorca vytvorili riešenie v konštantnom čase.

Celý zdrojový kód pracovných príkladov je ako vždy k dispozícii na stránkach GitHub.