Fibonacci sorozat Java-ban

1. Áttekintés

Ebben az oktatóanyagban a Fibonacci sorozatot tekintjük meg.

Pontosabban három módszert fogunk bevezetni a n kifejezés a Fibonacci sorozatból, az utolsó állandó idejű megoldás.

2. Fibonacci sorozat

A Fibonacci sorozat egy olyan számsor, amelyben minden tag a két előző kifejezés összege. Az első két kifejezés az 0 és 1.

Például a sorozat első 11 kifejezése az 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, és 55.

Matematikai szempontból a sorrend Sn a Fibonacci-számokat a megismétlődés relációja határozza meg:

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

Most nézzük meg, hogyan kell kiszámítani a n kifejezés a Fibonacci sorozatból. A három módszer, amelyre összpontosítunk, rekurzív, iteratív és Binet képletét használja.

2.1. Rekurzív módszer

Az első megoldásunkhoz egyszerűen fejezzük ki a megismétlődési relációt közvetlenül Java-ban:

public static int nthFibonacciTerm (int n) {if (n == 1 || n == 0) {return n; } visszatér nthFibonacciTerm (n-1) + nthFibonacciTerm (n-2); }

Mint láthatjuk, ellenőrizzük, hogy n egyenlő 0 vagy 1. Ha igaz, akkor visszaadjuk ezt az értéket. Minden más esetben rekurzív módon hívjuk meg a függvényt a (n-1) kifejezés és (n-2) futamidőt, és adja vissza az összegüket.

Bár a rekurzív módszer egyszerűen megvalósítható, azt látjuk, hogy ez a módszer sok ismételt számítást végez. Például a 6. kifejezés, hívást kezdeményezünk a 5 és a 4 kifejezés. Sőt, a felhívás a 5 kifejezés hívást kezdeményez a 4 ismét kifejezés. Emiatt a rekurzív módszer sok felesleges munkát végez.

Mint kiderült, ez teszi időbeli összetettsége exponenciális; O (Φn) hogy pontos legyek.

2.2. Iteratív módszer

Az iteratív módszerben elkerülhetjük a rekurzív módszerrel végzett ismételt számításokat. Ehelyett kiszámoljuk a sorozat feltételeit, és az előző két kifejezést tároljuk a következő kiszámításához.

Vessünk egy pillantást a megvalósítására:

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

Először ellenőrizzük, hogy a kiszámítandó kifejezés az 0 kifejezés vagy 1 kifejezés. Ebben az esetben visszaadjuk a kezdeti értékeket. Ellenkező esetben kiszámoljuk a 2. kifejezés használata n0 és n1. Ezután módosítjuk a n0 és n1 változók a 1 kifejezés és 2. kifejezés ill. Addig folytatjuk az iterációt, amíg ki nem számoltuk a szükséges kifejezést.

Az iteratív módszer elkerüli az ismétlődő munkát azáltal, hogy az utolsó két Fibonacci kifejezést változókba tárolja. Az iteratív módszer időbeli és térbeli összetettsége az Tovább) és O (1) illetőleg.

2.3. Binet képlete

Csak azt definiáltuk n Fibonacci szám az előtte lévő kettő szempontjából. Most megnézzük Binet képletét a n Fibonacci-szám állandó időben.

A Fibonacci kifejezések fenntartják az úgynevezett arányt aranymetszés by -vel jelölve, a görög karakter kiejtette „phi”.

Először nézzük meg, hogyan aranymetszés kiszámítása:

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

Most nézzük meg Binet képlete:

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

Valójában ez azt jelenti képesnek kell lennünk a n Fibonacci szám csak némi számtannal.

Fejezzük ki ezt Java-ban:

public static int nthFibonacciTerm (int n) {double squareRootOf5 = Math.sqrt (5); kettős phi = (1 + négyzetRootOf5) / 2; int nthTerm = (int) ((Math.pow (phi, n) - Math.pow (-phi, -n)) / squareRootOf5); return nthTerm; }

Először kiszámoljuk a squareRootof5 és phi és változókban tárolja őket. Később Binet képletét alkalmazzuk a kívánt kifejezés megszerzéséhez.

Mivel itt irracionális számokkal van dolgunk, csak közelítést kapunk. Következésképpen több tizedesjegyig kell tartanunk a magasabb Fibonacci-számokat a kerekítési hiba elszámolásához.

Látjuk, hogy a fenti módszer kiszámítja a n Fibonacci kifejezés állandó időben, vagy O (1).

3. Következtetés

Ebben a rövid cikkben a Fibonacci sorozatot néztük meg. Rekurzív és iteratív megoldást vizsgáltunk. Ezután Binet képletét alkalmazva létrehoztunk egy állandó idejű megoldást.

Mint mindig, a működő példák teljes forráskódja elérhető a GitHubon.