Nagy házi feladat

A Szoftver labor I. tárgyban kötelező egy nagy házi feladat megoldása. A feladat szabadon választott. Lehet a lenti listából is választani, vagy azokhoz hasonló nehézségű, az elvárásoknak megfelelő saját problémák is megoldhatóak. (Egyetlen kivétel a plágiumkereső – azt nem szabad választani, mert az a minta házi.) A választást mindenképpen jóvá kell hagyja a laborvezető.

1 Követelmények

A nagy házi feladat a következő követelményeknek kell megfeleljen:

A nagy házi feladat leadásáról

Az elektronikusan leadott anyagok

A nagy házi feladathoz a megoldás forrásfájljait (*.c, *.h) és dokumentációját (*.pdf vagy *.html) kell feltölteni egy ZIP fájlban. A csomag egyéb, különösen a fordítással automatikusan előállítható fájlokat (*.obj, *.exe stb.) nem tartalmazhat.

A dokumentáció javasolt formátuma a szabványos PDF formátum. Word dokumentum nem megengedett. A javasolt PDF készítő letölthető innen: CutePDF. Telepítés után megjelenik egy fiktív nyomtató; arra nyomtatva készül a PDF fájl.

A feltöltött csomag maximális mérete fél megabájt, forráskóddal és dokumentációval együtt. Ebbe a feltöltött házinak bele kell férnie: fél megabájt szöveg egy 4-500 oldalas könyvnek felel meg! Ha mégsem lenne így, javasoljuk a dokumentációt egy fájlban leadni, továbbá abból a felesleges képeket, különösen a screenshotokat törölni. A program tesztelése nem azt jelenti, hogy az elindított programról screenshotok készültek – az ilyen képeknek az információtartalma nulla.

A plágiumról

A nagy házit minden esetben egyedül kell elkészíteni. A csoportmunka egy későbbi tárgy tananyaga. Ezen felül a plágiumot a TVSZ bünteti. A plágiumot elkövető hallgatók ellen hivatalból fegyelmi eljárást kell indítani.

A tárgyban plágiumnak minősül más szellemi termékének minden forrásmegjelölés nélküli felhasználása. Ide értjük többek között más házijának (módosított) beadását, a házi feladat megoldások ajándékozását és vásárlását, az Internetről letöltést is. Ez független attól, hogy a házi feladatként beadott anyag milyen úton és formában jutott el az eredeti tulajdonostól a beadóhoz. Kivételt képeznek a tárgyak honlapjáról letölthető kódrészletek (előadás fóliák, gyakorlati/labor anyagok megoldásai), továbbá a tárgy oktatóinak tanácsai, iránymutatásai.

A plagizált programokat évfolyam szinten, gépesítve keressük egy, a minta nagyháziban bemutatott plágiumkeresőhöz hasonló szoftverrel. Ez a szoftver forráskódok összehasonlítására van kihegyezve, és képes megtalálni azokat a programokat is, amelyek formázásban, változónevekben, sztringekben stb. különböznek egymásból. A kiléte nem titok, erről a címről: SIM letölthető. Az írójához hasonlóan úgy hisszük, hogy aki képes módosítani más szellemi termékét olyan szinten, hogy az átmenjen a plágiumteszten, akár meg is érdemelheti a jegyet a házijára. A szoftver által kiadott eredményeket minden esetben kézzel ellenőrizzük; attól senkinek nem kell tartania, hogy a program hibájából fog megbukni.

A tipikus
plágium
lepes=0;
while(megtalalt<parok)
{
    printf("\n\nLepesek szama: %d\n", lepes);
    printf("\n\nMelyik legyen az elso kartya? \nSor: ");
    scanf("%d", &m);
    printf("Oszlop: ");
    scanf("%d", &sz);
    while (m<1 || m>height || sz<1 || sz>width || keptabla[m-1][sz-1]==' ')
    {
        tablarajzolas();
        printf("\n\nLepesek szama: %d\n", lepes);
        printf("\n\nMelyik legyen az elso kartya? \nSor: ");
        scanf("%d", &m);
        printf("Oszlop: ");
        scanf("%d", &sz);
    }
    keptabla[m-1][sz-1]=tabla[m-1][sz-1];

    tablarajzolas();

    printf("\n\nLepesek szama: %d\n", lepes);

2 Segédlet – grafikus, szöveges képernyő és memóriakezelés

A házi feladatnak nem követelménye a grafikus megjelenítés. Aki összetettebb konzolos felületet szeretne csinálni (pl. aknakereső, tetris), használhatja az econio-t, amely a konzol képernyő kezelését segítő függvényeket tartalmaz (színek beállítása, adott pozícióra ugrás stb.) Ez egyszerűbb játékokhoz, teljes képernyőn futó programokhoz jól használható Windows alatt.

Gond szokott lenni Windowson a szöveges képernyőn az ékezetes karakterek megjelenítésével is. Ez azért van, mivel a Windows más karakterkódolást (betű→szám hozzárendelést) használ a grafikus és a konzolos programoknál. A probléma egy-két függvényhívással megoldható; erről bővebben a karakterkódolások oldalon olvashatsz.

A grafikus programokhoz pl. a platformfüggetlen SDL használható. A grafikus megjelenítés ebben a tárgyban nem tananyag, de önszorgalomból bárki készíthet grafikus programot is. Ezzel a házi feladat egyéb követelményeit (terjedelem, dinamikus memória, fájlkezelés stb.) nem lehet kiváltani.

A nagyházi memóriakezelési hibáinak felderítésére a Debugmalloc modult javasoljuk. Ezt csak hozzá kell linkelni a projekthez, és a szabványos hibakimenetre vagy fájlba írva jelzi a felszabadítatlan területeket, a túlindexeléseket és hasonlókat. De azért ez sem mindenható, csodákra nem képes!

3 Matematikai jellegű programok

Életjáték

Készíts menüvezérelt C programot, mely a Conway féle LIFE (életjáték) modellt valósítja meg. Részletek a http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life címen. A program legyen képes:

Egész aritmetika

Készíts függvénykönyvtárat, amely nem korlátozott ábrázolási tartományú egész aritmetikát valósít meg – vagyis képes tetszőlegesen nagy, akár 1000 számjegyű egész számokkal is számolni. A program legyen képes a négy alapművelet elvégzésére – amelyekkel alkotott kifejezéseket a billentyűzetről vagy fájlból vár. (Ezek lehetnek fordított lengyel jelöléssel adottak is.)

Numerikus integráló

Készíts C programot, mely a felhasználó által megadott függvényt numerikusan integrálja. Gondosan tervezd meg az adatstruktúrát! Tervezz egy megfelelő bemeneti nyelvet. A program legyen képes:

A program legyen képes felhasználó által megadott kifejezéseket eltárolni és feldolgozni! (Ezek lehetnek fordított lengyel jelöléssel adottak is.)

Mátrix függvénykönyvtár

Készíts függvénykönyvtárat, amellyel mátrixműveletek végezhetőek! Tárold egy mátrix szélességét, magasságát, valós értékeit! Legyen képes a programod bármilyen nagy mátrixokkal dolgozni, és a szokásos műveletek elvégzésén kívül a mátrixokat fájlba írni és fájlból visszaolvasni!

4 Játékok

Amőba

Készíts menüvezérelt C programot, mely amőbát játszik. A program legyen képes:

Reversi

Írj reversi játékot, amelyben a gép ellen lehet játszani! A program legyen képes:

(Vigyázat, ennél is kötelező dinamikus memóriakezelést használni, bár az amőbával ellentétben ezt fix méretű pályán szokták játszani. Konzultálj a laborvezetővel!)

Sokoban

A játékban egy figurával ládákat kell tologatni a képernyőn; úgy, hogy azok a megfelelő helyre kerüljenek. A pálya viszont olyan, hogy könnyű betolni olyan helyre a ládákat, ahonnan már elmozdítani nem lehet őket.

Olvasd a pályák leírását fájlból! Vezess dicsőséglistát! (Melyik játékos, melyik pályát, hány lépésből tudta megoldani?) Ez könnyedén megoldható szöveges képernyőn is.

Hexxagon

Táblás játék. A pálya hatszögletű elemekből áll. Mindkét fél néhány bábuval indul. Minden lépésben a játékosok valamely bábuval a szomszédos helyre terjeszkedhetnek (ilyenkor nő a bábuk száma), vagy kettővel arrébb ugorhatnak (ilyenkor nem) egy szabadon választott bábujukkal. Az újonnan lerakott bábu mellett az ellenség bábui színt váltanak; a lépő játékos megnyeri azokat. YouTube videó itt: http://www.youtube.com/watch?v=_E10ydLaLE8.

Írj programot, amelyben a gép különféle stratégiákkal játszik a felhasználó ellen!

Töltés-játék

(Grafikus program.) A játék a következő. A program a képernyő adott pontjából, adott irányban kilő egy pozitív töltéssel rendelkező részecskét. A játékos számára adott néhány másik töltés, amelyeket úgy kell elhelyeznie a képernyőn, hogy a mozgó töltés egy megadott célba jusson. Ezek az elhelyezendő töltések lehetnek különböző erősségűek, polaritásúak stb. Közben a pályán lehetnek fix töltések, falak stb. (Hasonló játék itt: http://kmk.blog.hu/2007/07/26/newton_kedvenc_jateka)

A program számoljon pontszámot a játékos számára (pl. hány próbálkozásra sikerült megoldania a pályákat), és ez alapján tartson nyilván dicsőséglistát is, amelyet fájlba ment és vissza is olvas! A programnak tetszőlegesen sok töltést kell tudni kezelnie. A pályák leírását (hol van töltés, hol van fal) olvasd fájlból! Egy pályán lehessen tetszőlegesen sok mind a kettőből!

Atomix

A játékban egy zegzugos pályán kell kirakni az elszórt atomokból egy molekulát. A játékos egy kattintással (vagy egy gomb megnyomásával) megfoghatja az atomokat, utána pedig egy irány megadásával (fel, le, jobbra vagy balra) elindíthatja azokat. A nehézség abban áll, hogy ilyenkor az atomok nem egyet ugranak arrébb, hanem addig mennek, amíg falba vagy egy másik atomba nem ütköznek.

A játékban a pálya lehessen tetszőlegesen nagy! Pályák letölthetőek innen: atomix.zip. Leírás megtalálható a ZIP-ben. Az original.json fájl viszonylag egyszerű pályákat tartalmaz.

Kalandjáték

Készíts szöveges kalandjáték programot, amely

Kígyó játék

Készíts kígyó játékot, ahol a kígyók ha megeszik a véletlenszerűen elhelyezett étket, akkor nő a méretük. Ha önmaguknak, vagy egymásnak ütköznek, az a játék végét jelenti. A program legyen képes:

Aknakereső játék

Készíts aknakereső játékot. A pálya téglalap alakú, cellákból álló tábla. Egy cellára rálépve megtudhatjuk, hogy az adott cellán van-e akna (ebben az esetben felrobbanunk – vége a játéknak), illetve, hogy hány szomszédos cellán van. Legyen lehetőség:

További játékok

Készíts egyszerű, alfanumerikus képernyőn futó játékprogramot (PacMan, Tetris, stb.) A program legyen képes:

Akasztófa

Az akasztófás és a szótáras programokhoz használható szólisták: szotar.zip.

A program a szavak listájából gondol egy feladványt, amelyet a felhasználónak ki kell találnia. Betűket tippel, amelyek ha a gondolt szóban szerepelnek, a gép felfedi őket. Pl. ha a gondolt szó ökör, a tippek k és r, akkor a felhasználó ezt látja: _k_r. A program legyen képes:

A szavak tömbben történő tárolása ennél a feladatnál nem elfogadható!

Gonosz akasztófa

Az alapfelállás a fentihez hasonló, de itt a gép nem kötelezi el magát egyetlen egy szó mellett sem. A felhasználó tippjei alapján mindig úgy szűkíti a szóba jöhető szavak halmazát, hogy a legkevesebb segítséget adjon a felhasználónak. Pl. a felhasználó idáig eljutott: _k_r, és az „akár” szóra gondol. Ezért tippel egy a-t, mire a gép azt mondja, hogy veszített, mert a szó az „ökör” volt. Miközben igazából eddig nem is gondolt egyetlen szóra sem.

KRESZ-teszt

Készíts programot, amellyel a KRESZ vizsgára lehet gyakorolni! A programnak fájlból kell beolvasnia a kérdéseket, amelyekre természetesen a helyes választ is tudja. A felhasználónak ezt kell megmondania. Vagy passzolnia, de akkor a kérdések végére érve újra meg fogja kapni a kihagyott kérdést. Vegye figyelembe a program az időt is! (Csinálhatod úgy, hogy egy kérdésen akármennyi ideig lehet gondolkodni, de a válasz után nézi a program, hogy mennyi idő telt el a játék indítása óta.)

Készíts dicsőséglistát és szégyenpadot: dicsőséglistára azok kerülnek, akik nagyon gyorsan válaszoltak a kérdésekre, szégyenpadra azok, akik a legtöbb rossz választ adták.

(A kérdések adatbázisa e-mailben elkérhető.)

Legyen Ön Is Milliomos!

A kérdések adatbázisa: loim.zip. Ebben egy Excel tábla van, amiből tetszőleges kódolással szövegfájlt tudsz készíteni.

Mint a tévés játék: egymás utáni kérdések, mindegyikre egy jó és három rossz válasz. Rossz válasz esetén rögtön kiesik a játékos; lehet kérni a gép segítségét (elvesz két rossz választ) és a közönség segítségét (szavaznak).

A program tartalmazzon dicsőséglistát a játékosokról: ki mennyi pénzt nyert, és mennyi ideig (perc) volt játékban.

A programnak fájlból kell beolvasnia a kérdéseket, amelyekből tetszőlegesen sok lehet! (A kérdések adatbázisa e-mailben elkérhető.)

5 „Számítástechnika, algoritmusok” feladatok

Huffman kódoló

Készíts parancssorból hívható C programot, amely a Huffman kódoló algoritmust felhasználva tömörít fájlokat. Részleteket lásd a http://en.wikipedia.org/wiki/Huffman_code címen. Tervezz megfelelő fájl formátumot a tömörítés kódtáblázatának tárolására. A program legyen képes:

Lempel-Ziv tömörítő

Lempel és Ziv algoritmusa a következő ötlettel tömöríti a fájlokat. Tegyük fel, hogy adott egy fájl a következő tartalommal:

Blah blah blah

Ebben a színnel jelölt részek egyformák, ezért a második előfordulást egy hivatkozással lehet helyettesíteni:

Blah b[D=5,L=5]lah

Ez azt jelenti, hogy D=5 bájtnyival ezelőtt volt egy L=5 hosszúságú sorozat, amit az adott helyen meg kell ismételni. (Most hosszabbnak tűnik, de binárisan tárolva ezt, rövidebb lesz.)

Írj programot, amely ilyen módszerrel képes tömöríteni és kicsomagolni fájlokat! Teszteld a programodat szövegfájlokon és képeken is (pl. BMP. A .png és .jpg fájlok már tömörítve vannak, azokat hiába próbálod tovább préselni.) Az algoritmusról sok írást találsz a neten.

Archív fájl függvénykönyvtár

Készíts függvénykönyvtárat, amellyel egy archív fájlba becsomagolt fájlok nyithatók meg C programból! A függvénykönyvtár használata hasonlítson minél jobban az stdio.h fájlkezelésére!

A fájlok becsomagolását egy parancssori segédprogrammal lehessen végezni:

pack archiv.dat file1.bmp file2.dat file3.doc

Ekkor keletkezzen egy archiv.dat nevű fájl. Abból programból a file2.dat megnyitása:

ARCHIV_FILE *fp;
char tomb[1024];

fp = archiv_fopen("archiv.dat", "file2.dat", "rb");
archiv_fread(tomb, 1, 1024, fp);

A fájlokat tömöríteni nem kell.

Pascalból C-be

Készíts parancssorból hívható C programot, amely egyszeru standard Pascal programokat fordít C nyelvre. A program legyen képes az alábbi Pascal fordulatok kezelésére:

Útvonaltervező

Készíts útvonaltervező programot!

A program legyen képes egy térkép szöveges reprezentációját fájlból beolvasni és az ebből felépített adatstruktúra alapján két megadott helyszín között útvonalat tervezni. Lehessen megadni az útvonaltervezés szempontját is (leggyorsabb, legrövidebb, stb)!

Buszjáratok

Készíts programot, amely egy közlekedési társaság buszjáratait képes nyilvántartani, és a menetrendek alapján útvonalakat felépíteni! Elvárások a programmal szemben:

6 Nyilvántartás jellegű programok

Tömbös megoldások ezeknél nem elfogadhatóak!

Telefonkönyv

Készíts menüvezérelt C programot, amely „rekordokban” tárolja bizonyos személyek nevét, foglalkozását, telefonszámát, esetleg más jellemző adatait. A program legyen alkalmas:

Határidő napló

Készíts határidő napló programot, amely „rekordokban” tárolja az események dátumát, pontos idejét, helyét, elnevezését, és egy hozzá kapcsolódó megjegyezést. Használj dinamikus adatszerkezetet. A program legyen képes:

Oktatók hallgatói véleményezése

Készíts programot, amely OHV kérdőíveket és azokra adott válaszokat tárol! A kérdőívek tetszőlegesen sok kérdést tartalmazhatnak, amelyekre tetszőlegesen sok válasz lehet. Ezen felül tartalmaznak egy szöveges mezőt, ahova a kitöltő bármit írhat.

Készítsen a program statisztikát a kitöltött kérdőívek alapján! Legyen képes a kérdőívek és az eredmények fájlba mentésére, illetve visszatöltésére!

Prog1 nyilvántartás

Készíts programot, amely képes hallgatók adatait nyilvántartani, és Prog1 eredményeiket számolni! A megjegyzendő adatok a következők:

„Tanítsd meg” a programnak a tárgykövetelményeket! Legyen képes a program listát készíteni azokról, akinek van megajánlott jegyük, akiknek P2ZH-t kell írniuk (nem sikerült sem a NZH-juk, sem a PZH-juk), legyen képes elővizsga rangsort készíteni (akiknek nincs megajánlott jegyük, de sok pontjuk van), és ehhez hasonló listákat kiírni a képernyőre!

Szoftlab1 nyilvántartás

Ugyanaz, mint a fenti, csak a Szoftlab1 tárgyhoz. Itt NZH eredményeket nem, hanem a nagy házik jegyeit kell nyilvántartani, és abból félév végi jegyet meghatározni.

Könyvtár

Készíts könyvtár-programot, amely képes könyvek adatait eltárolni „rekordokban”. A program legyen képes:

Szótár

Készíts szótár programot. A program adjon lehetőséget:

Étterem

Készíts programot, amely egy étteremben az egyes asztalokhoz tartozó megrendeléseket jegyzi meg. Legyen lehetőség:

Az asztalfoglalásokat és a menüt mentse a program fájlba is, hiszen azokat nem felejtheti el egy újraindítás vagy egy áramszünet miatt!

Mini-Facebook

Írj programot, amely emberek személyes adatait (név, nem, születési dátum stb.), továbbá ismeretségi viszonyait (kik ismerik egymást) képes nyilvántartani, és lehetővé teszi azt, hogy két ismerős üzenni tudjon egymásnak!

A programnak nem kell grafikusnak, se hálózatosnak lennie; elég, ha egyszerre egy ember tudja használni. (Utána ő kijelentkezik, és valaki más bejelentkezik.) Tegyen lehetővé ugyanakkor kereséseket (név szerint, iskola szerint, lakóhely szerint stb.), és ajánlja fel egy menüpontban a felhasználók számára az ismerősök ismerőseit! Tároljon el minden adatot fájlban (az üzeneteket is), és tegye lehetővé akárhány felhasználó és üzenet létezését!

Morze

Készíts parancssorból hívható C programot, amely Morze szövegeket kezel. Morze ábécét találsz pl. a http://www.soton.ac.uk/~scp93ch/morse/ címen. A program tudjon:

Tömbös, listás megoldás nem elfogadható!