Fibonacci nap

Fibonacci nap

Fibonacci nap 2018A 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ó alkalomhoz kötődik.

Hello World! másképpen

Hello World! - Piet programozási nyelven

Hello World! - Piet programozási nyelvenA programozási nyelvek tanulásának első lépése a „Hello World!” szintaktikájának megismerése, és egyben teszt arra is, hogy megfelelő-e a fejlesztői környezet telepítése, konfigurálása. Megjelenik-e a „Hello World!” a konzolon, felbukkanó ablakban, önálló ablakban, weblapon, üzenetben? Mit kell ezért tenni? Néhány Java példát nézünk erre.

1. Konzolos megoldás

Ez a kiinduló állapot. Futtatva a programot, a konzolon jelenik meg a szöveg.

2. Swing 1. megoldás

Itt felbukkanó párbeszédablakban jelenik meg a szöveg. A JOptionPane ablaka itt önálló, így nincs olyan szülője/tulajdonosa ( null), ahonnan elveheti a fókuszt.

3. Swing 2. megoldás

Itt egy testre szabott JFrame utód készül, alapvető beállításokkal. Az ablak címsorában jelenik meg a szöveg. Az ablak saját magát példányosítja és főablakként viselkedik, vagyis gondoskodik saját maga láthatóságáról, fókusz- és eseménykezeléséről (utóbbi 2 most nincs).

4. JavaFX megoldás

Itt egy testre szabott  Application utód készül, minimál beállításokkal. Az ablak címsorában jelenik meg a szöveg. Az ablak saját magát példányosítja és főablakként viselkedik.

5. Applet megoldás

Böngészőben fut a testre szabott JApplet utód. A weblapon elfoglalt téglalap alakú területen vízszintesen balra és függőlegesen középen jelenik meg a címke komponensben a szöveg.

6. JSP 1. megoldás

Ez egy JSP weboldal automatikusan generált forráskódja. Böngészőben jelenik meg a szöveg.

7. JSP 2. megoldás

Ez egy JSP weboldal egyszerű direktívával a h1 címsorban.

8. Servlet megoldás

Itt egy szervlet által generált weboldal, amely fixen tartalmazza a szöveget.

9. Atipikus 1. megoldás

„Adatbázisból is lekérdezhető” a szöveg.

10. Atipikus 2. megoldás

Ebben az esetben a Java nyelv által biztosított véletlenszám generáló osztályra támaszkodva állítjuk elő a szöveget. Mivel a random objektum által előállított számok csupán a véletlenség látszatát keltik, de valójában egy algoritmus szerint készülnek, ezért előre teljes pontossággal megjósolható a kimenet. Csupán meg kell találni azt a kezdőértéket, ami után „véletlenül” pont a h, e, l, l, o betűk fognak következni. Megismételve a folyamatot egy másik kezdőértékkel, megkapjuk a w, o, r, l, d  betűket is.

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

A példák a Java SE szoftverfejlesztő tanfolyam, a Java EE szoftverfejlesztő tanfolyam és a Java adatbázis-kezelő tanfolyam több alkalmához is kötődnek (kivéve 4. és 5.).

Hivatkozások a témakörben, amelyek más programozási nyelvek példáit is tartalmazzák:

Java fejtörők – haladó

Java fejtörők

Java fejtörőkJava fejtörők – csapdák, buktató, és szélsőséges esetek. Ez egy könyv címe, amelynek szerzői J. Bloch és N. Gafter. Magyar nyelven a Kiskapu Kft. jelentette meg. A 2010-es magyar kiadás a 2005-ös angol nyelvű kiadás fordítása. A könyv weboldaláról (http://www.javapuzzlers.com), letölthető a 95 fejtörőhöz tartozó mintapéldák gyűjteménye, és elérhető a 270 oldalból minta fejezetként 28 oldalnyi tartalom 9 fejtörővel és azok részletes magyarázataival.

A két részre bontott blog bejegyzés a könyv anyagából válogatva készült el. Az első rész a bevezetés. Ez a második rész, haladó szintű példákkal. Néhány példát továbbfejlesztettem.

7. fejtörő: Mit ír ki program a konzolra?

Kivételkezelés nélkül arra számítanánk, hogy a Hello World! nem jelenik meg a konzolon, mert a wordHard() metódus feltétel nélkül rekurzív módon folyamatosan újrahívja önmagát és az emiatt keletkező StackOverflowError hibával elszáll a program. A kivételkezelés természetesen módosítja a program működését.

Ha azt feltételezzük, hogy minden Throwable utódosztályból futás közben létrehozott objektum kivételkezeléssel elkapható, akkor végtelen ciklusnak tűnik a vezérlés, hiszen a try blokkban hibát okozó metódushívásra a finally blokkban újra ugyanannak a metódusnak a meghívásával reagálunk, amelyik korábban a hibát kiváltotta. Ez a gondolatmenet tévút. A kulcsszó a rekurzív vezérlést megvalósító verem adatszerkezet mérete. Részletes indoklás a blog bejegyzés végén található.

8. fejtörő: Mit ír ki program a konzolra?

Természetesen NullPointerException-re gyanakszunk, pedig a program hibátlanul működik. A kulcsszó a statikus metódusok minősítése, vagyis annak jelölése, hogy melyik osztálytól vagy objektumtól kérjük annak végrehajtását. Részletes indoklás a blog bejegyzés végén található.

9. fejtörő: Mit ír ki a program a konzolra?

Arra számítunk, hogy a kiírás 1999-12, de ehelyett 2000 1-et látunk a konzolon. Tudjuk, hogy a Date osztály jó része már deprecated és ezen próbáltak javítani a Calendar osztállyal. Bár ne tették volna. A kulcsszó az ős dátumkezelést megvalósító API rejtelmeiben van. Részletes indoklás a blog bejegyzés végén található.

10. fejtörő: Mit ír ki a program a konzolra?

Nem tűnik egyértelműen eldönthetőnek a helyzet, ezért szintaktikai hibára gyanakodhatunk. Azonban a forráskód helyes, a program futás közben sem dob kivételt/hibát és a konzolon megjelenik a White. Szokatlan, hogy nagybetűvel konstansokat szokás jelölni, pedig nincs erre utaló final a forráskódban. A kulcsszó a sorrendiségen van, ha ugyanabban a hatókörben/blokkban van azonos nevű változó és típus/osztály. Részletes indoklás a blog bejegyzés végén található.

11. fejtörő: Mit ír ki a program a konzolra?

A program helyes és egyértelműnek tűnik. A konzolra az s1 szövegtömb elemei kerülnek ki véletlenszerűen összekeverve. Finomítsunk a kérdésen. Vajon minden lehetséges permutáció azonos eséllyel fordul elő? Ha ez a kérdés egyáltalán felmerül, akkor a válasz nyilván nem. A kulcsszó most egy kis matematika. Részletes indoklás a blog bejegyzés végén található.

12. fejtörő: Mit ír ki a program a konzolra?

Ez a forráskód nem úgy működik, ahogyan a könyv írja. Meglepő módon nem a [3, 1, 4, 1, 5, 9]-et adja, hanem az [1, 1, 3, 4, 5, 9]-et. Némi indoklás a blog bejegyzés végén található.

Részletes indoklások

  • 7. fejtörő: ha a try blokkban folyamatosan meghívja saját magát a workHard() metódus, akkor előbb-utóbb betelik a verem. Ekkor a finally blokkra kerül a vezérlés, ahonnan újra hívja saját magát a workHard() metódus. Persze követni kell, hogy a rekurzió végrehajtása során a lefelé haladó vagy a felszálló ágon vagyunk és nem mindegy, hogy melyik szinten. A háttérben egy teljes bináris fa bontakozik ki, amelynek mélysége azonos a verem méretével, mélységi korlátjával. Ezt a teljes bináris fát járja be a program, azaz mélységi fabejárás. Egy n mélységű teljes bináris fa elemeinek száma 2n-1. A verem mérete a virtuális gép beállításaitól függ, több ezer mélységű is lehet. Végtelen ciklusról tehát nincs szó. Ugye milyen izgalmas? További részletek a könyv 100-102. oldalán találhatók.
  • 8. fejtörő: a végrehajtás kiértékeli a statikus greet() metódus hívásának minősítő kifejezését, de figyelmen kívül hagyja a kapott értéket. A metódust végrehajthatnánk Null.greet()-ként vagy közvetlenül (minősítés nélkül) meghívva is. További részletek a könyv 122-124. oldalán találhatók.
  • 9. fejtörő: a Date osztály a hónapokat nulla bázissal kezeli, ezért csak 0-11-ig “van értelme”. Számíthatnánk a tömb vagy szöveg túlindexelésénél tapasztaltakhoz hasonlóan kivételre, de nem ez történik. A 12. hónap a következő év első/nulladik hónapját jelöli. Ezért látjuk a konzolon a 2000-et, amit egy kötőjel követ. A Date.getDay() deprecated metódus pedig a dátumobjektumban tárolt nap adott héten (nem hónapban!) elfoglalt helyét adja meg, ami nullával, azaz vasárnappal indul. Tehát a konzolon megjelenő 1 nem a 2000. januárt jelenti, hanem azt, hogy a 2000. január 31. hétfőre esik. Aki ezek után meri használni a régi dátumkezelő API-t, magára vessen. További részletek a könyv 141-143. oldalán találhatók.
  • 10. fejtörő: ha ugyanabban a hatókörben/blokkban van azonos nevű változó és típus/osztály, akkor a változó neve az elsődleges. Ha betartjuk a névadási konvenciókat ( ClassName, objectName, CONSTANT_NAME), akkor nem adódhatnak ilyen gondok. Még egy csavar van: ha az előző elnevezési módosításokat megtesszük, akkor a program a Black-et írja ki a konzolra. További részletek a könyv 161-163. oldalán találhatók.
  • 11. fejtörő: konkrét esetből általánosítunk. 4 elemre a ciklus 4-szer hajtódik végre és minden lépésben kiválaszt egyet a 0 és az 3 indexű elemek közül, ami 44=256-féle lehetséges eredményt ad. Ha az r objektum jól működik, akkor az egyes futások esélye/valószínűsége megegyezik. 4 elemű tömb elemeinek 4!=24 (faktoriális) féle permutációja (lehetséges sorrendje) van. Mivel a 256 nem osztható 24-gyel, így biztos, hogy a shuffle() metódus bizonyos permutációkat gyakrabban állít elő, mint másokat. Általánosan: nn nem osztható n!-sal, ha n>2 egész szám. Vajon mi történik, ha egy 52 lapos pakli kártyát keverünk össze? Vajon milyen érdekességet vet ez fel? Minden poént nem lövünk le itt a blogban. További részletek a könyv 228-232. oldalán találhatók.
  • 12. fejtörő: ez a tankönyv utolsó példája. A felvetett gondolat nagyon frappáns: az összehasonlító rész „ha fej, én nyerek, ha írás, te veszítesz” tüneteitől szenved. További részletek a könyv 232-233. oldalán találhatók.

 

Állásinterjúkon időnként visszaköszönnek hasonló fejtörők, de ezekkel óvatosan kell bánni. Egy programozási nyelv „joghézagainak”, buktatóinak, szélsőséges eseteinek ismerete a könyv szintjét elérő ismeretanyaggal nem lehet elvárt még egy meghirdetett senior pozíció esetén sem. Ezen fejtörők ismerete (vagy nem tudása) egy jelöltről nem árulja el a mindennapokban használható szakmai tudás meglétét/hiányát. De nyilván aki szakmailag folyamatosan fejlődik és mindenféle keretrendszert alkotó forráskódokban turkál, elemez, előbb-utóbb találkozik ezekkel/ilyenekkel.

Tanfolyamainkon nem kifejezetten foglalkozunk hasonló problémákkal, de azért időnként feszegetjük a határokat. Természetesen részletesen indokoljuk, ha előkerül valamilyen hasonló eset. Általánosságban nem célunk, hogy extrém eseteken keresztül, a programozási nyelv gyenge pontjaira kihegyezve oktassuk a Java programozási nyelvet.

Java fejtörők – bevezetés

Java fejtörők

Java fejtörőkJava fejtörők – csapdák, buktató, és szélsőséges esetek. Ez egy könyv címe, amelynek szerzői J. Bloch és N. Gafter. Magyar nyelven a Kiskapu Kft. jelentette meg. A 2010-es magyar kiadás a 2005-ös angol nyelvű kiadás fordítása. A könyv weboldaláról (http://www.javapuzzlers.com), letölthető a 95 fejtörőhöz tartozó mintapéldák gyűjteménye, és elérhető a 270 oldalból minta fejezetként 28 oldalnyi tartalom 9 fejtörővel és azok részletes magyarázataival.

Messze nem mai az anyag, de teljesen örökzöld. Ma is kifejezetten igazán izgalmas átgondolni ezeket a fejtörőket. Biztos vagyok benne, hogy az igazán profiknak is nyújt újdonságot egy-egy fejtörő mögötti részletes magyarázat. Sokszor kiderül az a ravasz és csavaros magyarázatok között, hogy mire gondolt a költő, azaz mi volt/lehetett a Java programozási nyelv tervezése során a szakemberek elképzelése, illetve előfordultak-e kompromisszumok, amiknek persze következményei vannak.

A két részre bontott blog bejegyzés a könyv anyagából válogatva készült el. Ez az első rész, bevezető, alapozó szintű példákkal. A második rész haladó szintű példákat tartalmaz.

1. fejtörő: Mit ír ki program a konzolra?

Két – literálként megadott – egész szám összegét kell kapni. Két egyforma értéket várunk: 66666. Mégsem ezt kapjuk. Az első kiírás 66666-ot, a második 17777-et jelenít meg a konzolon. A kulcsszó a különböző egész literálok megadása. Részletes indoklás a blog bejegyzés végén található.

2. fejtörő: Mit ír ki program a konzolra?

Szöveges literálokat hasonlítunk össze, amelyek egyforma ( length: 10) tartalommal jönnek létre. Döntések eredményeit várjuk, boolean típusú változókat. Négy sorba tördelve ezt kapjuk: false, false, Animals are equal: false, Animals are equal: true. A kulcsszó a művelet végrehajtás sorrendje, másképpen kifejezések kiértékelési sorrendje. Részletes indoklás a blog bejegyzés végén található.

3. fejtörő: Mit ír ki a program a konzolra?

Természetesen a megjegyzéssel nem törődünk és arra gondolunk, hogy a konzolon a Hello World! jelenik meg (a két kiíró utasítás eredménye egyetlen sorban egymás után) és nem is értjük, hogy mi a kérdés. Nyilván a helyzet nem ilyen triviális. A program nem futtatható. A kulcsszó az unikód escape szekvencia (védőkarakter). Részletes indoklás a blog bejegyzés végén található.

4. fejtörő: Mit ír ki a program a konzolra?

Nyilván szintaktikai hibát feltételezünk, de a program hibátlan és futtatva ezt látjuk a konzolon: browser::maximize. A kulcsszó a címke/utasításcímke. Részletes indoklás a blog bejegyzés végén található.

5. fejtörő: Mit ír ki a program a konzolra?

Gyanús a helyzet. Adott egy függvény, aminek kötelezően van visszatérési értéke. Ez rendben van. Tudjuk, hogy a return utasítás kiugrik a függvényből, eljárásból, ciklusból. A kivételkezeléshez kötődő nyelvi kulcsszavakat is ismerjük: try, catch, finally, throw, throws. Ezek működését is ismerjük. Azt feltételezhetjük, hogy a try blokkból kiugrunk true értékkel és a decision() függvényt meghívó main() metódusba visszatérve kiíródik a konzolra, hogy true. Mintha a finally blokk nem is lenne. Nem így történik. A programot futtatva false jelenik meg a konzolon. A kulcsgondolat a finally blokk végrehajtásának vezérléséhez kapcsolódik. Részletes indoklás a blog bejegyzés végén található.

6. fejtörő: Mit ír ki a program a konzolra?

Már biztosan gyanakszunk, de azért a Hello World!-öt várjuk a konzolon. Ehelyett nem jelenik meg semmi. A kulcsszó a puffer ürítés. Részletes indoklás a blog bejegyzés végén található.

Részletes indoklások

  • 1. fejtörő: int típusú literál az 54321, de long típusú literál az 5432l. Az 1 – mint numerikus karakter – nem egyezik meg a kis l betűvel. Tanulság: használjuk nagy L betűt a long típusú literálok végén. További részletek a könyv 11-12. oldalán találhatók.
  • 2. fejtörő: a konkatenálást végző + operátor erősebben kötődik, mint a két objektumreferencia azonosságát eldöntő == operátor. Az első kiírásban látható művelet igazából a második kiírásban látható zárójeles formában kerül végrehajtásra. A harmadik kiírást az magyarázza, hogy a String típusú literálokat memóriacímeik és nem a bennük tárolt karaktersorozat/érték alapján hasonítódnak össze. A helyes gondolatmenet implementálását a negyedik kiírás tartalmazza: (megegyezik-e a két szövegliterál tartalma). További részletek a könyv 29-31. oldalán találhatók.
  • 3. fejtörő: a megjegyzés 3. sorában található \u karaktert 4 db hexadecimális számnak kellene követnie. Ez hiányzik, ami szintaktikai hibát jelent. További részletek a könyv 33-34. oldalán találhatók.
  • 4. fejtörő: az URL-ben lévő : egy ugyanolyan címke, amit a switch utasításban a case ágaknál szokás használni. Ez így is megengedett, de teljesen haszontalan. További részletek a könyv 47-48. oldalán találhatók.
  • 5. fejtörő: a kivételkezelési mechanizmus úgy működik, hogy a try blokkban lévő utasításoktól függetlenül – akár volt kivétel akár nem, akár return utasítást tartalmaz a try blokk – a finally blokk mindenképpen végrehajtódik. Ebben az esetben a kivételkezelési mechanizmus erősebb. További részletek a könyv 77-78. oldalán találhatók.
  • 6. fejtörő: a System.out egy PrintStream osztályú objektum. Többnyire automatikusan ürítik az átmeneti tárolóját az ezt használó utasítások, például System.out.print() és println(). A write() metódus nem üríti ezt a puffert. További részletek a könyv 195-196. oldalán találhatók.

 

További hasonló Java fejtörők, érdekességek

Tanfolyamainkon nem kifejezetten foglalkozunk hasonló problémákkal, de azért időnként feszegetjük a határokat. Természetesen részletesen indokoljuk, ha előkerül valamilyen hasonló eset. Általánosságban nem célunk, hogy extrém eseteken keresztül, a programozási nyelv gyenge pontjaira kihegyezve oktassuk a Java programozási nyelvet.

Ez volt az első rész, bevezető, alapozó szintű példákkal. Jöhet a második rész haladó szintű példákkal.