brute force - címke - it-tanfolyam.hu

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

2023. augusztus 4.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

2024. július 8.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.

Barátságos számok

2023. augusztus 15.2018. július 19. Szerző: Balogh Péter

Azokat a számpárokat, amelyekre igaz, hogy az egyik szám önmagánál kisebb osztóinak összege megegyezik a másik számmal és fordítva, külön-külön barátságos számoknak, együtt barátságos számpárnak hívjuk.

Másképpen: legyen d(n) az n természetes szám önmagánál kisebb osztóinak összege. Ha d(a)=b és d(b)=a, ahol a≠b, akkor a és b barátságos számpár.

Például: (220; 284), hiszen a 220 önmagánál kisebb osztói: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 és ezek összege 284, illetve 284 önmagánál kisebb osztói: 1, 2, 4, 71, 142 és ezek összege 220.

Írjunk Java programot, amely kiírja az 1-10000 zárt intervallumban található barátságos számpárokat!

1. megoldás

A baratsagosSzamparok1() eljárás ciklusai a brute force módszer szerint behelyesítik az összes lehetséges számot. Minimális lépésszám csökkentésre adódik lehetőség, hiszen a belső ciklus j változója i+1-ről indítható (így a megtalált számpárok nem íródnak ki fordítva is, mert teljesül, hogy i<j).

Az osztokOsszege1(n) függvény is minden lehetséges osztót figyelembe vesz 1-től n-1-ig.

private static int osztokOsszege1(int n) {

int s=0;

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

if(n%i==0)

s+=i;

return s;

}

private static void baratsagosSzamparok1() {

System.out.println("Barátságos számpárok 1-től 10000-ig:");

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

for(int j=i+1; j<=10000; j++)

if(i==osztokOsszege1(j) && j==osztokOsszege1(i))

System.out.println("("+i+"; "+j+")");

}

2. megoldás

Kisebb módosításokkal a lépésszám csökkenthető. A baratsagosSzamparok2() eljárás külső ciklusánál figyelembe vettem, hogy a legkisebb barátságos számpár kisebb tagja nagyobb 200-nál. Mivel a barátságos számpárok tagjainak paritása mindig megegyezik (azaz mindkettő páros vagy mindkettő páratlan), így a belső ciklus j változója indítható i+2-ről és léptethető kettesével ( j+=2), és továbbra is teljesül, hogy i<j.

Az osztokOsszege2(n) függvényt is módosítottam. Mivel az 1 minden számnak osztója, illetve a 2 minden páros számnak osztója, így s lehet 3 vagy 1 és a ciklus indítható 3-ról. A páros számok esetén a számnál kisebb legnagyobb osztó maximum n/2 lehet, illetve ugyanez páratlan számok esetén n/3 lehet. Ezekre figyelve a max változó adja a ciklus léptetésének felső határát. Az i változó léptetésénél figyelembe vettem, hogy páratlan számnak csak páratlan osztói lehetnek ( i=3-mal szinkronban).

private static int osztokOsszege2(int n) {

int s=(n%2==0?3:1);

int max=(n%2==0?n/2:n/3);

int lepes=(n%2==0?1:2);

for(int i=3; i<=max; i+=lepes)

if(n%i==0)

s+=i;

return s;

}

private static void baratsagosSzamparok2() {

System.out.println("Barátságos számpárok 1-től 10000-ig:");

for(int i=200; i<=10000; i++)

for(int j=i+2; j<=10000; j+=2)

if(i==osztokOsszege2(j) && j==osztokOsszege2(i))

System.out.println("("+i+"; "+j+")");

}

3. megoldás

Az eddigi két egymásba ágyazott ciklus helyett átszervezhető a baratsagosSzamparok3() eljárás. A j>i && osztokOsszege2(j)==i feltétel kiértékelése így sokkal hatékonyabb.

private static void baratsagosSzamparok3() {

System.out.println("Barátságos számpárok 1-től 10000-ig:");

for(int i=200; i<=10000; i++) {

int j=osztokOsszege2(i);

if(j>i && osztokOsszege2(j)==i)

System.out.println("("+i+"; "+j+")");

}

Vajon milyen nagyságrendű különbségek adódnak, ha összehasonlítjuk a három megoldás futási idejét?

Az 1. megoldás futási ideje 1104156 ms, a 2. megoldásé 257055 ms, a 3. megoldásé 121 ms. A konkrét értékek helyett a nagyságrendet megfigyelve a különbség nagyon látványos.

Mindhárom megoldás helyes és megkapjuk az intervallumban található öt barátságos számpárt: (220; 284), (1184; 1210), (2620; 2924), (5020; 5564), (6232; 6368).

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.

Források:

Wikipédia – Barátságos számok
Wikipedia – Amicable numbers
www.mathe.tu-freiberg.de – Vollkommene, befreundete und gesellige Zahlen
gorbem.hu – Barátságok számok
Hasonló feladat: https://projecteuler.net/problem=21 és megoldás: http://code.jasonbhill.com/c/project-euler-problem-21/

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: Metódusok, rekurzió alkalomhoz kötődik.

Hány éves a kapitány?

2023. január 1.2018. március 22. Szerző: Kaczur Sándor

A problémamegoldó, logikus gondolkodásra nevelő képzések anyagában, illetve felvételi feladatsorokban is sokszor megtalálható – többféle változatban is.

Lássunk egyet a népszerű „Hány éves a kapitány?” típusú feladatok közül!

Három elefántot kell berakodnunk – szólt a hajóskapitány az első tiszthez.
És hány évesek ezek az elefántok? – kérdezte az első tiszt.
Mindegyik elmúlt már két éves és életkoraik szorzata 2450 – volt a válasz.
Hát életkoraik összege?
Azt fölösleges elárulnom, mert abból még nem tudnád megállapítani életkorukat – mondta a kapitány, majd hozzátette: Az egyikük idősebb nálam.
Akkor már tudom, hogy hány évesek az elefántok – mondta az első tiszt.

Feltéve, hogy tényleg tudta; … hány éves a kapitány?

Hogyan használhatnánk a feladat megoldásához programozáshoz kötődő ismereteinket?

Állítsunk elő olyan három szorzótényezőt, amelyek szorzata 2450 és egyben írassuk ki az összegüket is a konzolra!

public class Kapitany {

public static void main(String[] args) {

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

for(int j=i; j<=100; j++)

for(int k=j; k<=100; k++)

if(i*j*k==2450)

System.out.println(

i+"*"+j+"*"+k+"=2450\t"+i+"+"+j+"+"+k+"="+(i+j+k));

}

Az i, j, k a három elefánt életkorát jelöli. Mivel mindegyik elmúlt két éves (és feltételezzük, hogy életkoraik egész számmal kifejezhetők), így i=3-ról indul. Az elefántok lehetnek egyidősek, ezért j=i-ről és k=j-ről indul. Nincs kizárt életkor, így a változók léptethetők egyesével. Az i, j, k monoton növekvő sorozatot alkot, ezért a kiírásban nem lesznek olyan sorok, amelyek csupán a szorzótényezők sorrendjében térnek el. Durva felső becslés a 100, hiszen az elefántok általában 60-70 évig élnek. Eredményül ezt kapjuk:

5*5*98=2450 5+5+98=108

5*7*70=2450 5+7+70=82

5*10*49=2450 5+10+49=64

5*14*35=2450 5+14+35=54

7*7*50=2450 7+7+50=64

7*10*35=2450 7+10+35=52

7*14*25=2450 7+14+25=46

Az eredményből milyen következtetés(eke)t lehet levonni és mi a megoldás?

Az egyszer előforduló összegeket ki kell zárni, mert abból az első tiszt tudná az elefántok életkorát. Többször előforduló összegként marad a 64. Tehát az elefántok lehetnek 5, 10, 49, illetve 7, 7, 50 évesek. Mivel a kapitánynál idősebb az egyik elefánt, így a kapitány nem lehet 48 éves vagy fiatalabb (mert ekkor nem lenne egyértelmű az életkora), illetve nem lehet 50 éves vagy idősebb (mert ekkor nem lenne nála idősebb elefánt). Tehát a kapitány 49 éves.

(Másképpen megközelítve: a 2450 prímtényezős felbontása 2*5²*7², amiből ugyanezekre a következtetésekre juthatunk.)

A feladat további változatai

Egy hajó hosszának, az árbóc magasságának, a kapitány kisfia életkorának és a kapitány életkorának szorzata 303335. Hány éves a kapitány?
A kapitány most kétszer annyi idős, mint a hajója volt akkor, amikor a kapitány kétszer volt annyi idős, mint most a hajója. A kapitány és a hajója összesen 70 éves. Hány éves a kapitány?
A Fekete Kalóz néven elhíresült kalózkapitány egyik sikeres kalandja után kiszámíttatta saját maga és kisfia életkorának, valamint hajója hosszának a szorzatát. Az eredmény 26 159 lett, amelyet mint szerencseszámot egy medálra vésetett és mindig a nyakában hordott. Hány éves a kapitány? (A hajóhosszt méterekben mérték, és a mérőszám egész szám!)
Te vezeted az utasszállító repülőt. Budapesten felszáll 11 utas. Bécsben leszáll 5 és felszáll 9. Párizsban 1 kivételével mindenki leszáll. Hány éves a kapitány?
A kapitány hajója most 40 éves. Kétszer annyi idős, mint amennyi a kapitány volt akkor, amikor a hajó annyi idős volt, mint a kapitány most. Hány éves a kapitány?

A bejegyzéshez tartozó 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 5-8. óra: Vezérlési szerkezetek alkalmához kötődik.

Ajánlott irodalom

Aki kedvet kapott és beszerezne néhány könyvet – tele érdekes, gondolkodtató, kreatív, logikai feladatokkal – ajánlom az alábbiakat:

Katona, R. (szerk): Logikai egypercesek – az elme játékai, 2. kiadás, DFT-Hungária Könyvkiadó, Budapest, 2006, ISBN 963 9473 55 3
Róka, S.: 2×2 néha 5? – Paradoxonok, hibás bizonyítások, Tóth Könyvkereskedés és Kiadó Kft., Debrecen, 2008, ISBN 963 5965 24 3
Károlyi, Zs.: Csak logIQsan!, 2. javított kiadás, Typotex Elektronikus Kiadó Kft., Budapest, 2017, ISBN 963 279 693 5
Róka, S.: Egypercesek – Feladatok matematikából 14-18 éveseknek, Tóth Könyvkereskedés Kft., Debrecen, 1997
G. Nagy, L.: A világ legújabb logikai rejtvényei, Magyar Könyvklub, H. n., 2001, ISBN 963 547 512 8

Haladóknak ajánlom

Smullyan, R.: A hölgy vagy a tigris? – és egyéb logikai feladatok, 2. javított kiadás, Typotex Kiadó Kft., Budapest, 2002, ISBN 963 7546 63 4
Smullyan, R.: Mi a címe ennek a könyvnek? – Drakula rejtélye és más logikai feladványok, Typotex Elektronikus Kiadó Kft., Budapest, 1996, ISBN 963 7546 64 2
Shasha, D.: Dr. Ecco talányos kalandjai, Typotex Kiadó – SHL Hungary Kft., 2000, ISBN 963 9132 72 1

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é.