Szorgalmi feladatok

Ezek a feladatok kiegészítő feladatok, különböző nehézségűek. Mindenki önmaga szórakoztatására, gyakorlásként oldhatja meg őket, vannak könnyűek, vannak gondolkoztató feladatok és van egy-kettő, aminek a teljeskörű igényes megoldása bőven túlmutat a tananyagon.

Beküldeni nem lehet, pont nem jár érte, semmi másról nem szól, csak a gyakorlásról. Próbáljuk idő szerint csoportosítani, ahogy a félév előrehalad.

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áljon.) 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.

Használd az első előadáson megismert vezérlési szerkezeteket!

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

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

„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ó: (ha már ismered a függvényeket, akkor se használd kérlek ebben a feladatban)

• 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!

Ha tetszett a Caesar kódolás (laboron volt), itt olvashatsz egy nehezebben visszafejthető titkosításról, az ún. Vigenère-rejtjelről

A feladat a kézi kódoláshoz és dekódoláshoz szükséges táblázat előállítása. A program kérjen egy jelszót, majd a jelszóhoz állítsa elő a táblázatot a megadott minta alapján, fejléccel, vízszintes és függőleges vonalakkal, de nehezítésként úgy, hogy

1. csak egy ciklus használható, és a ciklus magja egy print() hívás lehet, más nem!
2. a szövegkonstansok hossza nem haladhatja meg a 26-ot
3. sehol nem szerepelhet benne számkonstans, pl. 26

A beadott jelszó legyen a "PELDA", az elvárt kimenet pedig:

 |ABCDEFGHIJKLMNOPQRSTUVWXYZ
-+--------------------------
P|PQRSTUVWXYZABCDEFGHIJKLMNO
E|EFGHIJKLMNOPQRSTUVWXYZABCD
L|LMNOPQRSTUVWXYZABCDEFGHIJK
D|DEFGHIJKLMNOPQRSTUVWXYZABC
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ

Csak az angol ABC nagybetűivel kell foglalkozni, ékezetekkel nem.

Írd meg a titkosítást és a visszafejtést végző függvényeket is!

Laboron szerepelt a kő-papír-olló játék. Ebben a játékban úgy gondolhatjuk, mindenkinek egyforma esélye van, mert véletlenszerűen választunk és ha lejátszunk sok fordulót, akkor körülbelül a győzelmek száma egyenletesen oszlik majd meg a két játékos között.

Ez egy számítógép esetében, ha a véletlenszám generátor jó, ez nagy valószínűséggel igaz. Egy ember azonban (ez jól megfigyelhető gyerekeknél) nem fog egyenletes valószínűséggel választani, általában függeni fog a mutatott szimbólum attól, hogy az előző menetben, nyert vagy kikapott-e és mit választott akkor. Pl. ha az előző menetben kikapott papír választásával, nagyobb valószínűséggel fog ollót mutatni a következő játékban, mint újra papírt.

írjál programot, ami az ember ellen játszik, statisztikai alapon!

A játékokból készíts statisztikát! Tartsad nyilván azt, hogy ha az emberi játékos egy adott szimbólummal nyert illetve veszített, a következő játékban mit mutatott. Pl. ha ollóval veszített, legközelebb 11x választott követ, hatszor ollót és csak kétszer papírt.

Így a játékban, ha a gép "tudja", hogy az előző menetet az ember ollóval veszítette el, akkor nagyobb eséllyel követ fog legközelebb mutatni, ezért papírt választ.

Ebben a feladatban az adatszerkezet kitalálása egy picit nehezebb.

Tipp

A kő, papír, olló szövegek helyett használj egész számokat. Hogy érthető legyen a kód, ezeket tedd a program elején konstanssá, pl.

KO = 0
PAPIR = 1
OLLO = 2

Így a statisztikát listákból tudod építeni, amit könnyű lesz egész számmal indexelni.

Mivel már volt előadáson, ebben a feladatban kötelező a függvények használata!

Jobb megoldás

Persze a gépet hamar összezavarhatjuk, ha tudjuk, mit játszik. Pl. ha semmi mást nem csinálunk, mint kő, papír, olló sorrendben játszunk, bármi is történik, egy idő után semmit nem ér a statisztika és csak a véletlen dönt. Jobb megoldás az, ha sorozatokat keresünk az ember játékában és arra alapozva tippelünk.

Időnként előfordul, amikor két ember beszélget, hogy:

• "örülök" erre a másik:
• "örülök, hogy örülsz"

ezt persze folytathatjuk tovább is:

"örülök, hogy örülsz, hogy örülök, hogy örülsz, hogy örülök"

Írj rekurzív függvényt, ami paraméterként megkapja az "örülések" számát és kiírja a mondatot. Az előző mondat az öthöz tartozó eredmény.

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!

É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).

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 méretű! A területek ne csak kitöltve legyenek, hanem körberajzolva is. Jelöld be a BME-t a térképen!

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

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.

++++++++[>++++++++<-]>++.++++. – 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. 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. Itt a kód:

programkod = "[ThisprogramprintsSierpinskitriangleon80-columndisplay.]>++++[<++++++++>-]>++++++++[>++++<-]>>++>>>+>>>+<<<<<<<<<<[-[->+<]>[-<+>>>.<<]>>>[[->++++++++[>++++<-]>.<<[->+<]+>[->++++++++++<<+>]>.[-]>]]+<<<[-[->+<]+>[-<+>>>-[->+<]++>[-<->]<<<]<<<<]++++++++++.+++.[-]<]+++++*****Made*By:*NYYRIKKI*2002*****"

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

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

5. Ellenőrizd 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).

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!

Írj a Pont osztályhoz kivonó és abszolút érték 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).

Definiálj típust, amelyben egy időpontot tudsz tárolni, külön óra (0...23), perc (0...59) és másodperc (0...59) értékekkel! Valósíts meg minden értelmes műveletet operátor formájában! Minden függvényt dokumentálj docstring-gel és minden művelethez írj tesztet assert segítségével, ahogy az előadáson láttad. Teszteseteket pl. az Excel segítségével tudsz generálni. Pl. két időpont különbségére:

13:48:11-11:22:33=2:25:38

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.

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.

A Linux du nevű programja egy adott mappa összes fájljának méretét adja – vagyis annak a helyfoglalását. Természetesen ebbe beleszámít az abból nyíló további mappák tartalma is rekurzívan.

Windows esetén alapesetben ilyen program nincs, de a SysInternals-tól letölthető. https://docs.microsoft.com/en-us/sysinternals/downloads/du

Egy adott mappában indítva a program kimenete az alábbihoz hasonló. Az egyes sorok az almappák méreteit mutatják, az utolsó sor pedig a végösszeget.

10458   ./path-converter/src
16334   ./path-converter
273896  ./less.php
66718   ./tfpdf
61875   ./parsedown
4602    ./minify/src/exceptions
81707   ./minify/src
5083    ./minify/data/js
9179    ./minify/data
6659    ./minify/bin
105364  ./minify
32534   ./gettext/src/utils
25129   ./gettext/src/generators
33703   ./gettext/src/extractors
145666  ./gettext/src
173477  ./gettext
701760  .

A feladatod egy olyan rekurzív függvényt írni, amely képes arra, hogy a paraméterként adott nevű mappa méretét, vagyis az abban tárolt összes fájl, és az abból nyíló almappák összes fájljainak méretét meghatározza.

Segédletként lásd a fájlkezelésről szóló írás alját, ahol a mappákról van szó! Az os.walk() függvényt ne használd – a feladat lényege az, hogy te magad megoldd a számlálást.

A laborban szerepelhetett 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.

Í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ő.

Í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!

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

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!

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

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.

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

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

Írj egy függvényt, ami kap egy float-ot és kiírja tizes számrendszerben, majd olyan módon is, ahogy valójában a számítógép ábrázolja, tehát törtrész*2**exponens alakban. Például:

6.022e+23=1.9925126595177332*2**78
6.626e-34=1.7202079492325884*2**-111
-3.14=-1.57*2**1
0.125=1.0*2**-3

A feladat a bitműveletekről szól, ahogy a neve is mutatja, a törtrész és az exponens előállításához bitműveleteket kell használni. (math.frexp, sztring műveletek, vagy definíció szerinti matematikai megoldás bár helyes, nem fogadható el!)

Tehát a kódban <<, >>, & operátorok legyenek leginkább és hexadecimális konstansok.

Ezt a feladatot alacsony szinten kell megoldani. A Python erre is alkalmas. Eltolás, logikai műveletek minden processzor utasításkészletében megtalálhatók.

Tippek

• a megoldás nincs 10 sor, de utána kell nézni sok mindennek és jól végiggondolni, mi a maszk, merre kell eltolni, mennyivel stb.
• szükséged lesz egy olyan 8 byte hosszú egész számra, amelynek bitjei pontosan megegyeznek a függvény paraméterében lévő float-tal. Ezt a struct modul pack/unpack függvényeivel tudod például előállítani.
• ha nem lenne kéznél a Hardver alapok jegyzeted, a Python float valójában a IEEE754 double precision-nek felel meg, aminek a leírása itt található. Ez alapján "bitenként" szétszedheted a 64 bites egész számot részeire, az előadáson mutatott bitműveletek segítségével.
• hexadecimális formában érdemes a maszkoláshoz a konstansokat előállítani.

Magyar kártya paklikat szeretnénk tárolni, a lehető legtömörebben. Számold ki, hogy egy kártya ábrázolásához minimum hány bit szükséges, majd tárold el a teljes 32 lapos paklit úgy, hogy a lehető legjobban használd ki a tárterületet. Ötleteket az Eratoszthenész szitája, spórolósan feladat megoldásából vehetsz. Írd meg az ehhez tartozó kódot, ami generál egy véletlenszerű paklit, majd "összecsomagolja" a lehető legjobban és elmenti binárisan egy fájlba. A teszteléshez írj egy olyan függvényt is, amely kiolvassa a pakli lapjait és szövegesen megjeleníti a képernyőn, általad választott formátumban, pl.

Tök ász
Makk felső
Piros X
stb.

A feladatot bitműveletekkel kell megoldani.

Jobb megoldás

Ha definiáljuk a kártyák sorrendjét, akkor a pakli tulajdonképpen egy permutáció és nem a paklit alkotó lapokat tároljuk, hanem a permutáció sorszámát, 0 és 32!-1 között. Szerencsére a Python esetén az egész számok bitben mért mérete tetszőleges lehet. Ehhez viszont meg kell írni a n. permutációt előállító kódot.

Egy sakk állást úgy tudunk tárolni, hogy eltároljuk az összes figura típusát, színét és pozícióját. Tervezz meg egy szöveges fájlformátumot egy adott állás tárolására! Tervezz egy bináris formátumot is, és használd az előadáson megismert bitműveleteket a tömör tároláshoz!

Ezután fogd erről az oldalról a névnapodon kiadott feladványt (ha pont nincs aznapi, akkor a legközelebb lévőt), valósítsd meg és tárold el mindkét módon.

Hasonlítsd össze a saját formátumaidat a szabványos, json ill. xml alapú szerializációval!

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!

Majd oldd meg ugyanezt reguláris kifejezésekkel, a Python re moduljával! Dolgozz ugyanúgy fájl vége jelig, mint az előbb; a beolvasás közben fűzd össze a szöveget. Vigyázz, ez nem annyira egyszerű, teszteld sokat. A reguláris kifejezés összerakásához ezt vagy hasonló szolgáltatást érdemes használni.

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

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.

A félév során legalább három módszert megismertél amelyek alkalmasak arra, hogy szöveg szavaiból statisztikát készítsünk, azaz melyik szó hányszor szerepel. Ezek a módszerek a következők:

1. bináris fa (előadáson volt, kóddal együtt)
2. hash tábla (Algoritmusok és Gráfok... vödrös hash, csak informatikusoknak! Legyen a tábla mérete 1000 és használd a beépített hash() függvényt!) Ezt meg kell írnod...
3. dictionary

Ehhez negyedikként vegyük hozzá a collections Counter-t.

Fogj egy hosszabb (az egyszerűség kedvéért angol nyelvű és kb. 100 oldanyi) szöveget és készítsd el a szavak statisztikáját mind a négy módszer segítségével. (Addig számold, amíg egyforma eredményt nem kapsz :-) Mérd meg (nézz utána hogyan kell időt mérni!) a végrehajtás idejét és keress rá magyarázatot, hogy miért lesznek az egyes megvalósítások különböző sebességüek.

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.