programozási tételek - címke

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

2023. május 12.2023. május 9. Szerző: Kaczur Sándor

A 2023-as középszintű matematika érettségi feladatsorból az 5. feladat alkalmasnak bizonyult arra, hogy a programozás eszköztárával oldjuk meg. Rögtön többféleképpen is, hogy összehasonlíthatóak legyenek egymással. Érdekes belegondolni, hogy mennyire más lehetne a problémamegoldás, ha programozhatnánk a matematika érettségi vizsgán. A teljes feladatsor letölthető az oktatas.hu-ról.

5. feladat

Adja meg a 420 és az 504 legnagyobb közös osztóját! Megoldását részletezze!

Íme kulcsszavakban, mit érdemes átgondolni a megoldás előtt: számelmélet alaptétele, prímfelbontás (prímtényezős felbontás, faktorizáció), osztópár, prímek szorzata, prímtényezők szorzata, kanonikus alak, euklideszi algoritmus.

1. megoldás

private void lnko1(int aa, int bb) {

if(aa>0 && bb>0) {

int a=Math.max(aa, bb), b=Math.min(aa, bb), m=a%b;

while(m!=0) {

//System.out.println(a+" = "+a/b+" * "+b+" + "+m);

a=b;

b=m;

m=a%b;

}

//System.out.println(a+" = "+a/b+" * "+b+" + "+m);

int lnko=b;

System.out.println("lnko ("+aa+"; "+bb+") = "+lnko);

}

else

System.out.println("Mindkét számnak pozitívnak kell lennie!");

}

Az első megoldás az euklideszi algoritmus alkalmazása. A metódus paraméterezhető. Pozitív paramétereket vár és képes kiírni a konzolra a két szám legnagyobb közös osztóját. A módszer alapötlete: a legnagyobb közös osztó nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Ezzel csökken a nagyobb szám, így a cserék ismétlésével egyre kisebb számokat kapunk, amíg a két szám egyenlővé nem válik. Ez az eddigi számpároknak, így az eredeti számpárnak is a legnagyobb közös osztója. Az eredményt az utolsó nem nulla maradék while(m!=0) adja meg int lnko=b;. Az algoritmus lépésszáma csökkenthető, ha a>b, de ennek ellenőrzése nélkül is működik. Mivel a feladat kéri a megoldás részletezését, így aktiválva a megjegyzésbe tett forráskódokat, a kiírásból könnyen érthető, mi és hogyan történik:

504 = 1 * 420 + 84

420 = 5 * 84 + 0

lnko (420; 504) = 84

A konkrét esetben a metódus eredménye: lnko (420; 504) = 84. Nagyobb számok esetében „beszédesebb” a program kiírása, több lépésben írja ki a megoldáshoz vezető utat, ezért érdemes többféle paraméterrel is tesztelni a metódust.

2. megoldás

private List<Integer> primtenyezok(int n) {

List<Integer> primtenyezokLista=new ArrayList<>();

if(n>0)

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

while(n%i==0) {

//System.out.printf("%5d | %d\n", n, i);

primtenyezokLista.add(i);

n/=i;

}

//System.out.printf("%5d | \n", n);

return primtenyezokLista;

}

private String primtenyezokSzorzatkent(

List<Integer> primtenyezok) {

return primtenyezok.stream().map(i->i.toString()).

collect(Collectors.joining(" * "));

}

private void lnko2(int a, int b) {

if(a>0 && b>0) {

List<Integer> aPrimtenyezok=primtenyezok(a);

//System.out.println(a+" = "+

// primtenyezokSzorzatkent(aPrimtenyezok));

List<Integer> bPrimtenyezok=primTenyezok(b);

//System.out.println(b+" = "+

// primtenyezokSzorzatkent(bPrimtenyezok));

List<Integer> kozosPrimtenyezok=new ArrayList<>();

aPrimtenyezok.stream().distinct().forEach((prim)->{

long aPrimDb=aPrimtenyezok.stream().filter(p->p==prim).count();

long bPrimDb=bPrimtenyezok.stream().filter(p->p==prim).count();

long minEgyediPrimDb=Math.min(aPrimDb, bPrimDb);

if(minEgyediPrimDb>0)

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

kozosPrimtenyezok.add(prim);

});

int lnko=kozosPrimtenyezok.stream().reduce(1, (p1, p2)->p1*p2);

System.out.println("lnko ("+a+"; "+b+") = "+

/*primtenyezokSzorzatkent(kozosPrimtenyezok)+" = "+*/lnko);

}

else

System.out.println("Mindkét számnak pozitívnak kell lennie!");

}

A második megoldás a prímtényezős felbontásokon alapul. Mindkét szám esetén gyűjtsük össze listában ezeket, majd vegyük a két lista közös részét. (Ha lista helyett halmazok lennének, akkor metszet programozási tétel lenne.) A generikus listákba prímszámok kerülnek és bármelyik többször is előfordulhat. (Ezért most a leghosszabb közös részsorozat(ok) előállítása szükséges.) Addig osztjuk a számot 2-vel, amíg lehet, utána következik a többi prímosztó, amíg vannak. Érdemes több metódusra szétosztani a megoldást, mert jóval áttekinthetőbb és karbantarthatóbb Java forráskódot eredményez. A beszédes változó, objektum és metódusnevek is segítenek a megértésben. A második megoldás természetesen ugyanazt az eredményt adja, mint az első megoldás. Aktiválva a megjegyzésbe tett forráskódokat, a kiírásból most is könnyen érthetővé válik (középiskolás matematikaóra-szerűen), mi és hogyan történik:

420 | 2

210 | 2

105 | 3

35 | 5

7 | 7

1 |

420 = 2 * 2 * 3 * 5 * 7

504 | 2

252 | 2

126 | 2

63 | 3

21 | 3

7 | 7

1 |

504 = 2 * 2 * 2 * 3 * 3 * 7

lnko (420; 504) = 2 * 2 * 3 * 7 = 84

Kanonikus alakban: 420 = 2² * 3 * 5 * 7, 504 = 2³ * 3² * 7, így lnko (420; 504) = 2² * 3 * 7. Azaz összeszorozzuk a közös prímtényezőket az előforduló legkisebb hatványon.
A megoldás erősen épít a generikus kollekciók esetén jól használható Stream API lambda kifejezéseire. Ezeket most nem részletezem, helyette ajánlom a szakmai blogból a lambda kifejezés címkét.

Érdemes átgondolni

Nagy prímszámok esetén az euklideszi algoritmus nem hatékony. Az algoritmus végrehajtása kifejezetten lassú például a Fibonacci-számok esetén. A prímtényezőkre bontás feltételezett bonyolultságát számos kriptográfiai algoritmus használja ki. Vannak különleges esetek is, például: egyforma számok, az egyik szám 1, a két szám egymás többszöröse.
A feladat nem kérte a legkisebb közös többszörös meghatározását, de ha tudjuk a lnko(a, b)-t, akkor abból könnyen adódik a lkkt(a, b)=a*b/lnko(a, b).
A legnagyobb közös osztó tulajdonságait megismerve az euklideszi algoritmus könnyen optimalizálható. Számos esetben ellenőrzést végezhetünk, illetve triviális alapesetek is vannak. Létezik kiterjesztett euklideszi algoritmus is.

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

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

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

Digitális Témahét 2023

2023. március 31. Szerző: Kaczur Sándor

A Digitális Témahét 2016-ban indult országos rendezvénysorozat. Fő célja, hogy a digitális eszközökkel támogatott projektpedagógia és innovatív pedagógiai módszerek terjesztésén keresztül. 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 2021/2022-es tanévben 811 hazai és külhoni intézmény regisztrált, és 115 ezer tanuló vett részt egy vagy több programon, digitális projektben.

A 2022/2023-as tanévben a rendezvény március 27-31. között valósult meg. Kiemelt témák:

digitális állampolgárság;
a digitalizáció jelene és jövője;
a technológia eszközei és alkalmazásai;
az algoritmikus gondolkodás és programozás mint az alkotás eszközei;
digitális biztonság és digitális esélyteremtés.

Rendezvényünk plakátja

Az it-tanfolyam.hu 2023-ban is csatlakozott a rendezvénysorozathoz. Oktatóink meghirdettek hét programot, amelyekre 2023. március 31-én 18:00-21:00 óráig került sor.

Köszönöm oktató kollégáimnak, hogy örömmel csatlakoztak. A résztvevőinknek is köszönjük, hogy ellátogattak hozzánk. Mindannyian jól éreztük magunkat: közel 40-en voltunk jelen személyesen és online is közel 30-an követtek bennünket. Igazán tartalmas programot állítottunk össze. Valódi flow-élményt jelentett. Tanfolyamunk hallgatói és az érdeklődők számára is tudtunk újat mutatni. A programok közötti szünetek lehetőséget adtak a kérdésekre, az ismerkedésre. A kiállított posztereink körül is többször alakult ki csoportosulás, kötetlen beszélgetés. Idén is szívesen csatlakoztunk a rendezvénysorozathoz és szívesen emlékszünk majd vissza rá.

Tankocka – Keresztrejtvény: programozási tételek

2022. október 22.2022. augusztus 1. Szerző: Kaczur Sándor

Folytatjuk Tankockák blog bejegyzés sorozatunkat. A feladatban a 12 db programozási tétel nevének beírásával meg kell fejteni a keresztrejtvényt. Ez a témakör főként a Java SE szoftverfejlesztő tanfolyamunkhoz kötődik. A programozási tételek olyan alapfeladatok, amelyek univerzálisan használható építőkövek és bizonyított, hogy mindegyikük helyes. A programozási tételek fontosak a programozáshoz szükséges gondolkodásmód kialakításához, formálásához.

A programozási tételeket csoportosíthatjuk: elemi és összetett. Az elemi programozási tételek közös jellemzője, hogy bemenetük egy sorozat és kimenetük egyetlen adat (ami nem feltétlenül része/eleme a sorozatnak). Az összetett programozási tételek már több sorozattal működnek: lehet több bemenetük és több kimenetük is. Például egy bemeneti sorozatból előállítanak 2-3-több (nem biztos, hogy előre tudjuk, hogy hány darab) kimeneti sorozatot (vagy éppen fordítva). Más is lehet a csoportosítás alapja, például egyediek a sorozat elemei vagy lehetnek azonos elemek a sorozatban, számít az elemek sorrendje vagy nem. No vajon mi a keresztrejtvény megfejtése?

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

2023. január 3.2022. május 3. Szerző: Kaczur Sándor

A 2022-es középszintű matematika érettségi feladatsor eléggé egyszerű volt, de azért a 6. feladata inspirált arra, hogy a programozás eszköztárával oldjuk meg ezt a feladatot. Szükséges hozzá a megszámolás programozási tétel. Többféle megoldás/megközelítés (iteratív és rekurzív) is előkerül. É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.

6. feladat

Egy feleletválasztós teszt 5 kérdésből áll, minden kérdésnél négy válaszlehetőség van. Hányféleképpen lehet az 5 kérdésből álló tesztet kitölteni, ha minden kérdésnél egy választ kell megjelölni?

1. megoldás

static void feladat6Megoldas1() {

System.out.println((int)Math.pow(4, 5));

}

Rögtön tudjuk, hogy ez kombinatorika, n elem k-ad osztályú ismétléses variációja, amelynek paraméterei: n=4, k=5. A hatványozás azonosságainak ismeretében fejből is tudjuk a megoldást: 4⁵=2¹⁰=1024. A Java forráskód elvégzi a hatványozást. A Math.pow() függvény általánosabb, mint amire most szükségünk van. Fogad double valós paramétereket és double típusú értékkel tér vissza. Ezért hasznos az (int) explicit típuskényszerítés.

Másképpen: négy elemű halmazból öt elemet kiválasztunk és ezeket sorba rendezzük (permutáljuk) és egy elemet egy csoportban akár ötször is felhasználhatunk. Számít a sorrend. A lehetséges variációk száma: 1024.

2. megoldás

static int ismetlesesVariacio(int n, int k) {

return (int)(Math.pow(n, k));

}

static void feladat6Megoldas2() {

System.out.println(ismetlesesVariacio(4, 5));

}

Ha hasznos lenne egy általános metódus az ismétléses variáció kiszámítására, akkor ez egy tipikus megoldás lehet erre. Kiegészítendő még a két paraméter előjelének ellenőrzésével.

3. megoldás

static void feladat6Megoldas3() {

for(char k1='a'; k1<='d'; k1++)

for(char k2='a'; k2<='d'; k2++)

for(char k3='a'; k3<='d'; k3++)

for(char k4='a'; k4<='d'; k4++)

for(char k5='a'; k5<='d'; k5++)

System.out.print(""+k1+k2+k3+k4+k5+" ");

System.out.println();

}

Ha a megértést segíti, akkor a teljes leszámolás (brute force) módszerével, egymásba ágyazott ciklusokkal könnyen kiírathatjuk a konzolra az 1024 db különböző válaszlehetőséget. A k-val kezdődő sorszámozott ciklusváltozók jelölik az öt kérdést, azon belül az 'a'-tól 'd'-ig karakterek adják a válaszlehetőségeket. Eredményül ezt kapjuk (görgethető):

100

101

102

103

aaaaa aaaab aaaac aaaad aaaba aaabb aaabc aaabd aaaca aaacb

aaacc aaacd aaada aaadb aaadc aaadd aabaa aabab aabac aabad

aabba aabbb aabbc aabbd aabca aabcb aabcc aabcd aabda aabdb

aabdc aabdd aacaa aacab aacac aacad aacba aacbb aacbc aacbd

aacca aaccb aaccc aaccd aacda aacdb aacdc aacdd aadaa aadab

aadac aadad aadba aadbb aadbc aadbd aadca aadcb aadcc aadcd

aadda aaddb aaddc aaddd abaaa abaab abaac abaad ababa ababb

ababc ababd abaca abacb abacc abacd abada abadb abadc abadd

abbaa abbab abbac abbad abbba abbbb abbbc abbbd abbca abbcb

abbcc abbcd abbda abbdb abbdc abbdd abcaa abcab abcac abcad

abcba abcbb abcbc abcbd abcca abccb abccc abccd abcda abcdb

abcdc abcdd abdaa abdab abdac abdad abdba abdbb abdbc abdbd

abdca abdcb abdcc abdcd abdda abddb abddc abddd acaaa acaab

acaac acaad acaba acabb acabc acabd acaca acacb acacc acacd

acada acadb acadc acadd acbaa acbab acbac acbad acbba acbbb

acbbc acbbd acbca acbcb acbcc acbcd acbda acbdb acbdc acbdd

accaa accab accac accad accba accbb accbc accbd accca acccb

acccc acccd accda accdb accdc accdd acdaa acdab acdac acdad

acdba acdbb acdbc acdbd acdca acdcb acdcc acdcd acdda acddb

acddc acddd adaaa adaab adaac adaad adaba adabb adabc adabd

adaca adacb adacc adacd adada adadb adadc adadd adbaa adbab

adbac adbad adbba adbbb adbbc adbbd adbca adbcb adbcc adbcd

adbda adbdb adbdc adbdd adcaa adcab adcac adcad adcba adcbb

adcbc adcbd adcca adccb adccc adccd adcda adcdb adcdc adcdd

addaa addab addac addad addba addbb addbc addbd addca addcb

addcc addcd addda adddb adddc adddd baaaa baaab baaac baaad

baaba baabb baabc baabd baaca baacb baacc baacd baada baadb

baadc baadd babaa babab babac babad babba babbb babbc babbd

babca babcb babcc babcd babda babdb babdc babdd bacaa bacab

bacac bacad bacba bacbb bacbc bacbd bacca baccb baccc baccd

bacda bacdb bacdc bacdd badaa badab badac badad badba badbb

badbc badbd badca badcb badcc badcd badda baddb baddc baddd

bbaaa bbaab bbaac bbaad bbaba bbabb bbabc bbabd bbaca bbacb

bbacc bbacd bbada bbadb bbadc bbadd bbbaa bbbab bbbac bbbad

bbbba bbbbb bbbbc bbbbd bbbca bbbcb bbbcc bbbcd bbbda bbbdb

bbbdc bbbdd bbcaa bbcab bbcac bbcad bbcba bbcbb bbcbc bbcbd

bbcca bbccb bbccc bbccd bbcda bbcdb bbcdc bbcdd bbdaa bbdab

bbdac bbdad bbdba bbdbb bbdbc bbdbd bbdca bbdcb bbdcc bbdcd

bbdda bbddb bbddc bbddd bcaaa bcaab bcaac bcaad bcaba bcabb

bcabc bcabd bcaca bcacb bcacc bcacd bcada bcadb bcadc bcadd

bcbaa bcbab bcbac bcbad bcbba bcbbb bcbbc bcbbd bcbca bcbcb

bcbcc bcbcd bcbda bcbdb bcbdc bcbdd bccaa bccab bccac bccad

bccba bccbb bccbc bccbd bccca bcccb bcccc bcccd bccda bccdb

bccdc bccdd bcdaa bcdab bcdac bcdad bcdba bcdbb bcdbc bcdbd

bcdca bcdcb bcdcc bcdcd bcdda bcddb bcddc bcddd bdaaa bdaab

bdaac bdaad bdaba bdabb bdabc bdabd bdaca bdacb bdacc bdacd

bdada bdadb bdadc bdadd bdbaa bdbab bdbac bdbad bdbba bdbbb

bdbbc bdbbd bdbca bdbcb bdbcc bdbcd bdbda bdbdb bdbdc bdbdd

bdcaa bdcab bdcac bdcad bdcba bdcbb bdcbc bdcbd bdcca bdccb

bdccc bdccd bdcda bdcdb bdcdc bdcdd bddaa bddab bddac bddad

bddba bddbb bddbc bddbd bddca bddcb bddcc bddcd bddda bdddb

bdddc bdddd caaaa caaab caaac caaad caaba caabb caabc caabd

caaca caacb caacc caacd caada caadb caadc caadd cabaa cabab

cabac cabad cabba cabbb cabbc cabbd cabca cabcb cabcc cabcd

cabda cabdb cabdc cabdd cacaa cacab cacac cacad cacba cacbb

cacbc cacbd cacca caccb caccc caccd cacda cacdb cacdc cacdd

cadaa cadab cadac cadad cadba cadbb cadbc cadbd cadca cadcb

cadcc cadcd cadda caddb caddc caddd cbaaa cbaab cbaac cbaad

cbaba cbabb cbabc cbabd cbaca cbacb cbacc cbacd cbada cbadb

cbadc cbadd cbbaa cbbab cbbac cbbad cbbba cbbbb cbbbc cbbbd

cbbca cbbcb cbbcc cbbcd cbbda cbbdb cbbdc cbbdd cbcaa cbcab

cbcac cbcad cbcba cbcbb cbcbc cbcbd cbcca cbccb cbccc cbccd

cbcda cbcdb cbcdc cbcdd cbdaa cbdab cbdac cbdad cbdba cbdbb

cbdbc cbdbd cbdca cbdcb cbdcc cbdcd cbdda cbddb cbddc cbddd

ccaaa ccaab ccaac ccaad ccaba ccabb ccabc ccabd ccaca ccacb

ccacc ccacd ccada ccadb ccadc ccadd ccbaa ccbab ccbac ccbad

ccbba ccbbb ccbbc ccbbd ccbca ccbcb ccbcc ccbcd ccbda ccbdb

ccbdc ccbdd cccaa cccab cccac cccad cccba cccbb cccbc cccbd

cccca ccccb ccccc ccccd cccda cccdb cccdc cccdd ccdaa ccdab

ccdac ccdad ccdba ccdbb ccdbc ccdbd ccdca ccdcb ccdcc ccdcd

ccdda ccddb ccddc ccddd cdaaa cdaab cdaac cdaad cdaba cdabb

cdabc cdabd cdaca cdacb cdacc cdacd cdada cdadb cdadc cdadd

cdbaa cdbab cdbac cdbad cdbba cdbbb cdbbc cdbbd cdbca cdbcb

cdbcc cdbcd cdbda cdbdb cdbdc cdbdd cdcaa cdcab cdcac cdcad

cdcba cdcbb cdcbc cdcbd cdcca cdccb cdccc cdccd cdcda cdcdb

cdcdc cdcdd cddaa cddab cddac cddad cddba cddbb cddbc cddbd

cddca cddcb cddcc cddcd cddda cdddb cdddc cdddd daaaa daaab

daaac daaad daaba daabb daabc daabd daaca daacb daacc daacd

daada daadb daadc daadd dabaa dabab dabac dabad dabba dabbb

dabbc dabbd dabca dabcb dabcc dabcd dabda dabdb dabdc dabdd

dacaa dacab dacac dacad dacba dacbb dacbc dacbd dacca daccb

daccc daccd dacda dacdb dacdc dacdd dadaa dadab dadac dadad

dadba dadbb dadbc dadbd dadca dadcb dadcc dadcd dadda daddb

daddc daddd dbaaa dbaab dbaac dbaad dbaba dbabb dbabc dbabd

dbaca dbacb dbacc dbacd dbada dbadb dbadc dbadd dbbaa dbbab

dbbac dbbad dbbba dbbbb dbbbc dbbbd dbbca dbbcb dbbcc dbbcd

dbbda dbbdb dbbdc dbbdd dbcaa dbcab dbcac dbcad dbcba dbcbb

dbcbc dbcbd dbcca dbccb dbccc dbccd dbcda dbcdb dbcdc dbcdd

dbdaa dbdab dbdac dbdad dbdba dbdbb dbdbc dbdbd dbdca dbdcb

dbdcc dbdcd dbdda dbddb dbddc dbddd dcaaa dcaab dcaac dcaad

dcaba dcabb dcabc dcabd dcaca dcacb dcacc dcacd dcada dcadb

dcadc dcadd dcbaa dcbab dcbac dcbad dcbba dcbbb dcbbc dcbbd

dcbca dcbcb dcbcc dcbcd dcbda dcbdb dcbdc dcbdd dccaa dccab

dccac dccad dccba dccbb dccbc dccbd dccca dcccb dcccc dcccd

dccda dccdb dccdc dccdd dcdaa dcdab dcdac dcdad dcdba dcdbb

dcdbc dcdbd dcdca dcdcb dcdcc dcdcd dcdda dcddb dcddc dcddd

ddaaa ddaab ddaac ddaad ddaba ddabb ddabc ddabd ddaca ddacb

ddacc ddacd ddada ddadb ddadc ddadd ddbaa ddbab ddbac ddbad

ddbba ddbbb ddbbc ddbbd ddbca ddbcb ddbcc ddbcd ddbda ddbdb

ddbdc ddbdd ddcaa ddcab ddcac ddcad ddcba ddcbb ddcbc ddcbd

ddcca ddccb ddccc ddccd ddcda ddcdb ddcdc ddcdd dddaa dddab

dddac dddad dddba dddbb dddbc dddbd dddca dddcb dddcc dddcd

dddda ddddb ddddc ddddd

4. megoldás

static void feladat6Megoldas4() {

int db=0;

for(char k1='a'; k1<='d'; k1++)

for(char k2='a'; k2<='d'; k2++)

for(char k3='a'; k3<='d'; k3++)

for(char k4='a'; k4<='d'; k4++)

for(char k5='a'; k5<='d'; k5++)

db++;

System.out.println(db);

}

Ha csak a végeredmény szükséges, akkor ez az iteratív megoldás a megszámolás programozási tétellel előállítja azt.

5. megoldás

static void feladat6Megoldas5(String valasz) {

if(valasz.length()==5)

System.out.print(valasz+" ");

else

for(char v='a'; v<='d'; v++)

feladat6Megoldas5(valasz+v);

}

Ez egy rekurzív megoldás. Ciklus helyett a metódus önmagát hívja meg, így valósul meg az ismételt utasításvégrehajtás. A válaszlehetőségek összefűzésével (konkatenáció) előállított válasz akkor megfelelő, ha annak hossza öt. Ez esetben kiíródik a válaszlehetőség a konzolra (mintegy mellékhatásként). Ugyanazt az eredményt kapjuk, mint a 3. megoldásnál.

6. megoldás

static int db=0;

//...

static void feladat6Megoldas6(String valasz) {

if(valasz.length()==5)

db++;

else

for(char v='a'; v<='d'; v++)

feladat6Megoldas6(valasz+v);

}

//...

public static void main(String[] args) {

feladat6Megoldas6("");

System.out.println(db);

}

Szintén, ha csak a végeredmény szükséges, akkor ez a mellékhatással rendelkező rekurzív metódus előállítja azt. A mellékhatás most az, hogy a metódus eljárás és nem függvény és szükséges hozzá a db osztályváltozó (ami a metódushoz képest globálisnak is tekinthető).

7. megoldás

static void feladat6Megoldas7() {

int n=4, k=5, nadk=(int)Math.pow(n, k);

int[][] y=new int[nadk][1];

for(int i=0; i<=nadk-1; i++) {

int m=i;

int[] x=new int[k+1];

for(int j=1; j<=k; j++) {

x[j]=m%n;

m/=n;

}

y[i]=x;

}

for(int i=0; i<nadk; i++) {

for(int j=k; j>=1; j--)

System.out.print((char)(97+y[i][j]));

System.out.print(" ");

}

Ez a megoldás a válaszlehetőségeket megfelelteti n alapú számrendszerben k számjegyből álló számoknak. A kétdimenziós tömbben számokat tárol, így:

1,…,1,1 → 0…0000
1,…,1,2 → 0…0001
1,…,1,n → 0…001(n–1)
…
1,…,2,n → 0…001(n–1)
n,…,n,n → (n–1)...(n–1)

Végül a kiíró ciklus ezeket a számokat karakterekké alakítja ( 'a' ASCII kódja 97) és fordított sorrendben írja ki, hogy ugyanazt az eredményt kapjuk, mint a 3. megoldásnál.

Továbbfejlesztési lehetőségek

A 2. megoldáshoz: teszteljük le a lehetséges túlcsordulást és az int típus helyett szükség esetén használjunk long típust!
A 3. megoldáshoz: építsünk kétdimenziós tömb adatszerkezetet, amiből később az i-edik válaszlehetőség megadható!
Előzőhöz: állítsuk elő lexikografikus sorrendben az i-edik válaszlehetőséget adatszerkezet felépítése nélkül!
A 6. megoldáshoz: valósítsuk meg a rekurzív gondolatmenetet mellékhatás nélkül!
Teszteljünk: mennyi idő alatt hajtódik végre a 4. és a 6. megoldás? Mekkora paraméterekkel érzékelhető, hogy a rekurzió jóval lassabban fut?
A 7. megoldáshoz: cseréljük le az egésztömb adatszerkezetet karaktertömbre!

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

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

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 5-8. óra: Vezérlési szerkezetek, valamint 21-24. óra: Objektumorientált programozás 1. rész alkalmaihoz kötődik.

Ratkó István emlékest 2022

2022. december 19.2022. március 25. Szerző: Kaczur Sándor

A Gábor Dénes Főiskolán működő Ratkó István matematika interdiszciplináris alkalmazásai Műhely 2022. március 25-én 10. alkalommal rendezte meg a Ratkó István emlékestet. Ezen már többször is részt vettem előadóként és a hallgatóság tagjaként is. 2014-ben Prímszámkereső algoritmusok hatékonysága címmel, 2015-ben A bűvös négyzet története és előállítása (oktatóprogram) címmel tartottam előadást. A jubileumi emlékesten pedig „Töltsünk ki az ötöslottón 100 szelvényt úgy, hogy valamelyik szelvénnyel biztosan legyen két találatunk!” – a feladat megoldásához vezető út címmel tartottam előadást.

A blog bejegyzésben röviden összefoglalom az előadást:

Személyes élmények Ratkó tanár úrhoz kötődően
Ötöslottó: diszkrét matematika, elemi kombinatorikai feladat, lehetséges különböző szelvények száma, öttalálatos valószínűsége, szemléltetés
Véletlenszámok előállítása: valódi és ál (pszeudo) véletlenszámok, hardveres és szoftveres megoldások áttekintése, LCG
Egyetlen véletlenszám előállítása Java nyelven: procedurális, OO, szálbiztos megoldások
Egyetlen lottószelvény előállítása Java nyelven: adatszerkezet nélkül, logikai tömb (demóprogram), számtömb, szöveg (McMillan egyenlőtlenség, optimális kód, Huffman kód, prefixmentes kódolás, Shannon-Fano kód, hibajelző és hibajavító kód, Hamming távolság, Reed-Solomon kód, algebra: véges testek megkonstruálása), generikus lista (érték), generikus lista (keverés), generikus lista (elfogyasztás), generikus halmaz, funkcionális programozás / algoritmusok és adatszerkezetek rövid elemzése, összehasonlítása, kompromisszumok
Találatok száma: matematika vs. programozási tételek, metszet tömbbel és generikus listával, Stream API-val, lambda kifejezéssel
Különböző lottószelvények előállítása: összes eset, brute force, mesterséges intelligencia, problématér|állapottér, kombinatorikai robbanás kontrollálása
(szemléletváltás: az eddigi 1-90 intervallumból kiválasztott 5 különböző szám egy lottószelvényt jelentett, mostantól az 1-43949268 intervallumból kiválasztott különböző számok különböző lottószelvényeket jelentenek)

Eddig minden feldolgozható a középiskolás matematikai eszköztárral és kezdő Java objektumorientált programozás által biztosított mozgástérben. A továbbiakhoz szintet kell lépni.

A konkrét feladatspecifikáció:

„Töltsünk ki az ötöslottón 100 szelvényt úgy, hogy valamelyik szelvénnyel biztosan legyen két találatunk!” (Segítség: töltsünk ki 30 szelvényt úgy, hogy az 1-25 közötti számpárt lefedjék; 21 szelvényt úgy, hogy a 26-46 közötti összes számpárt lefedjék; 21 szelvényt úgy, hogy a 47-67 közötti összes számpárt lefedjék és 28 szelvényt úgy, hogy a 68-90 közötti összes számpárt lefedjék. Miért lesz így legalább két találatunk?)

A szintlépéshez hasznos ismerni két tankönyvet (Szilasi Zoltán: Bevezetés a véges geometriába, 2015; Reiman István: A geometria és határterületei, 2001) és egy tudományos cikket (Z. Füredi, G. J. Székely, Z. Zubor: On the Lottery Problem, 1995). További szükséges ismeretek (geometria, algebra, elemi matematika, kombinatorika): projektív geometria, véges projektív sík, Kirkman iskoláslány problémája, Fano-sík (mint algebrai és geometriai leképezés), Steiner-rendszer (ponthalmaz, amely elemszáma 6k+1 alakú prím), néhány konstruktív jellegű bizonyítás, skatulya-elv.

Az előadás a feladat megoldásához vezető útról szólt. Az eredmény előtti utolsó előtti lépés ezt jelenti (Java program konzolra kiírt szövege):

Töltsünk ki az ötöslottón 100 szelvényt úgy, hogy valamelyik szelvénnyel biztosan legyen két találatunk!

Segítség:

1-25 közötti összes számpár (300 db):

[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), (1, 14), (1, 15), (1, 16), (1, 17), (1, 18), (1, 19), (1, 20), (1, 21), (1, 22), (1, 23), (1, 24), (1, 25), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (2, 12), (2, 13), (2, 14), (2, 15), (2, 16), (2, 17), (2, 18), (2, 19), (2, 20), (2, 21), (2, 22), (2, 23), (2, 24), (2, 25), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 11), (3, 12), (3, 13), (3, 14), (3, 15), (3, 16), (3, 17), (3, 18), (3, 19), (3, 20), (3, 21), (3, 22), (3, 23), (3, 24), (3, 25), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (4, 12), (4, 13), (4, 14), (4, 15), (4, 16), (4, 17), (4, 18), (4, 19), (4, 20), (4, 21), (4, 22), (4, 23), (4, 24), (4, 25), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (5, 11), (5, 12), (5, 13), (5, 14), (5, 15), (5, 16), (5, 17), (5, 18), (5, 19), (5, 20), (5, 21), (5, 22), (5, 23), (5, 24), (5, 25), (6, 7), (6, 8), (6, 9), (6, 10), (6, 11), (6, 12), (6, 13), (6, 14), (6, 15), (6, 16), (6, 17), (6, 18), (6, 19), (6, 20), (6, 21), (6, 22), (6, 23), (6, 24), (6, 25), (7, 8), (7, 9), (7, 10), (7, 11), (7, 12), (7, 13), (7, 14), (7, 15), (7, 16), (7, 17), (7, 18), (7, 19), (7, 20), (7, 21), (7, 22), (7, 23), (7, 24), (7, 25), (8, 9), (8, 10), (8, 11), (8, 12), (8, 13), (8, 14), (8, 15), (8, 16), (8, 17), (8, 18), (8, 19), (8, 20), (8, 21), (8, 22), (8, 23), (8, 24), (8, 25), (9, 10), (9, 11), (9, 12), (9, 13), (9, 14), (9, 15), (9, 16), (9, 17), (9, 18), (9, 19), (9, 20), (9, 21), (9, 22), (9, 23), (9, 24), (9, 25), (10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (10, 16), (10, 17), (10, 18), (10, 19), (10, 20), (10, 21), (10, 22), (10, 23), (10, 24), (10, 25), (11, 12), (11, 13), (11, 14), (11, 15), (11, 16), (11, 17), (11, 18), (11, 19), (11, 20), (11, 21), (11, 22), (11, 23), (11, 24), (11, 25), (12, 13), (12, 14), (12, 15), (12, 16), (12, 17), (12, 18), (12, 19), (12, 20), (12, 21), (12, 22), (12, 23), (12, 24), (12, 25), (13, 14), (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 20), (13, 21), (13, 22), (13, 23), (13, 24), (13, 25), (14, 15), (14, 16), (14, 17), (14, 18), (14, 19), (14, 20), (14, 21), (14, 22), (14, 23), (14, 24), (14, 25), (15, 16), (15, 17), (15, 18), (15, 19), (15, 20), (15, 21), (15, 22), (15, 23), (15, 24), (15, 25), (16, 17), (16, 18), (16, 19), (16, 20), (16, 21), (16, 22), (16, 23), (16, 24), (16, 25), (17, 18), (17, 19), (17, 20), (17, 21), (17, 22), (17, 23), (17, 24), (17, 25), (18, 19), (18, 20), (18, 21), (18, 22), (18, 23), (18, 24), (18, 25), (19, 20), (19, 21), (19, 22), (19, 23), (19, 24), (19, 25), (20, 21), (20, 22), (20, 23), (20, 24), (20, 25), (21, 22), (21, 23), (21, 24), (21, 25), (22, 23), (22, 24), (22, 25), (23, 24), (23, 25), (24, 25)]

ebből kellene 30 db szelvényt kitölteni úgy, hogy az összes számpárt lefedje

26-46 közötti összes számpár (210 db):

[(26, 27), (26, 28), (26, 29), (26, 30), (26, 31), (26, 32), (26, 33), (26, 34), (26, 35), (26, 36), (26, 37), (26, 38), (26, 39), (26, 40), (26, 41), (26, 42), (26, 43), (26, 44), (26, 45), (26, 46), (27, 28), (27, 29), (27, 30), (27, 31), (27, 32), (27, 33), (27, 34), (27, 35), (27, 36), (27, 37), (27, 38), (27, 39), (27, 40), (27, 41), (27, 42), (27, 43), (27, 44), (27, 45), (27, 46), (28, 29), (28, 30), (28, 31), (28, 32), (28, 33), (28, 34), (28, 35), (28, 36), (28, 37), (28, 38), (28, 39), (28, 40), (28, 41), (28, 42), (28, 43), (28, 44), (28, 45), (28, 46), (29, 30), (29, 31), (29, 32), (29, 33), (29, 34), (29, 35), (29, 36), (29, 37), (29, 38), (29, 39), (29, 40), (29, 41), (29, 42), (29, 43), (29, 44), (29, 45), (29, 46), (30, 31), (30, 32), (30, 33), (30, 34), (30, 35), (30, 36), (30, 37), (30, 38), (30, 39), (30, 40), (30, 41), (30, 42), (30, 43), (30, 44), (30, 45), (30, 46), (31, 32), (31, 33), (31, 34), (31, 35), (31, 36), (31, 37), (31, 38), (31, 39), (31, 40), (31, 41), (31, 42), (31, 43), (31, 44), (31, 45), (31, 46), (32, 33), (32, 34), (32, 35), (32, 36), (32, 37), (32, 38), (32, 39), (32, 40), (32, 41), (32, 42), (32, 43), (32, 44), (32, 45), (32, 46), (33, 34), (33, 35), (33, 36), (33, 37), (33, 38), (33, 39), (33, 40), (33, 41), (33, 42), (33, 43), (33, 44), (33, 45), (33, 46), (34, 35), (34, 36), (34, 37), (34, 38), (34, 39), (34, 40), (34, 41), (34, 42), (34, 43), (34, 44), (34, 45), (34, 46), (35, 36), (35, 37), (35, 38), (35, 39), (35, 40), (35, 41), (35, 42), (35, 43), (35, 44), (35, 45), (35, 46), (36, 37), (36, 38), (36, 39), (36, 40), (36, 41), (36, 42), (36, 43), (36, 44), (36, 45), (36, 46), (37, 38), (37, 39), (37, 40), (37, 41), (37, 42), (37, 43), (37, 44), (37, 45), (37, 46), (38, 39), (38, 40), (38, 41), (38, 42), (38, 43), (38, 44), (38, 45), (38, 46), (39, 40), (39, 41), (39, 42), (39, 43), (39, 44), (39, 45), (39, 46), (40, 41), (40, 42), (40, 43), (40, 44), (40, 45), (40, 46), (41, 42), (41, 43), (41, 44), (41, 45), (41, 46), (42, 43), (42, 44), (42, 45), (42, 46), (43, 44), (43, 45), (43, 46), (44, 45), (44, 46), (45, 46)]

ebből kellene 21 db szelvényt kitölteni úgy, hogy az összes számpárt lefedje

47-67 közötti összes számpár (210 db):

[(47, 48), (47, 49), (47, 50), (47, 51), (47, 52), (47, 53), (47, 54), (47, 55), (47, 56), (47, 57), (47, 58), (47, 59), (47, 60), (47, 61), (47, 62), (47, 63), (47, 64), (47, 65), (47, 66), (47, 67), (48, 49), (48, 50), (48, 51), (48, 52), (48, 53), (48, 54), (48, 55), (48, 56), (48, 57), (48, 58), (48, 59), (48, 60), (48, 61), (48, 62), (48, 63), (48, 64), (48, 65), (48, 66), (48, 67), (49, 50), (49, 51), (49, 52), (49, 53), (49, 54), (49, 55), (49, 56), (49, 57), (49, 58), (49, 59), (49, 60), (49, 61), (49, 62), (49, 63), (49, 64), (49, 65), (49, 66), (49, 67), (50, 51), (50, 52), (50, 53), (50, 54), (50, 55), (50, 56), (50, 57), (50, 58), (50, 59), (50, 60), (50, 61), (50, 62), (50, 63), (50, 64), (50, 65), (50, 66), (50, 67), (51, 52), (51, 53), (51, 54), (51, 55), (51, 56), (51, 57), (51, 58), (51, 59), (51, 60), (51, 61), (51, 62), (51, 63), (51, 64), (51, 65), (51, 66), (51, 67), (52, 53), (52, 54), (52, 55), (52, 56), (52, 57), (52, 58), (52, 59), (52, 60), (52, 61), (52, 62), (52, 63), (52, 64), (52, 65), (52, 66), (52, 67), (53, 54), (53, 55), (53, 56), (53, 57), (53, 58), (53, 59), (53, 60), (53, 61), (53, 62), (53, 63), (53, 64), (53, 65), (53, 66), (53, 67), (54, 55), (54, 56), (54, 57), (54, 58), (54, 59), (54, 60), (54, 61), (54, 62), (54, 63), (54, 64), (54, 65), (54, 66), (54, 67), (55, 56), (55, 57), (55, 58), (55, 59), (55, 60), (55, 61), (55, 62), (55, 63), (55, 64), (55, 65), (55, 66), (55, 67), (56, 57), (56, 58), (56, 59), (56, 60), (56, 61), (56, 62), (56, 63), (56, 64), (56, 65), (56, 66), (56, 67), (57, 58), (57, 59), (57, 60), (57, 61), (57, 62), (57, 63), (57, 64), (57, 65), (57, 66), (57, 67), (58, 59), (58, 60), (58, 61), (58, 62), (58, 63), (58, 64), (58, 65), (58, 66), (58, 67), (59, 60), (59, 61), (59, 62), (59, 63), (59, 64), (59, 65), (59, 66), (59, 67), (60, 61), (60, 62), (60, 63), (60, 64), (60, 65), (60, 66), (60, 67), (61, 62), (61, 63), (61, 64), (61, 65), (61, 66), (61, 67), (62, 63), (62, 64), (62, 65), (62, 66), (62, 67), (63, 64), (63, 65), (63, 66), (63, 67), (64, 65), (64, 66), (64, 67), (65, 66), (65, 67), (66, 67)]

ebből kellene 21 db szelvényt kitölteni úgy, hogy az összes számpárt lefedje

68-90 közötti összes számpár (253 db):

[(68, 69), (68, 70), (68, 71), (68, 72), (68, 73), (68, 74), (68, 75), (68, 76), (68, 77), (68, 78), (68, 79), (68, 80), (68, 81), (68, 82), (68, 83), (68, 84), (68, 85), (68, 86), (68, 87), (68, 88), (68, 89), (68, 90), (69, 70), (69, 71), (69, 72), (69, 73), (69, 74), (69, 75), (69, 76), (69, 77), (69, 78), (69, 79), (69, 80), (69, 81), (69, 82), (69, 83), (69, 84), (69, 85), (69, 86), (69, 87), (69, 88), (69, 89), (69, 90), (70, 71), (70, 72), (70, 73), (70, 74), (70, 75), (70, 76), (70, 77), (70, 78), (70, 79), (70, 80), (70, 81), (70, 82), (70, 83), (70, 84), (70, 85), (70, 86), (70, 87), (70, 88), (70, 89), (70, 90), (71, 72), (71, 73), (71, 74), (71, 75), (71, 76), (71, 77), (71, 78), (71, 79), (71, 80), (71, 81), (71, 82), (71, 83), (71, 84), (71, 85), (71, 86), (71, 87), (71, 88), (71, 89), (71, 90), (72, 73), (72, 74), (72, 75), (72, 76), (72, 77), (72, 78), (72, 79), (72, 80), (72, 81), (72, 82), (72, 83), (72, 84), (72, 85), (72, 86), (72, 87), (72, 88), (72, 89), (72, 90), (73, 74), (73, 75), (73, 76), (73, 77), (73, 78), (73, 79), (73, 80), (73, 81), (73, 82), (73, 83), (73, 84), (73, 85), (73, 86), (73, 87), (73, 88), (73, 89), (73, 90), (74, 75), (74, 76), (74, 77), (74, 78), (74, 79), (74, 80), (74, 81), (74, 82), (74, 83), (74, 84), (74, 85), (74, 86), (74, 87), (74, 88), (74, 89), (74, 90), (75, 76), (75, 77), (75, 78), (75, 79), (75, 80), (75, 81), (75, 82), (75, 83), (75, 84), (75, 85), (75, 86), (75, 87), (75, 88), (75, 89), (75, 90), (76, 77), (76, 78), (76, 79), (76, 80), (76, 81), (76, 82), (76, 83), (76, 84), (76, 85), (76, 86), (76, 87), (76, 88), (76, 89), (76, 90), (77, 78), (77, 79), (77, 80), (77, 81), (77, 82), (77, 83), (77, 84), (77, 85), (77, 86), (77, 87), (77, 88), (77, 89), (77, 90), (78, 79), (78, 80), (78, 81), (78, 82), (78, 83), (78, 84), (78, 85), (78, 86), (78, 87), (78, 88), (78, 89), (78, 90), (79, 80), (79, 81), (79, 82), (79, 83), (79, 84), (79, 85), (79, 86), (79, 87), (79, 88), (79, 89), (79, 90), (80, 81), (80, 82), (80, 83), (80, 84), (80, 85), (80, 86), (80, 87), (80, 88), (80, 89), (80, 90), (81, 82), (81, 83), (81, 84), (81, 85), (81, 86), (81, 87), (81, 88), (81, 89), (81, 90), (82, 83), (82, 84), (82, 85), (82, 86), (82, 87), (82, 88), (82, 89), (82, 90), (83, 84), (83, 85), (83, 86), (83, 87), (83, 88), (83, 89), (83, 90), (84, 85), (84, 86), (84, 87), (84, 88), (84, 89), (84, 90), (85, 86), (85, 87), (85, 88), (85, 89), (85, 90), (86, 87), (86, 88), (86, 89), (86, 90), (87, 88), (87, 89), (87, 90), (88, 89), (88, 90), (89, 90)]

ebből kellene 28 db szelvényt kitölteni úgy, hogy az összes számpárt lefedje

Miért lesz így legalább két találatunk?

Végül ismertettem néhány lehetőséget az algoritmus vizsgálatára és az implementált Java forráskód tesztelésére.

Köszönöm Kupcsikné Fitus Ilona kolléganőnek, hogy a jubileumi Ratkó István emlékest szervezőjeként előadónak felkért. Örömmel csatlakoztam újra. A prezentációmat a résztvevőkkel megosztottam. Köszönöm az érdeklődő kollégáknak és hallgatóknak a részvételt és a pozitív visszajelzéseket. Az emlékestek programjai elérhetők. Ajánlom lottószelvény címkénket is, mert a téma igazi örökzöld.