A KöMaL 2009. januári informatika feladatai
Kérjük, ha még nem tetted meg, olvasd el a versenykiírást.
Feladat típusok elrejtése/megmutatása:
I-jelű feladatokA beküldési határidő 2009. február 16-án LEJÁRT. |
I. 202. Adott néhány kupac kavics. Minden lépésben az összes kupacból elveszünk egy kavicsot és ezekből egy új kupacot képzünk. A kupacok sorrendje nem számít.
Például:
A lépéseket addig ismételgetjük, amíg meg nem unjuk. Mivel véges a kavicsok száma, így előbb-utóbb a kavicsok eloszlása a kupacokban ciklikussá válik.
Írjunk programot, amely a bemeneti adatállományban megadott kupacok kavicsszáma alapján megadja, hogy hányadik lépésben kezdődik az ismétlődés és mi a ciklus hossza. Az összes kavics száma nem lehet több mint 50.
A program parancssori argumentuma legyen a kupacokat leíró adatállomány neve. A fájl első sorában egy egész szám áll, amely a kupacok N számát (1N25) adja meg. Az ezt követő N db sor mindegyikében egy érték szerepel, amely a kupacok kavicsszámát adja meg.
A program kimenete a képernyőre két pozitív egész szám, amely közül az első azt adja meg, hogy hányadik lépésben kezdődik egy új ciklus és a másik, hogy egy ciklus hány lépésből áll.
Beküldendő a program forráskódja (i202.pas, i202.cpp, ...), valamint a program rövid dokumentációja (i202.txt, i202.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
I. 203. Azt mondják, ha egy majmot leültetnek a számítógép klaviatúrája elé, és hagyják szabadon gépelni - pontosabban ütögetni a billentyűzetet - akkor előbb-utóbb leír minden értelmes szót, sőt le fogja gépelni Shakespeare minden művét is. Legépeli, azaz egymást követő billentyűleütések eredményeként megjelenik az értelmes szó, vagy éppen a mű szövege. Mindez csupán idő kérdése. Az alábbi kísérlettel vizsgálhatjuk, hogy a - legfeljebb 3 karakter hosszú - megadott szöveget legépelik-e a majmok.
A kísérlet leírása: Vegyünk egy majmot és egy számítógépet. Alakítsuk át a billentyűzetet oly módon, hogy csak az angol ábécé nagybetűit lehessen begépelni. Válasszunk egy karaktersorozatot. (Például: TE.)
Minden számítógépnél várjunk 50 000 billentyűleütést, majd határozzuk meg, melyik leütésnél alakult ki először a választott karaktersorozat. (Ha a majom a GJFTESFFX karaktersorozatot gépelte be, akkor a TE szó ezen megfigyelés során az 5. leütést követően jelent meg először.)
Az így kapott értéket jegyezzük fel. (Ha nem fordult volna elő a megadott karaktersorozat, akkor jegyezzük fel a 60 000 értéket.)
A feladat: Táblázatkezelő programban készítsünk megfelelő modellt a kísérlethez. A modell megalkotásakor feltételezhető, hogy minden billentyűt ugyanakkora valószínűséggel ütnek le a majmok. Vizsgáljuk a modell segítségével a FA, BOT, ORR szavakat és majom számára minden bizonnyal értelmetlen XP, PDF, PPT és MMM karaktersorozatot. (A megoldásnak alkalmasnak kell lennie más hosszúságú szövegek vizsgálatára is.) A ,,kísérletek'' eredményét az alábbi mintának megfelelően előállított mérés munkalap celláiba jegyezzük be. (Ezek a számok az egyes kísérletek kimenetének kézzel rögzített értékei.) Ezen a lapon más nem szerepelhet.
A táblázatban szereplő számadatok fiktív értékek. A majom munkalapon tároljuk tetszőleges módon és formában a majom által bevitt karaktereket. (Praktikus a feldolgozást segítő formát választani.) A segéd munkalapon - ha szükséges - tetszőleges segédszámítások végezhetők. (A feladat megoldható segédcellák alkalmazása nélkül is.) Végezzünk minél több kísérletet.
Beküldendő az i203.xls vagy i203.ods állomány tömörítve az i203.zip állományban, valamint egy szövegfájl (i203.txt, i203.pdf), amelyben írjuk le, hogy melyik program melyik verziójával készült. A szövegfájlban fogalmazzuk meg, van-e arra vonatkozó sejtés, hogy vajon az XYZ, XYX, XXY és XXX szerkezetű karaktersorozatok közül melyiknek a felbukkanása várható legelőször és legkésőbb.
(10 pont)
I. 204. Múlt havi számunkban, az I. 201. feladatban szerepelt a Cardano-féle rács, amely szövegek titkosítására alkalmas. Készítsünk programot, amely egy megadott rács segítségével titkosít egy megadott szöveget, azaz létrehozza a szöveg betűinek rács által mutatott elrendezését.
A program a rács elrendezését a parancssor első argumentumaként megadott szöveges fájlból olvassa. A fájl egy N×N-es rács esetén N sort tartalmaz, és minden sorában a rács kezdő állása mellett azokban a cellákban, amely alatt látni lehet a betűket egy kis ,,o'' betű található, a többi helyen egy ,,.'' pont. A program a még titkosítatlan szöveget a parancssor második argumentumaként megadott szöveges állományból olvassa. A fájl a magyar ABC kis- és nagybetűi mellett szóközöket, valamint a szokásos írásjeleket tartalmazza, és egy vagy több sorból áll. A program kimenete a parancssor harmadik argumentumaként megadott szöveges állomány, amely N×N-es betűnégyzeteket tartalmaz, melyek egymástól egy-egy üres sorral vannak elválasztva.
A titkosítás a szöveg elejétől kezdődik, és egymás után hozza létre az N×N-es betűnégyzeteket. A betűnégyzetek csak az eredeti szöveg betűit tartalmazzák (mindegyiket nagybetűssé alakítva), a szóközöket, újsor karaktereket és az egyéb írásjeleket nem. A titkosítás könnyen megfejthető, ha a szöveg karaktereinek elfogyása esetén az utolsó betűnégyzet nem teljes, csak bizonyos részein tartalmaz betűket. Ennek elkerüléséhez az utolsó betűnégyzetet úgy kell elkészíteni, hogy a szöveg végéhez hozzáillesztünk a szöveg elejétől annyi betűt, hogy a négyzet teljes legyen.
Példa:
Beküldendő a program forráskódja (i204.pas, i204.cpp, ...), valamint a program rövid dokumentációja (i204.txt, i204.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
S-jelű feladatokA beküldési határidő 2009. február 16-án LEJÁRT. |
S. 41. A 2008 májusában megjelent I. 188. feladatban, az L-System módszerként ismert, vonalas fraktálokat rajzoltunk vektorgrafikus rajzoló programmal. Készítsünk programot, amellyel az egyszerűsített L-System rendszert valósítjuk meg.
A következő axióma és szabály elemeket ismerje a rendszerünk:
A program kérje be az axiómát, a szabályt (csak a megadott szimbólumokat tartalmazzák), a szintet, amely a helyettesítések számát jelenti, a lépéshosszt és a fordulások szögét.
A program a bemeneti adatokat a programozási környezettől függően karakteres vagy grafikus felületen kérje be. A bevitt adatok ellenőrzése nem szükséges, mert feltételezzük, hogy a felhasználó csak helyes adatot ad meg.
Példa:
Beküldendő a program forráskódja (s41.pas, s41.cpp, ...), valamint a program rövid dokumentációja (s41.txt, s41.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható.
(10 pont)
Figyelem!
Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.