A 
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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:
|
1 2 3 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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 = 22 * 3 * 5 * 7, 504 = 23 * 32 * 7, így lnko (420; 504) = 22 * 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.
