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.