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.

Péntek 13

Péntek 13

Péntek 13Sokan szerencsés vagy balszerencsés napnak tartják a péntek tizenharmadikát. Évente 1-2-3 alkalommal megtörténik, hogy a hónap 13. napja péntekre esik (minden vasárnap kezdődő hónapban). A hónap 13. napja valamivel valószínűbben péntekre esik, mint a hét bármely más napja. Átlagosan 212,35 naponként fordul elő péntek 13. Előfordulhat két egymást követő hónapban is, de akár 14 hónap is eltelhet két péntek 13 között.

A nap említése sok helyen előfordult: regényekben, filmekben, híres emberek születése vagy halála is esett péntek 13-ra. Átlag alatti közlekedési baleset szokott előfordulni ezeken a napokon – talán mert az emberek óvatosabbak. Kimutatható összefüggést/korrelációt, „péntek 13 hatást” figyeltek meg a tőzsdén is.

Hasznos lehet, ha írunk egy Java programot, amely néhány egymást követő év esetén listázza a konzolra azokat a hónapokat, amikor 13-a péntekre esik.

Tervezés

Legyen egy listFriday13(year) eljárás, amely a paraméterként átvett évben kiírja azokat a hónapokat a konzolra, amelyekben 13-a péntekre esett/esik. Például: 2017: január, október. A hónapok nevei magyar nyelven jelenjenek meg. Az adott év hónapjain végighaladó ciklus legyen hatékony. Optimalizáljunk a ciklus lépésszámára! A ciklus álljon le, ha már talált 3 hónapot (mivel nem lehet több).

1. megoldás

A megoldást a tematika Tömbök témakörében az alábbiak szerint készíthetjük el. Előismeretek: változók, operátorok, ciklusok, programozási tételek, metódusok, tömbök, String összehasonlítás. Az ismert öröknaptár algoritmusokból implementáljuk az egyiket, például:

A listFriday13v1(year) eljárásban az elemi döntés egyszerű: dayOfWeek(year, month, 13).equals("Friday"). Épít az öröknaptárt megvalósító – saját – szöveget visszaadó függvényre. A függvény az algoritmus szerinti kódok előállításához ( centuryCode, monthCode, dayCode) felhasználja a szökőév ( isLeapYear(year)) függvényt, valamint két – konstansnak is tekinthető – névtelen tömböt ( new int[], new String[]).

2. megoldás

A megoldást a tematika Objektumorientált programozás témakörében az alábbiak szerint készíthetjük el. Felhasználjuk eddigi ismereteinket és a JDK beépített dátumkezelő (tároló, formázó) funkcióit (osztályok, interfészek, konstansok, felsorolások).

A listFriday13v2(year) eljárás a Calendar absztrakt osztály konstansait használja fel az elemi döntéshez: date.get(Calendar.DAY_OF_WEEK)==Calendar.FRIDAY. A dátumot a GregorianCalendar konstruktora példányosítja és figyelni kell a 0-bázisú hónapkezelésre. A dátum formázása során ( dfMonth) beállítjuk a megfelelően paraméterezett ( "hu") Locale típusú objektumot és a hónap hosszú nevét kérjük ( "MMMM"). A metódus generikus listába gyűjti a kiválasztott hónapok nevét, amiket végül a String.join() függvény fűz össze a megjelenítéshez.

Eredmény

A vezérlésben egy ciklus 2017-től 2036-ig szervezve az alábbi eredményt adja:

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 a fentiek szerint: 13-16. óra: Tömbök alkalom, illetve 17-28. óra: Objektumorientált programozás alkalom.

Aki gyakorolna a témához kötődően: írjon olyan Java programot, ami listázza a konzolra a 21. század éveit olyan hónapokba csoportosítva, amikor 13-a péntekre esik. Egy év többször is előfordulhat. Például: január – 2006, 2012, 2017, 2023, 2034, 2040, 2045, 2051, 2062, 2068, 2073, 2079, 2090, 2096. A megoldásokat hallgatóinktól az ILIAS-ra, érdeklődőinktől hozzászólásban várjuk.

Húsvétvasárnap

Húsvétvasárnap

HúsvétvasárnapA nyugati kereszténység húsvétvasárnapja legkorábban március 22-ére, legkésőbb április 25-re esik. Másképpen: a húsvét mozgó ünnep, azaz nem esik az év ugyanazon napjára minden évben. Az első niceai zsinat 325-ben úgy határozott, hogy legyen a keresztény húsvét időpontja a tavaszi napéjegyenlőség utáni első holdtöltét követő vasárnap.

A húsvét kiszámítására a legismertebb algoritmus Gauss módszere. A Java implementációban az easterGauss() függvény által elfogadható év paramétert életszerűen lekorlátoztam 1900-2099-ig terjedő évekre, valamint a vezérlés az aktuális és a rákövetkező 19 évben ír ki eredményt:

Az algoritmus részletes magyarázata alapján könnyen kiegészíthető úgy, hogy tetszőleges évre, illetve különböző naptárakra is működjön.

A kapott eredmények megtekinthetők:

A feladat – a kivételkezeléstől eltekintve – a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.