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

érettségi logó

érettségi logó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

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: 45=210=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

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

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ő):

4. megoldás

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

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

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

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(n1)
  • 1,…,2,n → 0…001(n1)
  • n,…,n,n → (n1)...(n1)

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.

Tankocka – Hiányos szöveg: objektumorientált programozás

Folytatjuk Tankockák blog bejegyzés sorozatunkat. A feladatban ki kell egészíteni az objektumorientált programozás bevezetéséhez tartozó hiányos szöveget. Ez főként a Java SE szoftverfejlesztő tanfolyamunk tematikájához kötődik.

Kiemelten fontos, hogy az OOP alapfogalmaival, összefüggéseivel tisztában legyünk. Ez a közös szakmai szókincs alapvető része. Enélkül gyakorlatilag nincs is miről beszélni. Kapcsolatok, időbeliség, ok-okozati összefüggések ismerete szükséges az OO tervezéshez. Enélkül egy feladatspecifikáció alapján nem tudunk modellezni. OO modell nélkül egy komolyabb feladat nem oldható meg. Mindez oda-vissza kölcsönösen segíti az adatbázis adatmodellező tevékenységét is.

Digitális Témahét 2022

A Digitális Témahét 2015-ben 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 2018/2019-es tanévben már több mint 3000 oktatási projekt valósult meg, közel 8000 pedagógus és 135000 diák részvételével.

A 2021/2022-es tanévben a rendezvény április 4-8. között valósult meg. 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 digitális technológia alkotó használata és az algoritmikus gondolkodás fejlesztése;
  • a kiemelt figyelmet igénylő tanulók fejlesztése és bevonása;
  • a nevelési-oktatási intézmények közötti együttműködés élénkítése;
  • a határon túli magyar pedagógusok és oktatási intézmények bevonása;
  • a digitális biztonság a mindennapi pénzügyeinkben;
  • az intézményen belül történő pedagógus közötti együttműködés élénkítése, a projektmódszer alkalmazásának kiterjesztése olyan kollégákra, akik még nem ismerik;
  • ebben a tanévben kiemelten: digitalizáció a 21. században, digitális írástudás és digitális gyermekvédelem, mesterséges intelligencia.

Rendezvényünk plakátja

Az it-tanfolyam.hu 2022-ben is csatlakozott a rendezvénysorozathoz. Oktatóink meghirdettek öt programot a https://digitalistemahet.hu weblapon. A programjainkra 2022. április 8-án 18:00-21:00 óráig került sor.

Köszönöm oktató kollégáimnak, hogy örömmel csatlakoztak. Mindannyian jól éreztük magunkat. Igazán tartalmas programot állítottunk össze. Idén is szívesen csatlakoztunk és szívesen emlékszünk majd rá. A résztvevőinknek is köszönjük, hogy ellátogattak hozzánk. Újra az offline világban találkozhattunk.

A “Tervezzünk közösen kommunikációt gyűjtögető robotok között!” című interaktív előadásomat a Digitális Témahét 2022 rendezvényhez tartozó több partnerintézményben is megtartottam jelenléti és online formában is.

 

Tankocka – Hang/Film felirattal: a barátkozás algoritmusa Dr. Sheldon Cooper szerint

Folytatjuk Tankockák blog bejegyzés sorozatunkat. A feladatban válaszolni kell a videóban megjelenő – algoritmusokhoz kapcsolódó – hat kérdésre! A videó a népszerű Agymenők (The Big Bang Theory) című sorozat 2. évad 13. epizódjából való, melynek címe: A barátkozás módszertana (The Friendship Algorithm). Ez a témakör főként az alapozó tanfolyamunkhoz kötődik: Java SE szoftverfejlesztő tanfolyam.

Az algoritmusok a tipikusan programozási nyelvtől független, konvertálható tudást jelentik és mindig szükség van rájuk. Többféle jelölésrendszer is kapcsolódik hozzájuk, például folyamatábra, mondatszerű leírás, struktogram, Jackson-ábra. Az UML jelölésrendszer elemei közül az objektumok kommunikációját, viselkedését leíró ábrák is algoritmusleíró eszköznek tekinthetők.

Ratkó István emlékest 2022

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):

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.