streamalism.org

1. Pregled

U ovom uputstvu pogledat ćemo Fibonaccijevu seriju.

Konkretno, primijenit ćemo tri načina za izračunavanje n-ti pojam Fibonaccijeve serije, posljednji je rješenje s konstantnim vremenom.

2. Fibonaccijeva serija

Fibonaccijev niz je niz brojeva u kojima je svaki pojam zbroj dva prethodna pojma. To su prva dva pojma 0 i 1.

Primjerice, prvih 11 pojmova iz serije su 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, i 55.

U matematičkom smislu slijed S_n Fibonaccijevih brojeva definiran je relacijom ponavljanja:

S (n) = S (n-1) + S (n-2), sa S (0) = 0 i S (1) = 1

Sada, pogledajmo kako izračunati n-ti pojam Fibonaccijeve serije. Tri metode na koje ćemo se usredotočiti su rekurzivne, iterativne i koriste Binetovu formulu.

2.1. Rekurzivna metoda

Za naše prvo rješenje, izrazimo relaciju ponavljanja izravno u Javi:

javni statički int nthFibonacciTerm (int n) {if (n == 1 || n == 0) {return n; } return nthFibonacciTerm (n-1) + nthFibonacciTerm (n-2); }

Kao što vidimo, provjeravamo je li n jednako je 0 ili 1. Ako je istina, tada vraćamo tu vrijednost. U svakom drugom slučaju, rekurzivno pozivamo funkciju za izračunavanje (n-1) th pojam i (n-2) th rok i vratiti njihov zbroj.

Iako je rekurzivna metoda jednostavna za primjenu, vidimo da ova metoda radi puno ponovljenih izračuna. Na primjer, da bi se izračunao 6. izraz, upućujemo pozive za izračun 5. i Četvrti termin. Štoviše, poziv za izračunavanje 5. Termin poziva za izračun Četvrti opet pojam. Zbog ove činjenice rekurzivna metoda obavlja puno suvišnih poslova.

Kako se čini, ovo čini njegova eksponencijalna vremenska složenost; O (Φn) točnije.

2.2. Iterativna metoda

U iterativnoj metodi možemo izbjeći ponovljene izračune izvedene rekurzivnom metodom. Umjesto toga, izračunavamo uvjete serije i pohranjujemo prethodna dva pojma kako bismo izračunali sljedeći.

Pogledajmo njegovu provedbu:

javni statički int nthFibonacciTerm (int n) {if (n == 0 || n == 1) {return n; } int n0 = 0, n1 = 1; int tempNthTerm; za (int i = 2; i <= n; i ++) {tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } povratak n1; }

Prvo provjeravamo je li pojam koji treba izračunati je 0th pojam ili 1. termin. Ako je to slučaj, vraćamo početne vrijednosti. Inače izračunavamo 2. pojam koji koristi n0 i n1. Zatim mijenjamo vrijednosti n0 i n1 varijable za pohranu 1. pojam i 2. pojam odnosno. Ponavljamo sve dok ne izračunamo traženi rok.

Iterativna metoda izbjegava ponavljanje pohranjujući posljednja dva Fibonaccijeva pojma u varijable. Vremenska složenost i složenost prostora iterativne metode je Na) i O (1) odnosno.

2.3. Binetova formula

Mi smo samo definirali n-ti Fibonaccijev broj u smislu dvojice prije njega. Sada ćemo pogledati Binetovu formulu za izračunavanje n-ti Fibonaccijev broj u konstantnom vremenu.

Fibonaccijevi pojmovi održavaju omjer tzv Zlatni omjer označena sa Φ, grčki znak izgovara se "phi".

Prvo, pogledajmo kako Zlatni omjer izračunava se:

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

Pogledajmo sada Binetova formula:

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

Zapravo, to znači to trebali bismo biti u mogućnosti dobiti n-ti Fibonaccijev broj sa samo nekom aritmetikom.

Izrazimo to na Javi:

javna statička int nthFibonacciTerm (int n) {double squareRootOf5 = Math.sqrt (5); dvostruki phi = (1 + squareRootOf5) / 2; int nthTerm = (int) ((Math.pow (phi, n) - Math.pow (-phi, -n)) / squareRootOf5); return nthTerm; }

Prvo izračunavamo squareRootof5 i phi i pohraniti ih u varijable. Kasnije primjenjujemo Binetovu formulu da bismo dobili traženi pojam.

Budući da ovdje imamo posla s iracionalnim brojevima, dobit ćemo samo aproksimaciju. Slijedom toga, trebat ćemo zadržati više decimalnih mjesta za veće Fibonaccijeve brojeve kako bismo objasnili pogrešku zaokruživanja.

Vidimo da gornja metoda izračunava n-ti Fibonaccijev pojam u stalnom vremenu, ili O (1).

3. Zaključak

U ovom kratkom članku pogledali smo Fibonaccijevu seriju. Gledali smo rekurzivno i iterativno rješenje. Zatim smo primijenili Binetovu formulu kako bismo stvorili rješenje s konstantnim vremenom.

Kao i uvijek, puni izvorni kod radnih primjera dostupan je na GitHub-u.