Fibonacci-spirál

Fibonacci logó

Fibonacci logóA Fibonacci-spirál a népszerű Fibonacci-sorozat elemei által meghatározott oldalhosszúságú négyzetekbe rajzolt maximális sugarú negyedkörök megfelelően összeillesztett darabjaiból/sorozatából áll. Sokszor hasonlítják az arany spirálhoz (jól közelíti), amely az aranymetszéshez kötődik.

A Fibonacci-spirál

Vegyük a Fibonacci-sorozat első 10 elemét! Rajzoljuk egymás mellé az alábbi elrendezésben belülről kifelé haladva az 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 oldalhosszúságú négyzeteket (az alábbi ábrán vékony sárgával jelölve). Piros színnel rajzoljuk bele a négyzetekbe a négyzet oldalhosszával megegyező sugarú negyedköröket. A negyedkörök megfelelő elrendezésben folytonos görbét alkotnak, és ezt nevezzük Fibonacci-spirálnak (az alábbi ábrán vastag pirossal jelölve).

Fibonacci-spirál 1

A rajzolás bármeddig folytatható, mert a sorozat végtelen, a négyzetek illeszkednek és az ábra rekurzív, önhasonló. Az alábbi animáció mutatja, hogyan alakul a spirál a nézőpont közelítésével. A viselkedés távolítás során is azonos lenne.

Fibonacci-spirál 2

Korábban blogoltunk már a Fibonacci napról, amelyet minden évben november 23-án ünneplünk. A sorozat első néhány eleméből összeáll a 11.23. és értelmezhető dátumként. Most nem a sorozat elemeinek előállítására fókuszálunk, hanem arra, hogy ezekből felépítsük a Fibonacci-spirált.

Készítsünk Java programot!

Grafikus felületű Java programot készítünk, amely 21 animációs fázisban mutatja be a Fibonacci-sorozat első 10 eleméből álló Fibonacci-spirál felépítését. A rajzolás fázisai:

  • Az 1. fázis a kiindulópontként tekinthető fehér, üres rajzlap. A rajzlap fekvő, mérete 890*550 pixel, amelyre éppen elfér a 10 negyedkörből álló spirál.
  • A 2-11. fázisban megfelelő pozícióba/koordinátákra kerülnek fel az ábra vázát alkotó négyzetek, belülről kifelé haladva. A négyzetek oldalainak hosszúsága a sorozat elemeinek megfelelő. A szomszédos négyzetek különböző színekkel kitöltöttek és mindegyikben megjelenik a sorozat megfelelő eleme.
  • A 12-21. fázisban – szintén belülről kifelé haladva – a négyzetek törlődnek és helyükre a spirált alkotó negyedkörök kerülnek fekete színnel. A 21. fázist tekintjük végeredménynek.

A fázisok kézzel, nyilakkal jelölt (Első, Előző, Következő, Utolsó) vezérlő nyomógombokkal megjeleníthetők, illetve egyben, időzítve animációként is lejátszható a rajzolási folyamat. Az elkészült program működése megfigyelhető az ábrán:

Fibonacci-spirál Java program

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 Java SE szoftverfejlesztő tanfolyamunkon, a szakmai modul Objektumorientált programozás témakörét követő 29-36. óra Grafikus felhasználói felület alkalmain már tudunk egyszerűbb szimulációs programot tervezni, kódolni, tesztelni.

Népesedési világnap

Népesedési világnap logó

Népesedési világnap logóAz ENSZ 1987-ben július 11-ét a népesedési világnappá (World Population Day) nyilvánította. Bolygónk lakossága aznap érte el az 5 milliárdot. További kerek számok voltak: 1999. október 12-én 6 milliárd, 2011. október 30-án 7 milliárd. További kerek számok várhatóak: 2023 – 8 milliárd, 2037 – 9 milliárd, 2057 – 10 milliárd. A KSH elemzése részletes elemzéseket közöl évről-évre a témában, például: 2019-ben, 2018-ban. A worldometer.info weboldalon folyamatosan frissülő kimutatások érhetők el a népességhez globálisan, valamint országonként is: például Magyarország aktuális népesedési adatai.

A népesedési világnap inspirált egy Java program megtervezésére és megírására. A swing GUI-s program megjeleníti a worldometer.info weboldalról kinyerhető adatok alapján régiónként (kontinensenként) az elérhető adatokat 1950-től 2020-ig az alábbiak szerint egy világtérképen.

Az elkészült program

Népesedési világnap Java program

Tervezés

Objektumorientált szemlélettel, MVC architekturális tervezési mintát követünk, angol nyelvű interfész, osztály, változó, objektum, metódus nevekkel. A projekt neve: WorldPopulation, a csomag neve: worldpopulation. Amit lehet, konstansként interfészbe (szeparálva) teszünk és az MVC rétegekhez kötődő osztályok implementálják. A modell minden évszámhoz tárolja a szükséges adatokat, mindezt egyetlen betöltéssel/letöltéssel éri el. A program kliensként hat régióra vonatkozó adatot gyűjt össze, alkalmazkodva a szerver adatforráshoz. A címsorban lévő összesített adat is elérhető közvetlenül a weboldalon, de a kisebb adatforgalom érdekében hasznos inkább a kliensben összesíteni. Mindössze egyetlen eseménykezelés szükséges: a csúszka beállításával megadott évszám alapján frissíteni kell a régiók címkéit és az ablak címsorát. Öröklődés hasznos a feladat megoldása során: egyrészt interfészek, másrészt osztályok között.

Interfészek

Az ősinterfész a WorldPopulationConstants, benne az évszám intervallum MIN_YEAR és MAX_YEAR határaival, valamint a megjeleníthető régiók neveivel tömbben: REGION_NAME_ARRAY. Két utódinterfész épül az ősre: ModelConstants és ViewConstants. Előbbi interfész az adatforráshoz kapcsolódik: URL_COMMON az URL eleje, URL_ARRAY az URL végei régiónként tömbben. Utóbbi interfész a megjelenítéshez kapcsolódik: WORLD_MAP_IMAGE a háttérkép annak WORLD_MAP_RECT méretével együtt, valamint a régiónkénti REGION_RECT_ARRAY téglalapok tömbje a kezdeti pozíciókkal/méretekkel, TITLE a sablon a program címsorához (frissítendő az évszámmal és az összesített népességgel). A megfelelő utódinterfészt mindig implementálja az MVC szerint hozzá illeszkedő osztály.

Osztályok

A belépési pont a WorldPopulation.java fájlban található.

Három összetartozó elemi adatot fog össze egybe a RegionData POJO, ezek name, year, population nevű rendre String, int, long típusú adatok. Például: Európa, 2020, 747643253. Tartalmaz két függvényt: getPopulation(), valamint toString(). Utóbbi HTML formátumban adja vissza a megjelenítendő adatokat.

A JLabel-ből származik az igényekhez alakított RegionLabel osztály. Ennek van előre megadott pozíciója, mérete, betűtípusa, betűmérete, sárga háttérszíne, piros kerete. Ezenkívül a téglalap átlátszó, valamint a benne megjelenő HTML tartalom vízszintesen középre igazított. Némi extra funkció, hogy egérrel megfogva – drag and drop – áthelyezhető, ami a MouseMotionListener egérmozgást figyelő interfész mouseDragged() metódusának felülírásával válik lehetővé. A mozgathatóságáért saját maga felel. Példaként közöljük az osztály teljes forráskódját:

A webről adatokat szerez és tárolja a Model osztály, a java.io és java.net csomagokra építve. Egy példa: a https://www.worldometers.info/world-population/europe-population/ oldal forrásából nyeri ki az osztály az alábbi adatokat:

Ezek parszolását követően elkészül egy optimálisnak tekinthető, generikus listákból álló regionListArray tömb adatszerkezet. A parszolás történhet egyszerű szövegkezeléssel vagy JSON feldolgozással is. Erre épülnek a konstruktorral és vezérlővel összehangoltan működő getter metódusok: getHTML(), getRegionList(), getRegionData(), getPopulation(). A JSON adatforrás feldolgozását most nem részletezzük, de hasonlóról blogoltunk már: Időjárás Budapesten.

A grafikus felhasználói felületet adja a JFrame utód View osztály. Három GUI komponensből áll: pnWorldMap – háttérkép JPanel, lbYear – kiválasztott/aktuális év JLabel, slYear – kiválasztható/görgethető aktuális év JSlider. Izgalmas megoldani egymásra/egymáson elhelyezni a komponenseket. Egy JLayeredPane komponens  DEFAULT_LAYER rétegére kerül a térképet tartalmazó háttérkép, majd a  PALETTE_LAYER rétegére kerül dinamikusan a hat  RegionLabel osztályú/típusú objektum. A csúszka komponens slYearStateChanged() eseménykezelő metódusa vezérlőként megszólítja a modell réteget és a visszakapott adatokkal frissíti a nézet réteget (a címsorban lévő összesítéssel együtt, ezres szeparátorokkal).

Ötlet továbbfejlesztésre

Hat különböző weboldal forráskódjából kell összegyűjteni a megjelenítendő adatokat. Ez 2020-ban régiónként 71 számot jelent és hat régió van. Érdemes lehet olyan adattárolást megvalósítani, amely csökkenti a szerverhez fordulások számát, illetve a letöltendő adatok mennyiségét. Hiszen a múltbeli évekhez kötődő historikus adatok nem változnak. Ha ezekre valamilyen formában a program emlékszik, akkor elegendő az utolsó tárolt évből kiindulva az aktuális évig évenként, régiónként lekérni mindössze 6, 12, 18… számot, a program utolsó futtatásának évéből kiindulva. Ez lényegesen kevesebb lenne, mint a jelenlegi 6*71 lekért szám. A koncepció kulcsszava: inkrementális adatfrissítés. Ha megvalósítjuk az ötletet, akkor figyelni kell arra, hogy az aktuális/utolsó évben az adatok akár másodpercenként is változhatnak.

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 tematikájához kötődik (ha a swing GUI-ra koncentrálunk és az adatok helyi fájlrendszerből elérhetők), és a Java EE szoftverfejlesztő tanfolyam tematikájához kapcsolódik (ha az adatokat közvetlenül a webről olvassuk).

Nemzetközi Pi nap

A Pi-t (π) mindenki ismeri. Talán sokaknak kedvenc története is van a π-vel kapcsolatosan, amelyet iskolában vagy utazásai alatt szerzett. A π Euklidesz geometriájában a kör kerületének és átmérőjének arányát jelöli. A π irracionális szám, azaz végtelen, nem szakaszos tizedestört; másképpen számjegyei között nincs ismétlődés. A π értékével a hétköznapokban 3,14-dal szokás számolni, de a tudomány területén ennél sokkal pontosabb közelítést szokás alkalmazni. A π közelítése az informatikának köszönhetően akár több millió tizedesjegyig is lehetséges (például: S. Memphill: Pi to 1,000,000 places).

A nemzetközi Pi nap alkalmából (március 14) megvalósítottunk néhány – végtelen összeggel és szorzattal – π közelítésre való képletet, algoritmust Java nyelven.

1. Viète-féle sor

Pi-kozelites-Viete

A módszer néhány eredménye: i=5 esetén 3.140331156954752 (2 tizedesjegyre pontos), i=10-nél 3.1415914215112 (5 tizedesjegyre pontos), i=11 esetén 3.1415923455701176 (6 tizedesjegyre pontos).

2. Leibniz-féle sor

Pi-kozelites-Leibniz

A módszer néhány eredménye: a 24. lépéstől stabil 1 tizedesjegyre, a 626. lépéstől stabil 2. tizedesjegyre, a 2453. lépéstől stabil 3 tizedesjegyre (hiszen alternál).

3. Wallis-formula

Pi-kozelites-Wallis

A módszer néhány eredménye: A 38. lépéstől 1, a 986. lépéstől 2, a 2650. lépéstől 3, a 16954. lépéstől már 4 tizedesjegyre pontos.

4. Csebisev-sor

Pi-kozelites-Csebisev

A módszer k=10-re már 8 tizedesjegyig pontos.

A bejegyzéshez tartozó teljes forráskódot – további 8 közelítő módszer implementációjával együtt – 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 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.

Télapó probléma

Télapó-probléma

Télapó-problémaAz operációs rendszerek tervezésének fontos része az ütemezési, erőforrás- és szálkezelési feladatok problémamentes, holtpontmentes megoldása, szinkronizálása, amiről sok ismert szerző publikált már, néhányan közülük angol nyelven: W. Stallings, A. B. Downey, A. S. Tanenbaum, A. S. Woodhull., és magyarul is: Galambos Gábor, Knapp Gábor és Adamis Gusztáv. Ehhez a szakterülethez tartozik több népszerű probléma/esettanulmány, például a vacsorázó bölcsek problémája, illetve a Santa Claus Problem, vagyis a Télapó probléma.

A Télapó probléma specifikációját és megoldását a konkurens programozás eszközeire építve J. A. Trono készítette el (szemaforokkal), amire építve is – és kritizálva is azt – több Java implementáció is elkészült (például: P. Steiner), valamint több programozási nyelv szálkezelési lehetőségeinek összehasonlításáról is publikált J. Hurt és J. B. Pedersen és kliens-szerver elosztott környezetben is áttekintette a lehetőségeket D. Marchant és J. Kerridge. Ismert Haskell, Erlang, Polyphonic C# implementáció is.

A Télapó probléma meghatározása

A Télapó alszik az északi-sarki boltjában és csak akkor ébredhet fel, ha mind a 9 rénszarvas visszatér a dél-csendes-óceáni trópusi szigetén töltött rendes évi nyaralásukról, illetve ha akad néhány manó, akiknek nehézségei vannak az ajándékkészítés során. A 10 manó közül 1 manó problémája nem elég komoly ahhoz, hogy felébressze a Télapót (egyébként sosem aludna), így 3 manó megy egyszerre a Télapóhoz. Amikor a 3 manó problémáit közösen megoldották, akkor mind a 3 manónak vissza kell térnie a többi manóhoz, mielőtt egy újabb manólátogatás megtörténne. Ha a Télapó úgy ébred, hogy 3 manó várja őt a bolt ajtajánál és az utolsó rénszarvas is visszatért a trópusokról, akkor a Télapónak fontosabb, hogy olyan gyorsan elinduljon a szánnal, amilyen gyorsan csak lehetséges – így a manóknak várniuk kell karácsony utánig. Feltételezzük, hogy a rénszarvasok nem akarják elhagyni a trópusokat, ezért az utolsó pillanatig maradnak, amíg csak lehetséges. Lehet, hogy egyáltalán nem is jönnének vissza, ameddig a Télapó fizeti a számlát a paradicsomban… Ez is megmagyarázhatja az ajándékok kiszállításának gyorsaságát, hiszen a rénszarvasok alig várják, hogy visszatérhessenek oda, ahol meleg van. Az utolsóként érkező rénszarvas büntetést kap a Télapótól, mialatt a többi rénszarvas a meleg kunyhóban várja, hogy befogják őket a szán elé.

A Télapó probléma – egyik – megoldása

Találtam egy kb. 10 perces kiváló YouTube videót/animációt (The Santa Claus Problem Thread Synchronization), amely lépésenként felépíti a feladatot, érzékelteti a közben felmerülő problémákat, és megoldást is mutat. Ezt ajánlom december 6-án minden érdeklődő figyelmébe:

Megjegyzés: a videót nem mi készítettük. 2017-től 2020-ig az eredeti linkről ágyaztuk be a blog bejegyzésbe a videót. 2020-ban a videót az eredeti linkről (https://www.youtube.com/watch?v=pqO6tKN2lc4) eltávolították. A blog bejegyzésbe jelenleg beágyazott videó a 2017-es mentett változat.

A feladatot részletekbe menően és komplex módon gondolkodva kell megtervezni, és implementációi komoly nyelvi eszköztárat igényelnek. Érdemes P. Steiner Java megoldását részletesen átnézni, újragondolva – újabb nyelvi eszköztárral – implementálni.

A feladat a Java EE szoftverfejlesztő tanfolyam 1-4. óra: Elosztott alkalmazások, webszolgáltatások, illetve 5-8. óra: Szálkezelés, párhuzamosság alkalmaihoz kapcsolódik.

Fibonacci nap

Fibonacci logó

Fibonacci logóA Fun Holidays – Fun, Wacky & Trivial Holidays weboldal sokféle különleges ünnepnapot listáz. Ezek leírása többnyire vicces, emlékezős, de néhány igazán érdekes, régi-régi hagyományt elevenít fel.

Ma van (november 23.) a Fibonacci nap. 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. Többféle történet is fűződik ehhez, talán az egyik legismertebb a nyúlpárok szaporodásához kötődik.

Honnan származik a Fibonacci nap? A mai nap hh.nn. formátumban 11.23. , és a számjegyek részei a Fibonacci-sorozatnak. Mindössze ennyi, ilyen egyszerű. 😉

A sorozat elemei könnyen előállíthatók néhány változó használatával, ha a kezdő programozó már ismeri a ciklust, mint algoritmikus építőelem – ez az iteratív megoldás. A rekurzív megoldás tipikus rossz megoldásként ismert, lássuk ennek Java megvalósítását:

Ha kiadnám a fenti Java forráskódot papíron ezt egy dolgozatban, zárthelyin, állásinterjú szakmai részén azzal a kérdéssel, hogy mit ír ki a program a képernyőre, akkor bizony sokan bajban lennének. Meg is történt ez már sokszor, tapasztalatból írom. A rekurzió első leszálló ágáig szinte mindenki eljut, de az ott induló első felszálló ágat követően sokan belezavarodnak a részlépések egymásutániságába. A végeredményt szinte mindenki tudja, de itt most arra helyezzük a hangsúlyt, hogy hogyan jutunk el odáig. Persze n=5-re fib(5)=5. Alig fordult még elő, hogy valaki hibátlanul leírta volna az alábbi eredményt:

A megoldás során – emlékeztetek arra, hogy ez atipikus megközelítés – sok-sok redundáns lépés történik. Hiszen például a fib(3)-at tudni kell a fib(4)-hez és a fib(5)-höz is, hiszen fib(4)=fib(2)+fib(3) és fib(5)=fib(3)+fib(4), valamint ebben az implementációban nincs semmilyen emlékezet (puffer, adatszerkezet), amivel a sok feleslegesnek vélhető számítást elkerülhetnénk.

Nyert ügye lehet annak, aki „fejben összerakja” az alábbi fát – akár dinamikusan, menet közben hozzáadva és törölve elemeket – és ebben navigálva (ezt bejárva) válaszolja meg a kérdést:

Fibonacci-sorozat-n=5

Az alábbi animáció segíthet a megértésben: 45 lépésben mutatja be az aktuális részlépést/részfeladatot (leszálló ág) és/vagy az aktuális részeredményt (felszálló ág):

Fibonacci-sorozat-n=5

A Fibonacci-sorozat többféleképpen kapcsolódik a természethez, természeti jelenséghez, növényekhez, állatokhoz (virágszirmok száma, levelek elfordulása, napraforgók magjai, fenyőtoboz pikkelyei, nautilus háza, aranymetszés, zenei hangolás, zeneművek tagolása), felhasználható algoritmusok futási idejének becsléséhez, fa adatszerkezetek építéséhez is. Az aranymetszésről megoszlanak a vélemények: vannak akik szinte mindenben ezt látják (művészet: festészet, szobrászat), mások módszeresen cáfolják ezt (például Falus Róbert: Az aranymetszés legendája, Magyar Könyvklub, 2001, második, javított kiadás, ISBN 963-547-332-X).

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ó alkalmához kötődik.