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

érettségi logó

érettségi logó

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

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:

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

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:

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.

Sankey-diagram készítése

A Sankey-diagram alkalmas kétféle adatsor közötti N:M fokszámú kapcsolat, összefüggés és a köztes átmenet ábrázolására. Hangsúlyozza a fő átvitelt vagy áramlatokat egy rendszeren belül. Az áramlás irányát nyíllal szemlélteti és az áramlatok szélessége arányos az áramlási mennyiségekkel.

Feladat

Jelenítsük meg HTML formátumú weboldalként a magyarországi régiókban a foglalkoztatottak számát nemzetgazdasági szektorok szerint a KSH 2018-as adatsora alapján! Automatizáljuk egy Java programmal úgy a feladatot, hogy az év paraméterként megadható legyen!

Tervezés

A KSH témastruktúrában a táblázat elérési útja:

  • 5. Területi adatok,
  • 5.1. A munkaerő-piaci tendenciák Magyarország régióiban,
  • 5.1.3. A foglalkoztatottak száma nemzetgazdasági szektorok szerint, nemenként (2008–)

Online böngészhető táblázat:
https://www.ksh.hu/docs/hun/xstadat/xstadat_hosszu/h_qlf017.html

Letölthető táblázat (XLS formátumban):
https://www.ksh.hu/docs/hun/xstadat/xstadat_hosszu/xls/h5_1_3.xls

A táblázatban lévő adatforrás szükséges része látható az ábrán:

KSH adatforrás Sankey-diagramhoz

A táblázatban a régiók az A105:A112 cellatartományban találhatók. A hozzájuk tartozó 3 nemzetgazdasági szektor a B-C-D oszlopok azonos soraiból olvashatók ki. POJO-k létrehozása mindenképpen hasznos a megvalósításhoz, például new SankeyData("Közép-Dunántúl", "Szolgáltatás", 253.89). Ezekből generikus listát is célszerű építeni: List<SankeyData> sankeyDataList.

Többféleképpen is hozzájuthatunk az adatokhoz attól függően, hogy milyen előismeretekkel rendelkezünk a különböző tanfolyamainkon:

  • A Java SE szoftverfejlesztő tanfolyamon „kézzel” letölthetjük a projekt files mappájába az XLS fájlt. Ezután akár manuálisan is összeállítható a POJO lista, vagy a JExcel API-val is hatékonyan feldolgozható a XLS fájl aktuális munkalapja. Fájlkezelés előtt az összeállított HTML fájlt kiírathatjuk a konzolra, ahonnan „kézzel” vágólapozva létrehozhatjuk belőle a szükséges HTML fájlt. Fájlkezeléssel persze adott mappába, adott fájlnévvel, kivételkezeléssel a java.io vagy java.nio csomagot használva a HTML fájl generálása is automatizálható.
  • A Java EE szoftverfejlesztő tanfolyamon megvalósítható, hogy a program kivételkezeléssel hálózati kapcsolatot épít, majd letölti az XLS fájlt és ezzel a feladat visszavezethető az előző esetekre. Azt is megtehetjük, hogy az XLS fájlt nem töltjük le, hanem olvasunk belőle közvetlenül a webről. Ekkor is rendelkezésünkre áll a POJO lista. Itt már tudunk HTML fájlt is automatikusan generálni.

Tanulmányoznunk kell a Google Charts galériában a Sankey diagram dokumentációját! Meg kell ismernünk a paraméterezési lehetőségeit és JavaScript forráskódját!

Megvalósítás

A createSankeyDiagram() függvény létrehozza a HTML fájl szöveges tartalmát. Átveszi adatforrásként a sankeyDataList generikus POJO listát. A String típusú sankeyData objektum tartalmazza a Stream API-val hatékonyan összefűzött – POJO-któl elkért – toString() szövegeket. Ezek a diagramhoz szükséges adatok ( addRows …). Például: "['Közép-Dunántúl', 'Szolgáltatás', 253.89]". A  String típusú  html objektum kezdetben tartalmazza a diagramhoz nem szükséges fix részeket, a diagram alapbeállításait, valamint a diagram fejlécéhez szükséges metaadatokat ( addColumnRégió, Nemzetgazdasági szektor, Foglalkoztatottak száma (ezer fő)). A függvény végül a html objektum #SankeyData# részét cseréli a sankeyData-val és az adatfüggő résszel frissített HTML tartalommal tér vissza.

Eredmény

Az egyik eredmény a generált HTML fájl (benne a grafikonhoz tartozó JavaScript) forráskódját tartalmazza:

A másik eredmény a Sankey-diagram képernyőképe, amelyről kiválóan leolvashatók az értékek:

Sankey-diagram

A böngészőben megjelenő HTML oldalon a Sankey-diagram dinamikusan – az egérkurzor pozíciójától függően – képes az aktuális adatok megjelenítésére, mintegy lebegő jelmagyarázatként.

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

Fibonacci-sorozat

Fibonacci logó

Fibonacci logóMa van (november 23.) a Fibonacci nap (újra). Fibonacci középkori matematikus volt, ő tette közismertté a Fibonacci-sorozat-ot. A (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, sorozat igen népszerű azok közében is, akik programozást tanulnak. A sorozat első két eleme 1 és 1 (ha szükséges, akkor nulladik elemmel is dolgozhatunk), és minden további elem az előző két elem összege.

Korábban is blogoltak a kollégáim a témában:

Következzen most az én öt különböző megoldásom Java forráskódja, rövid magyarázattal. Mindegyik a Fibonacci-sorozat első tíz elemét állítja elő.

1. megoldás

Az első megoldás generikus listát épít. Az első két elemet elhelyezi a lista elején ( list.add(1)). Ezek a lista nulladik és első elemei lesznek. Ezután a metódus a maradék 8 elemmel 2-től n-1-ig fiktív indexként hivatkozva az előző két elem összegeként ( list.get(i-1)+list.get(i-2)) index nélkül bővíti a listát.

2. megoldás

A második megoldás a tipikusan nem hatékony rekurzív módszert implementálja. A rekurzív fib() függvény a sorozat egyetlen elemét adja vissza, amit (a függvényt) a ciklus sokszor meghív ahelyett, hogy a ciklus vagy a rekurzió „emlékezne” az előző elemekre.

3. megoldás

A harmadik megoldás funkcionális nyelvi elemeket (Stream API) használ. A folyamba kétdimenziós tömbre történő hivatkozással ( f-> new int[] ), közvetlen hozzárendeléssel/leképezéssel ( map()), kerülnek be a sorozat elemei.

4. megoldás

A negyedik megoldás a Fibonacci-számok zárt alakját használja. Másképpen ez a Binet-formula:

Ezzel a képlettel a sorozat elemei közvetlenül megadhatók, azaz nem szükséges más elemekre való hivatkozás. A ciklus adja meg, hogy a sorozat 1-10-ig indexelt elemei szükségesek.

5. megoldás

Az ötödik megoldás szintén Stream API-t használ. Először előállít egy sorozatot 1-10-ig, amiket a leképezésnél ( map()) inputként használ és alkalmazza rájuk a Binet-formulát. Hagyományos ciklus utasítás nem szükséges.

Eredmény

Mindegyik megoldás a konzolra írja szövegesen az eredményt, azaz a Fibonacci-sorozat első tíz elemét: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Érdemes elemezni a hatékonyság klasszikus három szempontja (időigény/lépésszám, tárigény, bonyolultság) alapján a különböző megoldásokat. Ezek mérésével könnyen kiegészíthetők a fenti metódusok, vagy az azokat meghívó osztályban a vezérlés.

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

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

Tankocka – Párkereső: csomag, osztály, interfész

Folytatjuk Tankockák blog bejegyzés sorozatunkat. A feladatban 12 összetartozó párt kell megtalálni az ismert Java csomagok, osztályok, interfészek témakörben. Ez a témakör mindhárom tanfolyamunkhoz kötődik: Java SE szoftverfejlesztő tanfolyam, Java EE szoftverfejlesztő tanfolyam, Java adatbázis-kezelő tanfolyam. Ezek egyszerű lexikális ismeretnek tűnhetnek, de jóval túlmutat azon.

Tipikus hibaforrás, ha az osztály és/vagy interfész neve a különböző csomagok esetén megegyezik és megszokásból, rutinból, figyelmetlenségből rossz csomagból importálunk. Nem biztos, hogy rögtön triviális: mi a hiba, miért az a hiba, hogyan oldjuk meg. Például Timer osztály van a java.util és a javax.swing csomagokban is és nagyon nem mindegy, hogy mikor melyiket (és persze mire, hogyan) használjuk.

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

érettségi logó

érettségi logóA 2021-es középszintű matematika érettségi feladatsor 12. feladata inspirált arra, hogy a programozás eszköztárával oldjuk meg ezt a feladatot. Szükséges hozzá néhány programozási tétel: sorozatszámítás, eldöntés, megszámolás, kiválogatás. Többféle megoldás/megközelítés 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.

12. feladat

A háromjegyű pozitív egész számok közül véletlenszerűen kiválasztunk egyet. Mennyi annak a valószínűsége, hogy a kiválasztott szám számjegyei különbözők? Megoldását részletezze!

1. megoldás

Az 1. megoldás egymásba ágyazott ciklusokkal behelyettesíti a szóba jöhető 900 db háromjegyű szám számjegyeit. A feltétel 648 esetben teljesül. Három számjegy azonosságát két részfeltétel és kapcsolatával eldönthetnénk a trichotómia miatt. Három számjegy különbözőségéhez három részfeltétel és kapcsolatából áll össze a feltétel. A válasz a kedvező és összes eset aránya/hányadosa, azaz 0,72. Másképpen 648 db szám a 900 db háromjegyű szám közül. A megoldás lépésszáma 900.

2. megoldás

Az egymásba ágyazott ciklusok lépésszáma összeszorzódik. A legbelső ciklus az előtte lévő feltételtől függően kevesebbszer is végrehajtódhat, hiszen a százas és tízes helyiértéken lévő számjegyek egyezése esetén nincs értelme az egyes helyiértéken lévő számjegy vizsgálatának. Így a 2. megoldás lépésszáma 810, azaz 10%-kal kevesebb. Ez a három részből álló feltétel két részre bontásával érhető el.

3. megoldás

A 3. megoldásban egyetlen ciklus végzi a vizsgálatot, a megszámolást. A ciklusváltozó már nem számjegy, hanem maga a háromjegyű szám, amiről döntést kell hozni: különbözik-e mindegyik számjegye vagy sem. Három beszédes nevű segédváltozó segít értelmezni a Java forráskódot. Ezek az egész osztás és a maradékos osztás műveleteivel állíthatók elő.

4. megoldás

A 4. megoldás logikai visszatérési értékű segédfüggvényt alkalmaz. Ez egy menekülőutas megoldás. Ha kizáró feltétel szerint már döntést tudunk hozni (például megegyezik a százas és a tízes helyiértéken lévő számjegy), akkor hamis értékkel menekülünk. Egyébként ág nélkül ezután következhet az egyes helyiértéken lévő számjegy összehasonlítása a többivel. A második feltétel az eddigiekhez képest tagadott, mert a menekülés a cél. Ha nincs menekülés amiatt, hogy volt két megegyező számjegy, akkor – a feltételek egymásra épülése miatt – nincs más hátra, mint igaz értékkel visszatérni (ami azt jelenti, hogy nem volt egyezés, azaz minden számjegy különbözött).

5. megoldás

Az 5. megoldás segédfüggvénye a háromjegyű szám esetén a különböző számjegyek darabszámával tér vissza. A röptében előállított százaz, tízes, egyes helyiértékeken lévő számjegyekből folyam adatszerkezet készül, aminek feldolgozását a Stream API műveletei (egyediesítő, megszámoló) végzik el. Ezt a vezérlő ciklusban hárommal összehasonlítva léptethető a megszámolást megvalósító változó, hiszen ha teljesül a feltétel, akkor eggyel több megfelelő szám van, mint előtte volt.

6. megoldás

Az 6. megoldás újra másképpen közelít. Ha könnyebbnek tűnik az a feltétel, hogy mikor nem jó (kedvezőtlen) nekünk egy szám, akkor beépíthetjük ezt is. Megszámoljuk azokat a háromjegyű számokat, amelyeknél egy vagy két számjegy azonos, majd ez kivonjuk a háromjegyű számok darabszámából.

7. megoldás

A 7. megoldás már mindent folyamokkal old meg, azok képességeire építve. Az összes háromjegyű számot előállítja, majd rajtuk kiválogatás programozási tételt (szűrőt) használ (az 5. megoldás segédfüggvényére építve), végül a folyamban maradó számokat megszámolja. Ez a megoldás már olyan haladóknak való, akik magabiztosan építik össze a Stream API műveleteit és a lambda kifejezéseket. Mindent egyben. Persze hol itt a hatékonyság? Hozzászólásokban megbeszélhetjük.

8. megoldás

A 8. megoldás szintén folyam adatszerkezettel működik, de négy egymást követő lépésben végez szűrést (kiválogatást). A 900 db háromjegyű számból indulunk ki. Az 1. szűrő kihagyja a 9 db AAA számot, amelyek számjegyei azonosak és így marad utána 891 db szám. A 2. szűrő után marad 810 db szám, mert kimarad az a 81 db AAB alakú szám (ahol a százas és tízes helyiértéken lévő számjegyek megegyeznek) az összesen 90 db-ból, ami még a folyamban maradt az 1. szűrő után. A 3. szűrő kihagy 81 db ABB alakú számot és meghagy 729 db számot. A 4. szűrő kihagy 80 db ABA alakú számot és meghagy 648 db ABC alakú számot.

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, 13-16. óra: Tömbök, valamint 21-24. óra: Objektumorientált programozás, 2. és 3. rész alkalmaihoz kötődik.