Sakktábla (75 megoldás)

Adott az alábbi, sakktáblát kirajzoló program:

print("XX..XX..XX..XX..")
print("XX..XX..XX..XX..")
print("..XX..XX..XX..XX")
print("..XX..XX..XX..XX")
print("XX..XX..XX..XX..")
print("XX..XX..XX..XX..")
print("..XX..XX..XX..XX")
print("..XX..XX..XX..XX")
print("XX..XX..XX..XX..")
print("XX..XX..XX..XX..")
print("..XX..XX..XX..XX")
print("..XX..XX..XX..XX")
print("XX..XX..XX..XX..")
print("XX..XX..XX..XX..")
print("..XX..XX..XX..XX")
print("..XX..XX..XX..XX")

Végezz el ezen két módosítást!

  • Szüntesd meg a sormintát! Ahol látsz bármilyen ismétlést, azt mind tüntesd el a programból!
  • Jelenleg minden mező 2 egység széles: két darab X és . van vízszintesen és függőlegesen is. Oldd meg, hogy a felhasználó adhassa meg ezt a számot a program indítása után, vagyis hogy beállítható legyen a rajz mérete!

A szorgalmi feladatokkal egy pontversenyben is részt lehet venni. A verseny állása a szorgalmik oldalán tekinthető meg. Alapbeállítás szerint anonim módon jelensz meg a táblázatban. Ha szeretnél névvel megjelenni vagy teljesen eltűnni, az admin felületen beállíthatod.

Elfogadott megoldások: 75 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-09-19 04:00:00.

Kismutató, nagymutató (74 megoldás)

A feladat egy Python program írása, amely három számot vár a bemenetén. Ezek egy időpontot mutatnak: óra, perc és másodperc. A program ezek után teknőcgrafikával rajzoljon egy órát, amely a megadott időpontot mutatja.

Az órán legyen meg mindhárom mutató! A mutatók ne mindig pontosan az egész órára és percekre mutassanak! (Ha pl. fél kilenc van, a kismutató a nyolcas és a kilences között van középen. De ilyet a percmutató is csinál.) A számlapról ne hiányozzanak a percenkénti osztások sem, sőt az egész órákhoz tartozó osztások legyenek különbözőek, mint a többi! A megrajzolt óra ízlés szerint díszíthető is. Inspirációt találsz az Extrák / Galériák menüpont alatt.

Figyelj arra, hogy a feladatkiírás összes elvárását betartsd. És ne maradjon le a mainloop-os sor sem a végéről! A beolvasáshoz használhatod az input vagy a turtle.numinput függvényt is, ez rád van bízva.

Elfogadott megoldások: 74 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-09-25 04:00:00.

BF értelmező (13 megoldás)

++++++++[>++++++++<-]>++.++++. – ez egy Brainfuck (BF) nyelvű program, amelyik kiírja a szabványos kimenetére, hogy „BF”. Ha még nem olvastad volna, akkor nézd meg az algoritmusokról szóló írást és a Brainfuck nyelvről szólót. Ezek kellenek a feladat megértéséhez. Ugyanis a feladat egy BF értelmező írása Pythonban: egy olyan programot kell írni, amely le tud futtatni egy ilyen nyelven írt programot.

Az értelmezőnek mind a nyolc utasítást ismernie kell. A végtelen hosszú szalag helyett 32768 eleműt kell venni, amely a gép indításakor nullákkal van feltöltve. A cellák egész számokat tárolnak. Ezen az olvasó- és írófej bekapcsoláskori pozíciója a nulladik cella. Ha a BF program bármelyik irányba lelépne a 32768 elemű szalagról, akkor a futását meg kell szakítani. Az értelmezendő programot a Python forráskódban kell eltárolni, sztring formájában, amelynek a neve programkod:

programkod = ",+[-.,+]"

A futtatott programnak akkor van vége, amikor az értelmező eléri a programszöveg végét. A BF program kapja meg a Python program szabványos bemenetére érkező karaktereket, olyan módon, hogy a fájl vége jelet a −1-es értékre kell lefordítani számára. A Python program szabványos kimenete legyen a BF program kimenete. Azon kívül legfeljebb hibaüzenetet írhat ki.

Egyetlen egy karaktert az import sys modul sys.stdin.read(1) függvényhívásával lehet beolvasni; ez sikeres beolvasás esetén egy egyetlen karakterből álló sztringet ad, fájl vége jel esetén pedig üres sztringet. Egyetlen karaktert kiírni a print()-tel is lehet, de van sys.stdout.write() is.

Programozd is a képzeletbeli gépet, amelyet életre keltett az értelmeződ! A Python forráskódnak beépítve tartalmaznia kell az alábbi BF programok közül valamelyiket:

  • A keresztnevedet kiíró program.
  • Program, amely beolvassa a teljes bemenetét, utána pedig kiírja azt visszafelé. (Bemenet → tenemeB.)
  • Program, amely beolvas egy szöveget, ésmindentszóköznélkülvisszaírakimenetére.
  • Egyéb, tetszőleges program, ez esetben viszont legyen hozzá magyarázat!

Megjegyzések.

  1. Az Internet tele van BF értelmezőkkel, amelyek forráskódban is elérhetőek. Ezeket ne nézd meg, mert akkor nincs semmi értelme a feladatnak. Megoldásként végképp ne küldj be ilyet! BF nyelvű programokat viszont letölthetsz, és kipróbálhatsz a saját értelmeződdel. Vigyázz, akad pár „nem szabványos”.

  2. Ha nem fut a Sierpiński-háromszög programja az értelmeződben, akkor biztos nem jól csináltál valamit. Olyan megoldást ne küldj be, amin az a program nem működik (legfeljebb azért, hogy útmutatást kérj, de akkor ezt jelezd). Itt a kód:

programkod = "[ThisprogramprintsSierpinskitriangleon80-columndisplay.]>++++[<++++++++>-]>++++++++[>++++<-]>>++>>>+>>>+<<<<<<<<<<[-[->+<]>[-<+>>>.<<]>>>[[->++++++++[>++++<-]>.<<[->+<]+>[->++++++++++<<+>]>.[-]>]]+<<<[-[->+<]+>[-<+>>>-[->+<]++>[-<->]<<<]<<<<]++++++++++.+++.[-]<]+++++*****Made*By:*NYYRIKKI*2002*****"
  1. Ez a feladat nehéznek tűnik ELSŐRE, de a megoldás egyszerű, 30-40 sor. Egyedül a bezáró (vagy nyitó) zárójelpár megkeresésének algoritmusa nem triviális. Ötlet: Ha keressük egy [ bezáró párját, akkor addig kell menni, amíg meg nem találjuk az első ] karaktert. De ha közben újabb [ karakterrel találkozunk, akkor már a második ]-t keressük. Tehát kell egy változó, amelyik azt tárolja, hányadik ]-t keressük – vagy amikor ugrunk egy ciklus elejére, hányadik [-t.

  2. Használhatsz függvényeket, de ne használj globális változókat! Ne használj rekurziót sem (ha már tanultál róla régebben esetleg). Az ellentmond a feladat mondanivalójának; a rekurzió által olyan, mintha lenne egy harmadik szalag, a verem.

  3. Ellenőrizd beadás előtt a fájl vége jel kezelését! Hogy ez hogyan működik, az fejlesztőkörnyezettől és operációs rendszertől függ; üres sorba írt F6 + Enter vagy Ctrl-D szokott lenni. Próbáld ki, melyikre dob az input() egy EOFError típusú hibát! Erre a bemenetre ad üres sztringet a sys.stdin.read(1).

Elfogadott megoldások: 13 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-10-08 04:00:00.

„Cmabgidre eeygteemn vzétget ktuatás” (47 megoldás)

„A Cmabgidre eeygteemn vzétget ktuatás sernizt, tseljeen mdngiey, hgoy a lerít szvaak bsebeljeén mleyin serednbron vannak a btűek, cask az sámzít, hgoy az eslő és az ustloó bteű a hyeéln lyegen. A tböbi titsáaoln meg lehet keevvre, a sövezg akokr is osaalhtvó. Ez aézrt van, mret nem mdnien eyegs beűtt oavlnusk, hnaem tleejs svaaakzt eygben.”

Szóval még egyszer, most rendesen: „A Cambridge egyetemen végzett kutatás szerint, teljesen mindegy, hogy a leírt szavak belsejében milyen sorrendben vannak a betűk, csak az számít, hogy az első és az utolsó betű a helyén legyen. A többi totálisan meg lehet keverve, a szöveg akkor is olvasható. Ez azért van, mert nem minden egyes betűt olvasunk, hanem teljes szavakat egyben.” A kutatás egyébként nem pont erről szólt, és a pontos állítás nem ez; a történet elolvasható itt: Cmabridge.

Írj egy programot, amely beolvas egy szöveget, és kiírja azt a fenti leírás szerint megkavarva! Útmutató:

  • Előbb írj egy külön programot, amelyik egyetlen egy szó karaktereit tudja megkeverni. Legkönnyebb úgy, ha az összeset megkevered, és utána írsz olyan programrészt, amelyik az első és az utolsó karaktert érintetlenül hagyja. Írásjelekkel most ne foglalkozz. Figyelj arra, hogy a sztringek csak olvashatóak (immutábilisak): nem írhatod felül egy karakterüket, hanem új sztringet kell építeni.

  • Módosítsd ezt úgy, hogy még mindig egy szón dolgozol, de figyelembe veszed, ha annak írásjel van a végén! Pl. „alma!”, vagy „ajtó...”.

  • Ha ez működik, akkor „építsd körbe” olyan programrésszel, amelyik egy lista szavain alkalmazza ezt az algoritmust, minden szót kicserélve az összezagyváltra.

Nézz utána, mit csinál a sztringek .split() és .join() művelete, és használd azt a végleges megoldáshoz!

Elfogadott megoldások: 47 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-10-08 04:00:00.

Angry Birds 🐦 (17 megoldás)

Ebben a feladatban a ferde hajítással kell dolgozni.

Angry birds

Adott egy Angry Birds pálya. Olyan programot kell írnod, amelyben játszani lehet a játékot. A kör alakú madarat valamilyen szögben és sebességgel lehet kilőni. A felhasználó (szög;sebesség) kombinációkat ad meg, amivel megpróbálja egyből (visszapattanás nélkül) eltalálni a szintén kör alakú malacot. A felhasználó többször is próbálkozhat; játéknak akkor van vége, ha sikerült egy olyan kombinációt adnia, amellyel a malacot el lehet találni.

A kipróbált röppályákat ki kell rajzolni. Visszapattanásokat nem kell modellezni, vagyis veheted úgy, hogy a madár-malac találaton kívül nincs más ütközés. A rajzon szerepelhetnek díszletek is, napocska, felhő, fák, hegyek, amelyek a számítás szempontjából nem lényegesek. A programban szereplő adatok (madár és malac koordinátái, mérete) változóval kell legyenek megadva. Ne szerepeltesd ugyanazt a számkonstanst rengeteg helyen a forráskódban!

Néhány adalék a teknőcgrafikához:

  • A .textinput() és .numinput() függvényekkel szöveget és számot lehet beolvasni. Paramétereik: az ablak címe és a kérdés. Használd ezeket input() helyett, mert így szebb a program!

  • Ha szeretnél animálni (nem kötelező), a .tracer(0) függvényhívással a rajzolás követése kikapcsolható. Ez hasznos lehet a kezdeti háttér megrajzolásakor. Amikor a követés ki van kapcsolva, a megrajzolt elemek csak .update() függvényhívás hatására jelennek meg az ablakban. A .tracer(1) kapcsolja vissza a szokásos követést: a lassú mozgás, repülés hozzáad a játékélményhez.

  • Egyébként lásd a Turtle graphics oldalt.

Az ütközés számítása legyen matematikailag korrekt! Két kör akkor „ütközik”, ha a középpontjaik távolsága kisebb, mint a sugaraik összege. Ezt rajzold le papíron, és látni fogod, miért van így. A teknőcgrafika modult adattárolásra ne használd; ha lekérdezed a teknős koordinátáját a .pos() függvénnyel, biztosan nem lesz elfogadva a programod.

Elsősorban a programozási feladatra ügyelj (játékmenet, számítások)! A játék megjelenése, a grafika szépsége csak másodlagos. Tetszőlegesen szépítheted a rajzot, de ha a malac és a madár a rajzon csak két kör, az is jó.

Értékelés:

  • 1 pont, ha működik. Természetesen a tárgyban hirdetett kódolási szabályokat ilyenkor is be kell tartani (minden kód a main-ben, típusok helyes használata stb.)
  • 2 pont, ha emellett szépen függvényekre van bontva; nincs kódduplikáció, látható a forráskódon a top-down megközelítés.

Tiltott szavak: position; pos; xcor; ycor; distance

Elfogadott megoldások: 17 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-10-19 04:00:00.

Egri csillagok – NZH gyakorlófeladat (39 megoldás)

Az alábbi feladat megoldásával az algoritmusokat és a sztringeket lehet gyakorolni.

Adott a következő fájl: egri.txt. Ez az Egri Csillagok szavainak egy részét tartalmazza, az egyszerűség kedvéért kisbetűsítve és ékezettelenítve. Illeszd be ezt egy Python forráskódba! Definiálj egy változót, és inicializáld úgy, hogy a szavakat tartalmazza!

  1. Kérj egy fél szót a felhasználótól, és keresd ki a listából azokat a szavakat, amelyek tartalmazzák azt! Pl. „alma”, „alma almagyaron irgalmazzanak jutalmad oltalmazza tilalmas”.

  2. Írj függvényt, amely paraméterként átvesz egy szót, és visszatér a következő sztringek egyikével: magas, mély, vegyes. A függvény használatával számold meg, a szavak listájában hány magas, mély, vegyes hangrendű szó található! Írd ki ezeket a számokat, és melléjük azt is, hogy hány százalékot jelentenek az összes szóhoz képest! Mély hangrendű az, amely csak a, o, u magánhangzót tartalmaz, magas, amelyik csak e, i magánhangzót. (Az ö, ü hangokat tartalmazó szavak szándékosan nincsenek a listában.)

  3. Kérj a felhasználótól egy szót, és írd ki a képernyőre, hogy a beírt szó nem tartalmaz magánhangzóka, vagy csak egyforma magánhangzókat tartalmaz, esetleg különféle magánhangzókat tartalmaz! A magánhangzók: a, e, i, o, u, mert ékezettelenítve vannak a szavak. Az előzőhöz hasonlóan oldd meg ezt a feladatot is, legyen egy függvényed, amelyik csak egy szón dolgozik.

  4. Írj függvényt, amely egy szót kap paraméterként, és igaz vagy hamis értékkel tér vissza attól függően, hogy a szó betűi ábécé szerint növekvő sorban vannak-e! A „bot, hit, most” szavak például ilyenek. A függvény használatával írj programrészt, amellyel a szavak listájából kiválogatod és kiírod az ilyeneket!

  5. Keresd ki azokat a szavakat, amelyek első és utolsó betűjét elhagyva is értelmes, a listájában szereplő szó jön ki, pl. „lennie”, „enni”. Írd ki az eredeti és a rövidített szavakból képzett párokat!

Az egyes részfeladatok által generált kimenetet válaszd el a képernyőn, írd ki, melyik részlet hányadik részfeladathoz tartozik! Ahol lehet, használj beépített függvényt (az str típus függvényeit)!

Előírás a feladatban, hogy a tárgyban eddig tanult eszközöket használd, és ne olyanokat, amiket itt-ott találtál a neten! A gyakorlás lényege az, hogy te magad, a tanult eszközökből próbálod megépíteni a megoldást, nem pedig az, hogy megkeresed, mások hogyan oldottak meg hasonló feladatokat. Ha nem így teszel, az visszautasítás oka lesz.

Ellenőrizd a megoldásod, ne adj be olyan programot, ami nincs rendesen kitesztelve! A mély hangrendű szavak 626-an vannak; ha nem ez jön ki, biztosan ellenőrizned kell a megoldást. A lennie-enni pár is szerepel a szótárban.

Tiltott szavak: set;sorted;open;sort

Elfogadott megoldások: 39 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-10-22 04:00:00.

Rendezés, de milyen? (17 megoldás)

Adott az alábbi rendezőalgoritmus.

lista = [9, 5, 8, 2, 7, 5, 3, 8, 2, 1]

for x in range(0, len(lista)-1):
    for y in range(x + 1, len(lista)):
        if lista[x] > lista[y]:
            tmp = lista[x]
            lista[x] = lista[y]
            lista[y] = tmp

print(lista)

Foglald össze pár mondatban, hogyan működik az algoritmus! Utána pedig véleményezd, tételesen válaszolva ezekre a kérdésekre:

  1. Helyes vagy nem?
  2. Gyors vagy nem? Lépésszámát tekintve.
  3. Átgondolt vagy nem? Mit használ fel a külső ciklus abból, amit a belső ciklus csinált?
  4. Változtatnál rajta? Mit?
  5. Ha esetleg tanultál erről az algoritmusról: mi a neve?

Indokold is az állításokat! Ez a feladat nem könnyű préda, nem elég csak pár szót beküldeni a pontért. Sajnos az eddigi években a tapasztalat az volt, hogy elterjed a megoldás, ezért javítva is csak határidő után lesz. Gondold át a megoldásod beküldés előtt!

Tiltott szavak: kissebb

Elfogadott megoldások: 17 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-10-22 04:00:00.

Azon pontok mértani helye... (18 megoldás)

Ez az első grafikus szorgalmi. A megoldás előtt tanulmányozd az Pygame-ről szóló írást, azon belül is az „Első program” fejezetet!

A feladat a következő. Egy olyan programot kell írnod, amely megnyit egy 640×480 pontból álló ablakot. Ezután végigpásztázza ennek összes képpontját, az alábbiak szerint színezi őket.

  • Pirosra színezi azokat, amelyek kb. 200 képpontnyira vannak a (320;240) ponttól.
  • Zöldre színezi azokat, amelyek távolságösszege a (240;200) és (400;280) pontoktól kb. 250 képpontnyi.
  • Kékre azokat, amelyeknél a (240;240) ponttól és a (400;240) ponttól vett távolságok különbségének abszolút értéke kb. 100 képpont.
  • Végül pedig fehérre azokat, amelyeknél a távolság a (320;240) ponttól, illetve az x=400 egyenestől kb. ugyanakkora.

A „kb. valahány képpont”-nál az egyenlőség határát nevezd epszilonnak, és add meg a programban egy eps nevű változóval! Ennek jó értéke lehet az 5, de próbálhatsz kisebbeket vagy nagyobbakat is (pl. 2 vagy 10). Az egyes alakzatoknak neve is van (középiskolában tanult alakzatok), ezeket írd bele kommentben a programba!

  • 1 pontért: készítsd el a rajzot! Használd fel a programban az előadáson mutatott Pont osztályt!

  • 2 pontért: Írj a Pont osztályhoz kivonó __sub__ és abszolút érték __abs__ operátort! Ügyelj arra, hogy ezek tényleg azt a műveletet végezzék, amit a nevük mond. A p1 - p2 kifejezés a pontok közti vektort (vektorok különbségét) kell adja, szintén egy pontot. Az abs(p) kifejezés pedig a vektor hosszát (origótól való távolságát).

Beadás előtt ellenőrizd:

  • Nem nevezted-e i-nek és j-nek a koordinátatengelyeket; nem ez a nevük.
  • Nincs-e sok kódduplikáció a feladat matematikai részében. Bárhol ismétlést, hasonlóságot látsz, ahhoz függvény kell. Pl. a Pitagorasz-tétel rengetegszer kelleni fog, de más ilyet is fogsz találni.
  • Nincs-e if (xxx) return true; else return false; alakú kódrészleted.
  • Nem használod-e a.__sub__(b) és a.__abs__() alakban az operátorokat. Ha igen, javítsd ki. Lásd az előadást!

Elfogadott megoldások: 18 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-10-29 04:00:00.

Világtérkép 🌍 (17 megoldás)

Adott az alábbihoz hasonló formátumban két számsor: vilag.txt és tavak.txt.

-59.6 -80.0
-62.3 -80.9
-64.5 -80.9
-61.9 -80.4
e
-159.2 -79.5
-162.4 -79.3
-160.2 -78.7
e

A fájlok világtérképet tartalmaznak. Minden sor egy GPS pozíciót ad meg. A számpárok első tagja a hosszúsági érték (longitude; -180...+180 fok nyugatról keletre), második tagja pedig egy szélességi érték (latitude; -90...+90 fok délről északra). A számpárok sorozatai sokszögeket írnak le, a kontinensek és nagyobb szigetek, illetve tavak körvonalaival. Minden szigetet vagy tavat egy olyan sor követ a fájlokban, amiben csak egy "e" betű van. Mentsd le a fájlokat jobb klikk, mentés másként funkcióval!

világtérkép

A feladatod egy olyan teknőcgrafikás programot írni, amely kirajzolja a világtérképet. Színeket tetszőlegesen választhatsz, az ablak viszont legyen 1080×540-es vagy 720×360 méretű! A területek ne csak kitöltve legyenek, hanem körberajzolva is. Jelöld be a BME-t a térképen!

Építsd fel a programban a következő adatszerkezetet! Egy fájl adatait olvasd be egy listába. A lista tartalmazzon sokszögeket, amelyek önmaguk szintén listák, bennük GPS koordinátákat tároló objektumokkal! Tehát pl. szigetek[3][4].x legyen a 3. sziget 4. csúcspontjának x koordinátája (földrajzi hosszúsága).

Ötletek a megvalósításhoz:

  • Jól használható itt a teknőcgrafika már ismert begin_fill() és end_fill() függvénye, amelyek tetszőlegesen bonyolult, akár konkáv sokszögeket is ki tudnak színezni. A goto() függvénnyel ugorhatsz egy megadott pozícióra, forgolódás nélkül. A color() függvény két paramétert is kaphat, a körvonal és a kitöltés színét.

  • Az ablak méretét a setup() függvénnyel adhatod meg. A koordinátarendszert a setworldcoordinates() függvénnyel módosíthatod, így GPS koordináta → képernyőkoordináta átváltással nem kell bajlódnod, mert csinálja a turtle modul magától.

Ellenőrizd beadás előtt:

  • Pontosan azt az adatszerkezetet építetted-e fel, amit a feladat kér. Ez elsődleges értékelési szempont.

  • Legyenek körbezárva az alakzatok! Grönland északi részén tudod ellenőrizni, hogy ez megtörtént-e. Emiatt viszont ne tedd egy sokszög csúcsai közé kétszer ugyanazt a pontot!

  • Ne duplikálj kódot, írj függvényeket!

Elfogadott megoldások: 17 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-11-05 04:00:00.

Palacsintarendezés 🥞 (16 megoldás)

Nem csak helyben rendezések léteznek, mint amilyenek előadáson szerepeltek – amelyekben az elemi lépés két elem cseréje.

Ha egy palacsintatornyot szeretnénk rendezni (felülre a kicsik, alulra a nagyok), akkor nagyon nehéz lenne két palacsintát megcserélni benne. Egyszerű művelet viszont a torony egy részének átfordítása: csak benyúlunk egy lapáttal valamelyik két palacsinta közé, és egy ügyes mozdulattal átfordítjuk az egészet.

palacsintarendezés

A programozásban az ilyen elven működő rendezést, mily meglepő, palacsintarendezésnek nevezik (pancake sorting). Külön elmélete van, több algoritmust is kitaláltak hozzá. A legkevesebb szükséges átfordítás számát meghatározó képlet (n függvényében, ahol n a torony mérete), máig ismeretlen.

A legegyszerűbb algoritmus a közvetlen kiválasztásos rendezéshez hasonlít. Ebben megkeressük a legnagyobb palacsintát, aztán a fölötte lévő résszel együtt átfordítjuk. Így a legnagyobb felülre kerül, és a teljes tornyot átfordítva betehetjük azt alulra. A feladat: írd meg ezt a palacsintarendezést! A lista álljon 10 egész számból, és minden megfordítási lépés után írd ki a listát, hogy látszódjon a rendezés! Ügyelj arra, hogy az algoritmus lépésenként két megfordítást használ; mindkettő után meg kell jeleníteni a számsort. Alkalmazd a Python listaműveleteit (vágás, összefűzés, megfordítás) – ilyen feladatokra ne írj saját ciklust!

Választásod szerint a kiírás helyett megjelenítheted a rendezést teknőcgrafikával vagy pygame modullal is. Teknőcgrafika esetén mindenképp legyen .tracer(0) és .update(); ha nem használtad még ezeket a függvényeket, olvasd el az Angry Birds szorgalmi vonatkozó bekezdését.

Elfogadott megoldások: 16 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-11-12 04:00:00.

Levesek (26 megoldás)

Egy rendezvényszervező cég a rendelt ételeket összesíti. Minden fogáshoz többféle étel közül is választhatnak a vendégek (pl. hagymaleves sajttal és krutonnal, paradicsomleves, rákóczi túrós, somlói galuska, sör, bor, ...). Az összes választott ételt egy szövegfájlban kapjuk meg:

paradicsomleves
somlói galuska
kóla
paradicsomleves
juhtúróval töltött gombafejek
ásványvíz
sör
...

Fontos kérdés lenne természetesen, hogy melyik ételből hány adag kell. De amivel most foglalkozni kell, az a levesek kérdésköre. A konyhán tudni szeretnék, hogy végül kell-e levest főzniük, és ha igen, akkor egyfélét vagy többfélét. Ezen múlik, hogy milyen típusú edényekben kell szállítaniuk és tálalniuk majd. A fenti összesített rendelésben egyféle leves van (paradicsom), de ha valaki hagymalevest kérne, akkor már többféle edényre is szükség lenne.

A feladatod a következő: írj egy függvényt, amelyik paraméterként egy szövegfájl nevét kapja. A fájl minden sorában egy étel neve szerepel. A visszatérési értékében azt kell ennek megadnia, hogy a) nincs leves, b) egyféle leves, vagy c) többféle leves van a rendelések közt. Ezeket onnan ismered meg, hogy a nevükben szerepel valahol a „leves” szó. A visszatérési értékhez definiálj egy felsorolt típust is, és használd azt!

Írj főprogramot, amelyben meghívod a fenti függvényt a rendelesek.txt nevű fájlra, és kiírod az eredményt!

Elfogadott megoldások: 26 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-11-19 04:00:00.

Morze dekóder 🌳 (19 megoldás)

Az előadáson láttad, hogy bináris fából morzekódot dekódoló fát is lehet építeni.

morze

Keresd meg a neten a jelek táblázatát, és írj programot, amelyik felépíti egy táblázat alapján ezt a dekódoló fát!

Írj függvényt, amelyik megkap egy jelsorozatot, pl. ".--." és a dekódoló fát; ebből pedig visszaadja a dekódolt betűt, pl. "P"!

Írj főprogramot, amelyik beolvassa és dekódolja a morze.txt nevű fájlt, amelyikben az alábbihoz hasonlóan egy morzekóddal írt szöveg van. Ebben betűkhöz tartozó jelsorozatokat szóköz választja el egymástól, a szavakhoz tartozóakat pedig újsor karakter. Olvasd be a fájlt, és írd ki a dekódolt szöveget a kimenetre!

.--. -.-- - .... --- -.
..-. - .--

Értékelés:

  • 1 pont, ha a dekódolás működik a fa segítségével.

  • Még 1 pont, ha a fát is algoritmussal építed meg; kiindulva egy Morze táblázatból, amelyik ábécé rendben (!) tartalmazza a jeleket.

Elfogadott megoldások: 19 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-11-27 04:00:00.

Szintaxisfa 🌳 (13 megoldás)

Mint tudjuk, a fák nem csak keresőfák lehetnek. A hierarchiának más szerepe is lehet: például kifejezéseket, operátor–operandus viszonyokat is leírhatunk velük. Például az alábbi bináris fa a (3 + x) * 8 kifejezést, függvényt tárolja:

A fa gyökere egy szorzat típusú csomópont. Ennek gyerekei az összeg és a 8-as konstanst tartalmazó csomópontok. Az összeg gyerekei pedig 3 és x. Az operátoroknak vannak gyerek csomópontjaik (miknek a szorzata, miknek az összege), az x-nek és a konstansoknak viszont nincsenek, azok levelek a fában.

Építs fel egy ilyen fát a programodban! Elég, ha csak az összeadást és a szorzást ismeri. Építsd fel a programban a rajzon látható függvényt!

  • Definiálj ehhez felsorolt típust vagy konstansokat, amelyek a kifejezés típusát mutatják!

  • Definiálj osztályt a bináris fa csomópontjához! Tárold mindig ezt el a csomópontban, hogy tudd, hogyan kell kezelni egy adott csomópontot! Lesznek benne olyan adattagok is, amelyeket a csomópont típusától függően néha nem használsz semmire.

  • 1 pontért: Tedd lehetővé, hogy ki lehessen értékelni a benne tárolt függvényt egy adott helyen, pl. x = 2 esetén 40 a benne tárolt függvény értéke. Írj függvényt, amelyik megkapja egy fa gyökerét és az x értékét, majd megadja a függvényt értékét az adott helyen! A fenti példában ez kiertekel(gyoker, 2) lenne, ahol a függvényhívás értéke 40.

  • Még 1 pontért: Oldd meg, hogy ki lehessen írni a függvényt magát! A kiírásban a kelleténél több zárójel lehet, de kevesebb ne legyen (tehát pl. ((3 + x) * 8) elfogadható, de 3 + x * 8 nem, mert mást jelent). Írj függvényt, amelyik sztringgé alakítja a függvényt: sztringge(gyoker). Választásod szerint ez lehet az __str__ operátor is.

Elfogadott megoldások: 13 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-11-27 04:00:00.

Halmaz és bináris keresés (14 megoldás)

A laborban szerepelt egy hash táblás feladat. Ebben szavakat kellett tárolni egy hash táblában, amelyet halmaznak kellett használni: be lehetett tenni egy szót (legfeljebb egyszer), kivenni azt, illetve megnézni, hogy szerepel-e a szó a halmazban.

A halmaz tárolására egy másik igen hatékony módszer is kínálkozik, ez pedig a rendezett lista. Miért hatékony ez?

  • Eleme-e: a rendezett listában bináris kereséssel, azaz intervallumfelezéssel meg tudjuk találni a keresett elemet. Ez O(log n) lépésben történik.
  • Beszúrás: ha nincs az elem a rendezett listában, a bináris keresés pont ott áll meg, ahol lennie kéne, vagyis ahova be kell szúrni.
  • Törlés: a törlendő elem helyének megkeresése itt is O(log n) lépésben történhet.

1 pontért: Írd meg a halmaz_letrehoz(), halmaz_betesz(), halmaz_eleme_e() és halmaz_kivesz() függvényeket úgy, hogy azok mindegyike rendezett listával és bináris kereséssel dolgozzon! Írj ezekhez teszteket az assert() függvénnyel, a laboron tanult módon!

A rendezett tárolás lehetővé teszi azt is, hogy a halmazműveleteket, azaz például a metszetet és az uniót, nagyon gyorsan elő tudjuk állítani: egész pontosan O(n) időben. Ezekhez az összefésülés algoritmusát kell alkalmazni, amelyet az összefésülő rendezésről szóló írás első része is bemutat. Az algoritmus lényege, hogy a rendezett számsorok elejét hasonlítjuk mindig össze. Ha ott egyforma elem van, akkor az mindkét számsorban szerepel:

4, 8, 9, 15
4, 12, 15, 17

Ha az első nagyobb, mint a második, akkor a második listában mehetünk előre. Például a következő számsorok elejét, a 8-at és a 12-t látva biztosak lehetünk, hogy a 8 nem szerepel az alsó listában, mert akkor a 12 előtt kellett volna lennie:

8, 11, 17, 34
12, 17, 35, 89

Ugyanez fordítva igaz akkor, ha a második nagyobb, mint az első.

Még 1 pontért: Írj meg további három függvényt! Legyenek ezek a halmaz_metszet(), a halmaz_unio() és a halmaz_egyenlo_e(). Az előbbi kettő állítsa elő két halmaz metszetét és unióját O(n) időben, majd térjen vissza az új halmazokkal. A harmadikkal pedig lehessen két halmazt összehasonlítani. Teszteld ezeket a függvényeket is, előbb az egyelőségvizsgálót önmagában, majd a metszeteket és az uniókat annak segítségével!

Tiltott szavak: sort;sorted

Elfogadott megoldások: 14 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-12-03 04:00:00.

Trie fa (11 megoldás)

A trie fa (trie tree, radix tree, prefix tree) egy olyan adatszerkezet, amelyben sztringek tárolhatók, és azok prefix alapján könnyen kereshetők. Alább látható egy ilyen fa, amely a tea, tej, ki és kis szavakat tartalmazza. A t, te és k sztringek nincsenek a fában; azok a csomópontok érvénytelenek, csak az előbbi szavakhoz vezető út miatt kellett létrehozni őket.

1 pontért: Írj programot, amely ilyen szótárat épít! Lehessen egy egyszerű felületen hozzáadni a szavakat, és ellenőrizni, benne vannak-e a szótárban!

> betesz tea
ok.

> betesz teli
ok.

> keres tea
benne van.

> keres te
nincs benne.

> kilep

A fát kétféleképpen építheted fel, válaszd az egyik lehetőséget a kettő közül:

  • Feltételezheted, hogy csak angol kisbetűs szavak lesznek. Ezekből összesen 26 darab van (a-tól z-ig), ezért a fában a gyerekeket egy 26 elemű listában tárolod a szokásos bal és jobb referenciák helyett.

  • A gyerekeket egy dict-ben tárolod. Ebben a kulcs a betű lesz, amelyik az adott irányba visz.

Még 1 pontért: A programnak képesnek kell lennie a meglévő szavak listázására is. Például:

> listaz
tea
teli

Ehhez se tárolj sztringeket a csomópontokban, hanem ugyanúgy csak érvényes/érvénytelen jelölést, mint az előzőhöz!

Elfogadott megoldások: 11 darab.
Szerezhető: 2 pont. Leadási határidő: 2020-12-03 04:00:00.

NHF galéria 2020 (17 megoldás)

Ha szeretnéd a nagy házidat beküldeni a „szépségversenyre”, azt itt teheted meg. A formai követelmények:

  • Egy maximum 800×600-as, igényesen, széleken nem hibásan kivágott képernyőkép PNG formátumban: kep.png.
  • Feladat címe és rövid leírás, helyesírási hibáktól és elgépelésektől mentesen, txt formátumban: leiras.txt.
  • Hozzájárulás egy másik txt-ben, hogy megjelenhetsz névvel a honlapon: hozzajarulas.txt.
  • Mindezek egy ZIP fájlba csomagolva.

Ha méretezned kell a képet, olyan programmal csináld, amelyik szépen teszi azt, pl. GIMP! Leginkább a betűkön látszik.

Figyelem: ez a feladat nem potya +1 pont! A beküldött képen látszódnia kell, hogy energiát fektettél a program megjelenésének fejlesztésére. Ez grafikus programokra is érvényes, konzolos programokra még inkább. A csúnya képek, hejjes irási , hipás leírások pontot nem kapnak, csak citrom-díjat 🍋. A szépség fogalma szubjektív; ha bizonytalan vagy, nézd a régebbi galériákat, vagy kérdezz.

Elfogadott megoldások: 17 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-12-11 16:00:00.

A kör (9 megoldás)

A feladat egy olyan programot írni, amely egy kört rajzol ki a képernyőre. A programban a felhasználónak mozgatnia kell tudni a kör középpontját az egérrel („fogd és vidd”, rákattint, mozgat, elenged). Ezen felül, ha a körív valamely pontjára kattint és azt húzza el, azzal a sugarát kell tudnia módosítani. Mindeközben az ablak aljára legyenek kiírva a kör középpontjának koordinátái, és a sugara! Ötleteket a Pygame-es írás ad, különösen az első két része.

A kattintásnál ügyelj arra, hogy a távolság meghatározását (középpontra kattintott-e, körívre kattintott-e) egy adott tartományon belüli közelségként kell értelmezni. Az egész szám koordinátákkal rendelkező képpontok amúgy nem lesznek pontosan rajta a görbén, mert az matematikailag nulla vastagságú.

Használj a programban állapotgépet! Jegyezd meg egyetlen állapotváltozóban az egérmozdulatok kezeléséhez, hogy mit csinált épp a felhasználó: nem kattintott, vagy a középpontra kattintott, esetleg a körívre! Figyelj arra, hogy ne terheld fölöslegesen a gépet; a képet csak akkor kell újrarajzolni, ha az változott.

Tiltott szavak: pygame.font.Font

Elfogadott megoldások: 9 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-12-11 16:00:00.

Szekszárdon születtem, színésznőt szerettem (17 megoldás)

A feladat megszámolni az „sz” betűvel kezdődő szavakat (lásd a feladat címét), fájl vége jelig a szabványos bemeneten, és kiírni a számukat. Szó karakterének tekintjük az ábécé összes kis- és nagybetűjét, szóhatárolónak minden mást. A szavak között tetszőlegesen sok szóhatároló lehet.

Tervezz állapotgépet állapottáblával, és írj programot, amely megvalósítja azt! Az állapottáblát írd be kommentben a program tetejére. Nem kell szépnek lennie, csak legyen érthető.

Elfogadott megoldások: 17 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-12-11 16:00:00.

Síkidom területe (6 megoldás)

Ehhez a feladathoz előzetesen elérhető a 14. heti előadásanyag.

Adottak az alábbi síkidomok: egy parabola, egy kör, és egy szinuszfüggvény alatti terület:

síkidomok

Feladat: írj egy olyan programot, amely Monte Carlo-módszerrel meghatározza a három síkidom metszetének területét! Ehhez véletlenszerűen kell pontokat generálnia egy téglalapon belül, és azt vizsgálnia, a pontok mekkora hányada esik a meghatározott területre.

A program tartalmazzon egy olyan függvényt, amely nem csak ezt a problémát tudja megoldani, hanem tetszőleges számú síkidom megadható neki oly módon, hogy függvények listáját veszi át, illetve egy befoglaló téglalapot, amelyen belül vizsgálnia kell a pontokat. Az egyes függvények paraméterei ehhez x, y koordináták kell legyenek, visszatérési értékük egy logikai érték: hogy a síkidom területére esik-e a pont, vagy nem.

Elfogadott megoldások: 6 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-12-11 16:00:00.

Bankautomata 💰 (3 megoldás)

Ehhez a feladathoz előzetesen elérhető a 14. heti előadásanyag.

Egy bankautomatában a használható címletek (1000, 2000, 5000, 10000, 20000) ismeretében adjuk meg, egy adott pénzösszeget hogyan lehet legegyszerűbben, legkevesebb bankjeggyel kifizetni. A megoldást egy mohó algoritmus adhatja, amely a legnagyobb címletektől halad a kisebb felé – ezért lesz a legkevesebb bankjegy az eredmény.

A mohó algoritmus viszont könnyen rossz megoldást adhat akkor, ha figyelembe kell vennünk, hogy melyik bankjegyből mennyi áll rendelkezésünkre. Márpedig a bankautomata rekeszei végesek, nem lehet bennük végtelen pénz. Ha ez a helyzet:

címlet      készlet
5000        87
2000        35
1000        1

Akkor ha az első ügyfél 6000 forintot kér, 5000 + 1000-et fog kapni; de ezzel az ezres kifogy, és a második ügyfél már 3×2000 forintot kell kapjon, ha ő is 6000-et vesz ki, mint az előző. Ha pedig a rekeszek tartalma ez:

címlet      készlet
10000       87
2000        35

Akkor hiába próbálna valaki 5000 forintot felvenni, nem tud. Ugyan jóval több pénz van az automatában, de csak azokat az ügyfeleket tudja kiszolgálni, akik páros 1000 forintokat kérnek.

Írj visszalépő keresést használó programot, amely

  • Eltárolja a címleteket és a rendelkezésre álló darabszámot.
  • Folyamatosan összegeket kér a felhasználótól, amíg üres sort nem kap.
  • Mindig kiírja, hogyan lehet a legegyszerűbben kiadni az adott összeget, figyelembe véve a készletet.
  • Debug céllal jelzi azt is, hogy a készlet hogyan alakul a pénz kiadása után.

Javasolt ehhez egy olyan függvényt írni, amelyik az első paraméterében látható listában kapja a készletet, és a második paraméterében kapott listába írja az eredményt.

Ne felejtsd el a dolgokat, amiket eddig a félévben tanultál! Globális változók, mágikus konstansok, rossz adatmodell, teszteletlen program beadása, ... Ezek mind visszautasításhoz vezetnek.

Elfogadott megoldások: 3 darab.
Szerezhető: 1 pont. Leadási határidő: 2020-12-11 16:00:00.