Fibonacci-sorozat

Fibonacci napMa van (november 23.) a Fibonacci nap (újra). Fibonacci középkori matematikus volt, ő tette közismertté a Fibonacci-sorozat-ot. A (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, sorozat igen népszerű azok közében is, akik programozást tanulnak. A sorozat első két eleme 1 és 1 (ha szükséges, akkor nulladik elemmel is dolgozhatunk), és minden további elem az előző két elem összege.

Korábban is blogoltak a kollégáim a témában:

Következzen most az én öt különböző megoldásom Java forráskódja, rövid magyarázattal. Mindegyik a Fibonacci-sorozat első tíz elemét állítja elő.

1. megoldás

Az első megoldás generikus listát épít. Az első két elemet elhelyezi a lista elején ( list.add(1)). Ezek a lista nulladik és első elemei lesznek. Ezután a metódus a maradék 8 elemmel 2-től n-1-ig fiktív indexként hivatkozva az előző két elem összegeként ( list.get(i-1)+list.get(i-2)) index nélkül bővíti a listát.

2. megoldás

A második megoldás a tipikusan nem hatékony rekurzív módszert implementálja. A rekurzív fib() függvény a sorozat egyetlen elemét adja vissza, amit (a függvényt) a ciklus sokszor meghív ahelyett, hogy a ciklus vagy a rekurzió „emlékezne” az előző elemekre.

3. megoldás

A harmadik megoldás funkcionális nyelvi elemeket (Stream API) használ. A folyamba kétdimenziós tömbre történő hivatkozással ( f-> new int[] ), közvetlen hozzárendeléssel/leképezéssel ( map()), kerülnek be a sorozat elemei.

4. megoldás

A negyedik megoldás a Fibonacci-számok zárt alakját használja. Másképpen ez a Binet-formula:

Ezzel a képlettel a sorozat elemei közvetlenül megadhatók, azaz nem szükséges más elemekre való hivatkozás. A ciklus adja meg, hogy a sorozat 1-10-ig indexelt elemei szükségesek.

5. megoldás

Az ötödik megoldás szintén Stream API-t használ. Először előállít egy sorozatot 1-10-ig, amiket a leképezésnél ( map()) inputként használ és alkalmazza rájuk a Binet-formulát. Hagyományos ciklus utasítás nem szükséges.

Eredmény

Mindegyik megoldás a konzolra írja szövegesen az eredményt, azaz a Fibonacci-sorozat első tíz elemét: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Érdemes elemezni a hatékonyság klasszikus három szempontja (időigény/lépésszám, tárigény, bonyolultság) alapján a különböző megoldásokat. Ezek mérésével könnyen kiegészíthetők a fenti metódusok, vagy az azokat meghívó osztályban a vezérlés.

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió és 17-28. óra Objektumorientált programozás alkalmaihoz kötődik.

“Fibonacci-sorozat” bejegyzéshez 2 hozzászólás

Szólj hozzá!