objektumorientált programozás - címke - Oldal 17 a 17-ből

Java fejtörők – haladó

2023. augusztus 4.2017. június 5. Szerző: Balogh Péter

Java 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?

public class Test {

static void workHard() {

try {

workHard();

}

finally {

workHard();

}

public static void main(String[] args) {

workHard();

System.out.println("Hello World!");

}

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?

public class Null {

static void greet() {

System.out.println("Hello World!");

}

public static void main(String[] args) {

((Null)null).greet();

}

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?

import java.util.Calendar;

import java.util.Date;

public class Test {

public static void main(String[] args) {

Calendar c=Calendar.getInstance();

c.set(1999, 12, 31);

Date d=c.getTime();

System.out.println(c.get(Calendar.YEAR)+"-"+d.getDay());

}

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?

class X {

static class Y {

static String Z="Black";

}

static C Y=new C();

}

class C {

String Z="White";

}

public class Test {

public static void main(String[] args) {

System.out.println(X.Y.Z);

}

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?

import java.util.Random;

public class Test {

private static Random r=new Random();

private static void swap(Object[] a, int i, int j) {

Object temp=a[i];

a[i]=a[j];

a[j]=temp;

}

public static Object[] shuffle(Object[] a) {

for (int i = 0; i < a.length; i++)

swap(a, i, r.nextInt(a.length));

return a;

}

public static void main(String[] args) {

String[] s1={"alma", "körte", "barack", "dinnye"};

for(Object o: shuffle(s1))

System.out.print(o+", ");

System.out.println();

}

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?

import java.util.Arrays;

public class Test {

public static void main(String[] args) {

Integer[] array={3, 1, 4, 1, 5, 9};

Arrays.sort(array,

(Integer i1, Integer i2) -> i1 < i2 ? -1 : (i2 > i1 ? 1 : 0));

System.out.println(Arrays.toString(array));

}

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 2ⁿ-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 4⁴=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: nⁿ 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

2023. január 1.2017. május 20. Szerző: Balogh Péter

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?

public class Test {

public static void main(String[] args) {

System.out.println(12345+54321);

System.out.println(12345+5432l);

}

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?

public class Test {

public static void main(String[] args) {

String pig="length: 10";

String dog="length: "+pig.length();

System.out.println("Animals are equal: "+pig==dog);

System.out.println(("Animals are equal: "+pig)==dog);

System.out.println("Animals are equal: "+(pig==dog));

System.out.println("Animals are equal: "+pig.equals(dog));

}

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?

* Generated by the IBM IDL-to-Java compiler, version 1.0

* from F:\TextRoot\apps\a1\units\include\PolicyHome.idl

* Wednesday, June 17, 1998 6:44:40 o'clock AM GMT+00:00

public class Test {

public static void main(String[] args) {

System.out.print("Hell");

System.out.println("o World!");

}

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?

public class Test {

public static void main(String[] args) {

System.out.print("browser:");

https://www.google.com;

System.out.println(":maximize");

}

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?

public class Test {

private static boolean decision() {

try {

return true;

}

finally {

return false;

}

public static void main(String[] args) {

System.out.println(decision());

}

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?

public class Test {

public static void main(String[] args) {

String hello="Hello World!";

for(int i=0; i<hello.length(); i++)

System.out.write(hello.charAt(i));

}

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

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

Egy matematika érettségi feladat megoldása programozással 2017

2023. augusztus 4.2017. május 11. Szerző: Kaczur Sándor

A 2017-es középszintű matematika érettségi feladatsor 12. feladata inspirált egy Java program megírására. Szükséges hozzá néhány programozási tétel: sorozatszámítás, megszámolás, valamint adatszerkezetként ideális egy kétdimenziós tömb. Érdekes belegondolni, hogy mennyire más lehetne a problémamegoldás, ha programozhatnánk a matematika érettségi vizsgán. A teljes feladatsor a megoldásokkal együtt letölthető az oktatas.hu-ról.

12. feladat

Egy kockával kétszer egymás után dobunk. Adja meg annak a valószínűségét, hogy a két dobott szám összege 7 lesz! Válaszát indokolja!

Matematikai megoldás

A feladat nagyon egyszerű. Két megoldást ismertet a javítási-értékelési útmutató:

Összesen 6 * 6 = 36-féleképpen dobhatunk. Hat olyan dobáspár van, amelyben 7 az összeg: (1; 6), (2; 5), (3; 4), (4; 3), (5; 2) és (6; 1). A keresett valószínűség 6/36-od, vagyis egyhatod.
Bármennyit is dobunk elsőre, ezt a második dobás egyféleképpen egészítheti ki 7-re. Így a második dobásnál a hat lehetséges értékből egy lesz számunkra kedvező. A keresett valószínűség egyhatod.

Közelítő megoldások szimulációval

Egy alkalom két kockadobást jelent egymás után. A dobások sorrendje nem számít (alkalmanként és összességében sem). Minél több alkalommal végezzük el a kockadobásokat, annál jobban megközelítjük a fenti valószínűséget (várható értéket, bővebben: nagy számok törvénye). Az egyhatod közelítő értéke a Java double adattípusával 0.16666666666666666.

1. megoldás

Ha nem akarunk emlékezni a dobásokra, összegükre, csupán megszámolnánk, hogy hány olyan dobáspár van, amelyben 7 az összeg, akkor ehhez mindössze egy számláló ciklus kell, aminek a ciklusmagjában két véletlen kockadobás összegét előállítjuk és növelünk egy számlálót/gyűjtőt, ha az éppen 7. Az eredményt a számláló és a ciklus lépésszámának hányadosa adja meg. Például meghívhatjuk a metódust így: kockadobas1(5000); és kaphatjuk eredményül ezt: 5000 alkalomból 7 összegként 836 alkalommal fordult elő. Valószínűség: 0.1672 . A metódus kivételt dob, ha értelmetlen a paramétere. Íme a metódus Java forráskódja:

static void kockadobas1(int alkalomDb) {

if(alkalomDb<=0)

throw new IllegalArgumentException("Hiba: alkalomDb<=0");

int osszeg7db=0;

for(int i=1; i<=alkalomDb; i++) {

int dobas1=(int)(Math.random()*6+1);

int dobas2=(int)(Math.random()*6+1);

if(dobas1+dobas2==7)

osszeg7db++;

}

System.out.println(

alkalomDb+" alkalomból 7 összegként "+

osszeg7db+" alkalommal fordult elő. Valószínűség: "+

((double)osszeg7db/alkalomDb));

}

2. megoldás

Ha egy 13 elemű egész típusú tömböt használhatunk emlékezetként. Kezdetben 2-től 12-ig indexelve nullázzuk ki, így csoportos gyűjtést tudunk megvalósítani. A nullázás most inicializáló blokkal történt, mert nem sok eleme van a tömbnek (sok elemnél inkább használjunk erre ciklust). A tömb első két elemét nem használjuk semmire. Mi történik a ciklusban? Például dobas1=3 és dobas2=4 esetén a dobasDbTomb[7] elemét növeli (mindegy mi volt ott korábban, de inkrementálódjon). Most több adatot tárolunk, mint amiből megválaszolható a feladatban megfogalmazott konkrét kérdés, de ezt tekinthetjük strukturális tartaléknak.

static void kockadobas2(int alkalomDb) {

if(alkalomDb<=0)

throw new IllegalArgumentException("Hiba: alkalomDb<=0");

int[] dobasDbTomb={-1, -1,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

for(int i=1; i<=alkalomDb; i++) {

int dobas1=(int)(Math.random()*6+1);

int dobas2=(int)(Math.random()*6+1);

dobasDbTomb[dobas1+dobas2]++;

}

System.out.println(

alkalomDb+" alkalomból 7 összegként "+

dobasDbTomb[7]+" alkalommal fordult elő. Valószínűség: "+

((double)dobasDbTomb[7]/alkalomDb));

}

Hasonló, egydimenziós tömbbel történő belső adattárolást megvalósító elosztott alkalmazásról blogoltunk már: Kockadobás kliens-szerver alkalmazás.

3. megoldás

Ez az igazi szimuláció, swing GUI grafikus környezetben, ahogyan az alábbi képernyőképen látható. A megvalósítás kétdimenziós tömböt használ adatszerkezetként. Álljon 7 sorból és 7 oszlopból és legyen i a sor- és j az oszlopindex. A tömb [0][0]-dik elemét nem használjuk semmire. Az első oszlopába ( j=0 és i>0) bekerülhetnek a dobókockán előforduló számok 1-től 6-ig. Hasonlóan az első sorba ( i=0 és j>0) is. Ezek a dobott számok alapján indexek lesznek és az ábrán zöld hátterű cellákba kerültek. A tömb többi eleme kezdetben 0 (nulla), ezek az ábrán fehér hátterű cellák. A szürke hátterű cellák (mellékátló) esetén a dobott számok összege 7 és jól látszik, hogy ez hatféleképpen fordulhat elő a 36-féle eset közül. Például a 2. sor 5. oszlopában lévő szám mutatja, hogy a 10000 alkalomból 274-szer fordult elő az, hogy a dobáspár a (2; 5) lett. A tömb két indexe felcserélhető lenne, mert ez a mellékátlóban lévő számok összegét nem befolyásolja.

A programban kiválasztható néhány alkalomból amit szeretnénk, és a Dob nyomógombra kattintva indul el időzítővel a folyamat. Várakoztatás/menet közben piros színnel kiemelve látszik/megfigyelhető, hogy az éppen aktuális dobás hol növeli az értéket/előfordulást/darabszámot. A képernyőképen befejeződött állapot látható. Az eredményt a szürke cellákban lévő számok összegének és az alkalmak számának hányadosa adja meg. Ezt a háttérbeli kétdimenziós tömbben összesítéssel az alábbi Java forráskód-részlet adja meg:

int osszeg7db=0;

for (int i = 1; i <= 6; i++)

osszeg7db+=dobasTomb[i][7-i];

String eredmeny=alkalomDb+" alkalomból 7 összegként "+

osszeg7db+" alkalommal fordult elő.";

Most lényegesen több adatot tárolunk, mint ami a konkrét válaszhoz kell, de cserébe jól érzékeltethető a csoportos gyűjtés/megszámolás működése. A program grafikus felhasználói felületének felépítését és az eseménykezelés megvalósítását most nem részletezzük.

Eszünkbe juthatna, hogy a program miért dob kétszer 1 és 6 közötti számot egymás után és ezt összegzi, amikor egyetlen 2 és 12 közötti dobással (véletlenszám generálással) megkaphatnánk a dobáspár összegét. Hiszen két db 1 és 6 közötti szám összege mindig 2 és 12 közötti szám. Jó lenne ez az ötlet/megvalósítás? Igen? Nem? Miért? A hozzászólásokhoz várjuk az indoklást.

Ajánljuk matematika érettségi feladat címkénket, mert a témában évről-évre blogolunk.

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 17-28. óra: Objektumorientált programozás alkalmaira épülő 29-36. óra: Grafikus felhasználói felület alkalmaihoz kötődik.

Digitális Témahét 2017

2023. március 20.2017. április 7. Szerző: Kaczur Sándor

A Digitális Témahét 2016-ban indult országos rendezvénysorozat. Fő célja a digitális pedagógia módszertanának népszerűsítése és elterjesztése. A program fontos törekvése, hogy a digitáliskompetencia-fejlesztés az informatikán túl kiterjedjen más tantárgyakra is. A résztvevő pedagógusok és diákok változatos és kreatív iskolai projektek keretében fejleszthetik képességeiket technológiával támogatott tanulás során. A Digitális Témahét rendezvény minden meghirdetett programja ingyenes.

A 2016/2017-es tanévben a rendezvény április 3-7. között valósult meg. Kiemelt témakörök/szempontok:

a multidiszciplináris megközelítés: a matematika, a természet- és mérnöki tudományok, valamint a művészet- és társadalomtudományok együttes megjelenítése;
a tanítás eszközkészletének és módszereinek megújítása;
a pedagógiai innováció, a digitális pedagógia ösztönzése;
az informatikai pályaorientáció.

Meghirdetett eseményünk

2017-ben egy eseményt hirdettem meg Digitális Témahét 2017 rendezvényen.
Helyszín: 1056 Budapest, Váci utca 47., 3. emelet 309-es terem, megközelítés
Dátum és időpont: 2017. április 7. 18:00-21:00-ig
Az esemény ingyenes volt, de a részvétel előzetes regisztrációhoz kötött.

A három órás laborgyakorlat a Brit érmék projektfeladat (forrás: Project Euler #31 Coin sums) megtervezését, négyféle megoldását és tesztelését foglalta magába.

Bevezetés:

Az Egyesült Királyságban 8-féle érme van forgalomban.
Ezek a következők (pound (£) és pence (p)): 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), és £2 (200p).
£2-ot például így lehet kifizetni: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p.
Hányféleképpen lehet kifizetni £2-ot úgy, hogy bármilyen érméből bármennyit felhasználhatunk?
A válasz: 73682.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

1. megoldás: 1×£2

2. megoldás: 2×£1

3. megoldás: 1×£1 + 2×50p

4. megoldás: 4×50p

5. megoldás: 1×£1 + 5×20p

6. megoldás: 2×50p + 5×20p

7. megoldás: 10×20p

8. megoldás: 1×£1 + 1×50p + 2×20p + 1×10p

9. megoldás: 3×50p + 2×20p + 1×10p

10. megoldás: 1×50p + 7×20p + 1×10p

11. megoldás: 1×£1 + 4×20p + 2×10p

12. megoldás: 2×50p + 4×20p + 2×10p

13. megoldás: 9×20p + 2×10p

14. megoldás: 1×£1 + 1×50p + 1×20p + 3×10p

15. megoldás: 3×50p + 1×20p + 3×10p

16. megoldás: 1×50p + 6×20p + 3×10p

17. megoldás: 1×£1 + 3×20p + 4×10p

18. megoldás: 2×50p + 3×20p + 4×10p

19. megoldás: 8×20p + 4×10p

20. megoldás: 1×£1 + 1×50p + 5×10p

21. megoldás: 3×50p + 5×10p

22. megoldás: 1×50p + 5×20p + 5×10p

23. megoldás: 1×£1 + 2×20p + 6×10p

24. megoldás: 2×50p + 2×20p + 6×10p

25. megoldás: 7×20p + 6×10p

26. megoldás: 1×50p + 4×20p + 7×10p

27. megoldás: 1×£1 + 1×20p + 8×10p

28. megoldás: 2×50p + 1×20p + 8×10p

29. megoldás: 6×20p + 8×10p

30. megoldás: 1×50p + 3×20p + 9×10p

31. megoldás: 1×£1 + 10×10p

32. megoldás: 2×50p + 10×10p

33. megoldás: 5×20p + 10×10p

34. megoldás: 1×50p + 2×20p + 11×10p

35. megoldás: 4×20p + 12×10p

36. megoldás: 1×50p + 1×20p + 13×10p

37. megoldás: 3×20p + 14×10p

38. megoldás: 1×50p + 15×10p

39. megoldás: 2×20p + 16×10p

40. megoldás: 1×20p + 18×10p

41. megoldás: 20×10p

42. megoldás: 1×£1 + 1×50p + 2×20p + 2×5p

43. megoldás: 3×50p + 2×20p + 2×5p

44. megoldás: 1×50p + 7×20p + 2×5p

45. megoldás: 1×£1 + 4×20p + 1×10p + 2×5p

46. megoldás: 2×50p + 4×20p + 1×10p + 2×5p

47. megoldás: 9×20p + 1×10p + 2×5p

48. megoldás: 1×£1 + 1×50p + 1×20p + 2×10p + 2×5p

49. megoldás: 3×50p + 1×20p + 2×10p + 2×5p

50. megoldás: 1×50p + 6×20p + 2×10p + 2×5p

51. megoldás: 1×£1 + 3×20p + 3×10p + 2×5p

52. megoldás: 2×50p + 3×20p + 3×10p + 2×5p

53. megoldás: 8×20p + 3×10p + 2×5p

54. megoldás: 1×£1 + 1×50p + 4×10p + 2×5p

55. megoldás: 3×50p + 4×10p + 2×5p

56. megoldás: 1×50p + 5×20p + 4×10p + 2×5p

57. megoldás: 1×£1 + 2×20p + 5×10p + 2×5p

58. megoldás: 2×50p + 2×20p + 5×10p + 2×5p

59. megoldás: 7×20p + 5×10p + 2×5p

60. megoldás: 1×50p + 4×20p + 6×10p + 2×5p

61. megoldás: 1×£1 + 1×20p + 7×10p + 2×5p

62. megoldás: 2×50p + 1×20p + 7×10p + 2×5p

63. megoldás: 6×20p + 7×10p + 2×5p

64. megoldás: 1×50p + 3×20p + 8×10p + 2×5p

65. megoldás: 1×£1 + 9×10p + 2×5p

66. megoldás: 2×50p + 9×10p + 2×5p

67. megoldás: 5×20p + 9×10p + 2×5p

68. megoldás: 1×50p + 2×20p + 10×10p + 2×5p

69. megoldás: 4×20p + 11×10p + 2×5p

70. megoldás: 1×50p + 1×20p + 12×10p + 2×5p

71. megoldás: 3×20p + 13×10p + 2×5p

72. megoldás: 1×50p + 14×10p + 2×5p

73. megoldás: 2×20p + 15×10p + 2×5p

74. megoldás: 1×20p + 17×10p + 2×5p

75. megoldás: 19×10p + 2×5p

76. megoldás: 1×£1 + 4×20p + 4×5p

77. megoldás: 2×50p + 4×20p + 4×5p

78. megoldás: 9×20p + 4×5p

79. megoldás: 1×£1 + 1×50p + 1×20p + 1×10p + 4×5p

80. megoldás: 3×50p + 1×20p + 1×10p + 4×5p

81. megoldás: 1×50p + 6×20p + 1×10p + 4×5p

82. megoldás: 1×£1 + 3×20p + 2×10p + 4×5p

83. megoldás: 2×50p + 3×20p + 2×10p + 4×5p

84. megoldás: 8×20p + 2×10p + 4×5p

85. megoldás: 1×£1 + 1×50p + 3×10p + 4×5p

86. megoldás: 3×50p + 3×10p + 4×5p

87. megoldás: 1×50p + 5×20p + 3×10p + 4×5p

88. megoldás: 1×£1 + 2×20p + 4×10p + 4×5p

89. megoldás: 2×50p + 2×20p + 4×10p + 4×5p

90. megoldás: 7×20p + 4×10p + 4×5p

91. megoldás: 1×50p + 4×20p + 5×10p + 4×5p

92. megoldás: 1×£1 + 1×20p + 6×10p + 4×5p

93. megoldás: 2×50p + 1×20p + 6×10p + 4×5p

94. megoldás: 6×20p + 6×10p + 4×5p

95. megoldás: 1×50p + 3×20p + 7×10p + 4×5p

96. megoldás: 1×£1 + 8×10p + 4×5p

97. megoldás: 2×50p + 8×10p + 4×5p

98. megoldás: 5×20p + 8×10p + 4×5p

99. megoldás: 1×50p + 2×20p + 9×10p + 4×5p

100. megoldás: 4×20p + 10×10p + 4×5p

101. megoldás: 1×50p + 1×20p + 11×10p + 4×5p

102. megoldás: 3×20p + 12×10p + 4×5p

103. megoldás: 1×50p + 13×10p + 4×5p

104. megoldás: 2×20p + 14×10p + 4×5p

105. megoldás: 1×20p + 16×10p + 4×5p

106. megoldás: 18×10p + 4×5p

107. megoldás: 1×£1 + 1×50p + 1×20p + 6×5p

108. megoldás: 3×50p + 1×20p + 6×5p

109. megoldás: 1×50p + 6×20p + 6×5p

110. megoldás: 1×£1 + 3×20p + 1×10p + 6×5p

...

1000. megoldás: 7×20p + 4×5p + 20×2p

1001. megoldás: 1×50p + 4×20p + 1×10p + 4×5p + 20×2p

1002. megoldás: 1×£1 + 1×20p + 2×10p + 4×5p + 20×2p

1003. megoldás: 2×50p + 1×20p + 2×10p + 4×5p + 20×2p

1004. megoldás: 6×20p + 2×10p + 4×5p + 20×2p

1005. megoldás: 1×50p + 3×20p + 3×10p + 4×5p + 20×2p

1006. megoldás: 1×£1 + 4×10p + 4×5p + 20×2p

1007. megoldás: 2×50p + 4×10p + 4×5p + 20×2p

1008. megoldás: 5×20p + 4×10p + 4×5p + 20×2p

1009. megoldás: 1×50p + 2×20p + 5×10p + 4×5p + 20×2p

1010. megoldás: 4×20p + 6×10p + 4×5p + 20×2p

...

10000. megoldás: 1×50p + 1×20p + 4×10p + 10×5p + 17×2p + 6×1p

10001. megoldás: 3×20p + 5×10p + 10×5p + 17×2p + 6×1p

10002. megoldás: 1×50p + 6×10p + 10×5p + 17×2p + 6×1p

10003. megoldás: 2×20p + 7×10p + 10×5p + 17×2p + 6×1p

10004. megoldás: 1×20p + 9×10p + 10×5p + 17×2p + 6×1p

10005. megoldás: 11×10p + 10×5p + 17×2p + 6×1p

10006. megoldás: 1×£1 + 12×5p + 17×2p + 6×1p

10007. megoldás: 2×50p + 12×5p + 17×2p + 6×1p

10008. megoldás: 5×20p + 12×5p + 17×2p + 6×1p

10009. megoldás: 1×50p + 2×20p + 1×10p + 12×5p + 17×2p + 6×1p

10010. megoldás: 4×20p + 2×10p + 12×5p + 17×2p + 6×1p

...

73655. megoldás: 1×10p + 1×5p + 1×2p + 183×1p

73656. megoldás: 3×5p + 1×2p + 183×1p

73657. megoldás: 1×5p + 6×2p + 183×1p

73658. megoldás: 1×10p + 3×2p + 184×1p

73659. megoldás: 2×5p + 3×2p + 184×1p

73660. megoldás: 8×2p + 184×1p

73661. megoldás: 1×10p + 1×5p + 185×1p

73662. megoldás: 3×5p + 185×1p

73663. megoldás: 1×5p + 5×2p + 185×1p

73664. megoldás: 1×10p + 2×2p + 186×1p

73665. megoldás: 2×5p + 2×2p + 186×1p

73666. megoldás: 7×2p + 186×1p

73667. megoldás: 1×5p + 4×2p + 187×1p

73668. megoldás: 1×10p + 1×2p + 188×1p

73669. megoldás: 2×5p + 1×2p + 188×1p

73670. megoldás: 6×2p + 188×1p

73671. megoldás: 1×5p + 3×2p + 189×1p

73672. megoldás: 1×10p + 190×1p

73673. megoldás: 2×5p + 190×1p

73674. megoldás: 5×2p + 190×1p

73675. megoldás: 1×5p + 2×2p + 191×1p

73676. megoldás: 4×2p + 192×1p

73677. megoldás: 1×5p + 1×2p + 193×1p

73678. megoldás: 3×2p + 194×1p

73679. megoldás: 1×5p + 195×1p

73680. megoldás: 2×2p + 196×1p

73681. megoldás: 1×2p + 198×1p

73682. megoldás: 200×1p

A választ tartalmazó fájl letölthető: it-tanfolyam.hu-brit-ermek-megoldas-eredmeny.zip (377 kB, kicsomagolva 4,2 MB).

Feladatok Java nyelven: készíteni kell négy Java programot, amelyik listázza a lehetséges eseteket a konzolra a példa szerinti formátumban!

Az első iteratív megoldás brute force megoldást tartalmazzon! Ez 1473155834 lépésben fog véget érni.
A második iteratív megoldás próbálja csökkenteni a lépésszámot! A cél 3000000 alá eljutni, például: 2886726.
A harmadik megoldás rekurzív legyen!
A negyedik megoldás objektumorientált legyen!

A fokozatosság elvét betartva, sok-sok előismeretre volt szükség a feladatok megoldásához. A két legizgalmasabb rész a hatékonyság szempontjaihoz és a rekurzív megközelítéshez kötődött. Sok-sok kérdés hangzott el. Az i-edik megoldás direkt előállítása (a teljes sorozatból való kiválasztás nélkül) is felmerült. Köszönöm mindenkinek, aki részt vett rendezvényünkön.

A laborgyakorlaton készült forráskódokat tanfolyamaink hallgatói számára – a témához kapcsolódó témakörökhöz, ILIAS-ra feltöltve – tesszük elérhetővé.

CHOO + CHOO = TRAIN

2023. július 5.2017. február 5. Szerző: Kaczur Sándor

Most nem a híres kisvonatról van szó, hanem egy ismert kriptoaritmetikai feladványról. Ebben a feladattípusban egyszerű matematikai műveletek szerepelnek és a különböző betűk különböző számjegyeket jelölnek. Általában többféleképpen megoldhatók: intuíció, ötlet, módszeres próbálkozás, következtetés, kizárás vagy klasszikus behelyettesítés. Ha van megoldás és meg is találunk egyet, akkor a következő kérdés az, hogy van-e még, illetve összesen hány megoldás van?

Íme a feladat:

Érdemes minden megoldás során figyelembe venni a minden számjegyet 0-9-ig végigpróbáló lépések helyett legalább az alábbi öt feltételt:

C >= 5, hiszen CHOO olyan négyjegyű szám, aminek a kétszerese ötjegyű szám,
T = 1, mivel két négyjegyű szám összege 10000 < TRAIN < 20000 (ebben az esetben),
O >= 6, hiszen maradéknak képződnie kell, mert I és N különbözik,
2 <= N < I és
I >= 3 és szintén a maradékképződés miatt.

Esetleg még tovább gondolkodva, felfedezhetünk egyéb összefüggéseket, illetve kizárhatunk egyéb értékeket, így jelentősen csökkenthető egy-egy Java implementáció lépésszáma.

1. megoldás

Ez adatszerkezet nélküli megoldás, így eléggé összetett feltétellel valósul meg a művelet teljesülése (megfelelő helyiértékek használatával) és a különbözőségek vizsgálata.

public static void chooChooTrain1() {

for (int c = 5; c <= 9; c++)

for (int h = 0; h <= 9; h++)

for (int o = 6; o <= 9; o++)

for (int r = 0; r <= 9; r++)

for (int a = 0; a <= 9; a++)

for (int i = 3; i <= 9; i++)

for (int n = 2; n < i; n++)

if((1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n &&

c!=h && c!=o && c!=1 && c!=r && c!=a && c!=i && c!=n &&

h!=o && h!=1 && h!=r && h!=a && h!=i && h!=n &&

o!=1 && o!=r && o!=a && o!=i && o!=n &&

r!=1 && r!=a && r!=i && r!=n &&

a!=1 && a!=i && a!=n &&

i!=1 && i!=n &&

n!=1)

System.out.println(

" "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");

}

2. megoldás

Itt az ellenőrzési feltétel egyszerűbb, mert a különbözőség/egyediség tesztelését áthárítottam a halmazszerűen működő HashSet generikus kollekcióra, építve annak beépített képességére.

public static void chooChooTrain2() {

HashSet<Integer> hs=new HashSet<>();

for (int c = 5; c <= 9; c++)

for (int h = 0; h <= 9; h++)

for (int o = 6; o <= 9; o++)

for (int r = 0; r <= 9; r++)

for (int a = 0; a <= 9; a++)

for (int i = 3; i <= 9; i++)

for (int n = 2; n < i; n++) {

hs.add(c); hs.add(h); hs.add(o);

hs.add(1); hs.add(r); hs.add(a); hs.add(i); hs.add(n);

if(hs.size()==8 &&

(1000*c+100*h+10*o+o)*2 == 10000+1000*r+100*a+10*i+n)

System.out.println(

" "+c+h+o+o+"\n+ "+c+h+o+o+"\n------\n "+1+r+a+i+n+"\n");

hs.clear();

}

Mit gondolsz, melyik megoldás hajtódik végre gyorsabban? Miért?

Mivel a két megoldásnál a ciklusok szervezése megegyezik, így a használt adatszerkezet dönt (hiszen annak konstrukciós és szelekciós, azaz karbantartási műveletei vannak). Az 1. megoldás a gyorsabb, mert nem használ adatszerkezetet. A 2. megoldás lényegesen lassabban fut, mert a generikus kollekció műveletei miatt az automatikus szemétgyűjtő tevékenység erősen igénybe vett. A különbség nagyságrendileg 15-szörös.

A feladatnak két megoldása van: 5466 + 5466 = 10932 és 5488 + 5488 = 10976.

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

Akinek kedve támadt, lásson hozzá hasonló feladatokhoz:

SEND + MORE = MONEY
6 * KAYAK = SPORT
2 * MOST = TOKYO
CROSS + ROADS = DANGER
FORTY + TEN + TEN = SIXTY
mathsisfun.com – Algebra Puzzles
cryptarithms.awardspace.us – Crack-a-Puzzle Online – Puzzles Menu
www.campusgate.co.in – Cryptoarithmetic problem with explanation

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalomhoz, illetve a 21-24. óra: Objektumorientált programozás, 2. rész alkalomhoz kötődik.