Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A KöMaL 2012. 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ű feladatok

A beküldési határidő 2012. február 10-én LEJÁRT.


I. 283. A KöMaL két hónappal ezelőtti I. 277. feladatában települések helyét és lakosságszámát a földrajzi koordináták alapján kellett megjeleníteni. Adott ugyanaz a (honlapunkról letölthető) helyforr.dat állomány, amelyben Magyarország településeinek neve (ékezetmentesen), földrajzi koordinátái és lakosainak száma található.

Készítsünk programot i283 néven, amely a képernyőn a felhasználó által megadott koordinátájú terület településeit és azok nevét jeleníti meg adott téglalapban. A településeket ábrázoló pontok töltsék ki a téglalapot a képernyőn, majd annyi településnév jelenjen meg, amely elfér anélkül, hogy a feliratok egymásba érnének. A település nevének elhelyezése csökkenő lélekszám alapján történjen. A neveket lefedő téglalapok bal felső sarka a települések földrajzi koordinátái legyenek. A nevek a településeket ábrázoló pontokat eltakarhatják, de egymást nem. Az a név, amely az előírt sorrend szerint egy másik felíratott kitakarna, vagy az ábrázolt tartományból kinyúlna, az adott felbontás esetén, ne jelenjen meg.

A program a települések földrajzi koordinátáit, a lélekszámot és a település nevét a fenti fájlból olvassa be. A fájl első sora a települések számát (\(\displaystyle n\)), a térkép, azaz az ábrázolás téglalapjának vízszintes (\(\displaystyle dx\)) és függőleges (\(\displaystyle dy\)) méretét (\(\displaystyle 256\le dx,dy\le 1024)\) tartalmazza. Az ezt követő \(\displaystyle n\) darab sorban a települések adatai szerepelnek. A sorok első adata a hosszúsági, a második a szélességi koordinátákat tartalmazza szögperc mértékegységben. A harmadik adat a település lélekszámát adja meg, a negyedik pedig a nevét ékezetmentesen.

Minta:

Beküldendő egy tömörített i283.zip állományban a program forráskódja (i283.pas, i283.cpp, ...), valamint a program rövid dokumentációja (i283.txt, i283.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ó.

A feladat megoldásához letölthető állomány:   helyforr.dat

(10 pont)

megoldás, statisztika


I. 284. A vitaminok az emberi szervezet számára nélkülözhetetlen, biológiailag aktív szerves vegyületek. A legfontosabb vitaminok adatai állnak rendelkezésre a vtabla.txt állományban. Emellett a vitforras.txt állomány adatai azt adják meg, hogy az egyes vitaminok milyen élelmiszerekben fordulnak elő.

1. Készítsünk új adatbázist vitamin néven. Importáljuk az adattáblákat az adatbázisba vtabla és vitforras néven. A txt típusú adatállományok tabulátorokkal tagolt UTF-8 kódolásúak, és az első soruk tartalmazza a mezőneveket.

2. A létrehozás során állítsuk be a megfelelő típusokat és kulcsokat. A vitforras táblához adjunk hozzá azon néven egyedi azonosítót.

Készítsük el a következő feladatok megoldását. A zárójelben lévő néven mentsük el azokat. Ügyeljünk arra, hogy a megoldásban pontosan a kívánt mezők szerepeljenek.

3. Listázzuk lekérdezés segítségével a vízben oldódó vitaminok nevét, minimális és maximális napi szükségletét. (3vizben)

4. Készítsünk lekérdezést, amellyel felsoroljuk a B12-vitamint tartalmazó élelmiszerek nevét. (4b12)

5. Adjuk meg lekérdezés segítségével azoknak az élelmiszereknek a nevét, amelyekben kettőnél több vitamin van. Az élelmiszerek neve mellett jelenítsük meg a bennük előforduló vitaminok számát. (5tobb)

6. Adjuk meg lekérdezés segítségével, hogy az A-vitamint tartalmazó élelmiszerek milyen más vitamint tartalmaznak még. A listában minden vitamin neve egyszer szerepeljen, de az A-vitamint már ne jelenítsük meg. (6avit)

7. Lekérdezéssel határozzuk meg azoknak az élelmiszereknek a nevét, amelyek egyszerre zsír és vízoldható vitaminokat is tartalmaznak. Minden élelmiszer neve egyszer szerepeljen a listában. (7komplex)

8. Készítsünk jelentést, melyben a vitaminok neve szerint csoportosítva és rendezve jeleníti meg az azokat tartalmazó élelmiszerek nevét ábécérendben. A jelentéshez létrehozhatunk segédlekérdezést, ha szükséges. (8jel)

9. Listázzuk ki azokat a vitaminokat, amelyekhez nincs élelmiszerforrás megjelölve az adatbázisban. (9hiany)

10. Készítsünk kereszttáblás lekérdezést, amelyben élelmiszerenként megadjuk, hogy a vitaminok közül melyeket tartalmazza. (10kereszt)

Beküldendő egy tömörített i284.zip állományban az adatbázis (i284.accdb, i284.odb, ...), valamint egy rövid dokumentáció (i284.txt, i284.pdf, ...), amelyből kiderül az alkalmazott adatbázis-kezelő neve, verziószáma.

A feladat megoldásához szükséges letölthető állományok: vitforras.txt, vtabla.txt

(10 pont)

megoldás, statisztika


I. 285. Valószínűleg sokan ismerik az általános vagy középiskolából a Logo nyelvet, amelyben érdekes és izgalmas ábrákat készíthetünk egy teknőc irányításával. Az Imagine Logo programozási környezetet minden tanuló és tanár számára szabadon használható és letölthető a http://logo.sulinet.hu oldalról. A feladatunk az lesz, hogy tanítsuk meg a teknőcöt labirintust rajzolni, illetve kitalálni egy labirintusból.

Először rajzoljunk egy véletlen labirintust, melynek minden járata és minden fala 11 egység széles, tehát alapelemként 11×11 méretű fehér (járat) vagy fekete (fal) négyzetekből áll. A labirintust létrehozó labkész :n :m eljárás két paramétere a labirintus négyzeteinek vízszintes és függőleges száma (két páratlan pozitív egész). A labirintus közepe a rajzlap közepére kerüljön, és egy kijáratot tartalmazzon a bal felső sarok alatti négyzet helyén.

A teknőc érzékeli a lapon az adott helye alatti pont színét. Másodszor ennek felhasználásával készítsünk egy elhelyez :n :m eljárást, amely véletlenszerűen elhelyezi a teknőcöt a labirintusba egy járat négyzet közepére úgy, hogy észak felé nézzen, és egy kitalál :n :m eljárást, amely megpróbálja kivezetni a teknőcöt a labirintusból. A teknőc húzzon egy 5 egység vastag színes vonalat, amely mutatja, hogy mely járatokon haladt keresztül, de a négyzeteken belüli apró mozgásoknál a teknőc ne húzzon vonalat. Az eljárás érjen véget, ha a teknőc kiért a labirintusból.

A kivezető algoritmus nagyon egyszerű is lehet, tehát nem követelmény, hogy a teknőc minden labirintusból kijusson. A körjáratot nem tartalmazó labirintusokból pl. ki lehet jutni úgy, hogy olyan módon mozgunk, hogy közben tőlünk jobbra mindig fal van.

A megoldás során csak a teknőcgrafikát és a Logo nyelv funkcionális részét használjuk. Ne alkalmazzunk változókat, csak rekurzió segítségével valósítsunk meg ismétlést. Igyekezzünk minél több önállóan is értelmes függvényre és eljárásra bontani a megoldást, pl. négyzet rajzolása, annak megállapítása, hogy van-e fal előttem stb.

Beküldendő egy i285.zip tömörített állományban a megoldást tartalmazó i285.imp Imagine Logo Project és egy i285.txt szöveges állomány, amely ismerteti a megoldás során készített egyes eljárásokat és függvényeket.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2012. február 10-én LEJÁRT.


S. 68. Adatok tömörítésének egyik módja a Huffman kódolás. Az októberben kitűzött I. 276. feladatban a kódolás menetét kellett egy prezentációban bemutatnunk, most feladatunk a kódolást végző program elkészítése.

A módszer lényege, hogy az eredeti állomány minden bájtját különböző hosszúságú bitsorozatra cseréli úgy, hogy a ritkábban előforduló bájtok hosszabb, a gyakoribb bájtok rövidebb bitsorozatot kapnak. A kód létrehozásának alapja, hogy az eredeti állomány egyes bájtjainak gyakorisága alapján létrehozunk egy bináris fát, majd megfelelő módon bejárjuk.

A fa felépítésének lépései a következők:

1. Először minden bájtot a gráf egy izolált pontjának tekintünk, amelynek nincsenek leágazásai, és értéke a benne szereplő karakter gyakorisága.

2. Ezután a két legkisebb gyakoriságú bájt pontját összevonjuk, és befűzzük őket egy olyan új gráfpont bal és jobb ágába, amelynek értéke a két karakter gyakoriságának összege, majd a két eredeti gráfpontot töröljük.

3. A 2. pontot ismételjük addig, amíg az összes betűt föl nem fűztük egy bináris fába.

Az így létrejött fában a gyökérelemtől indulva megkapjuk az egyes karakterek Huffman kódját úgy, hogy a karakterhez vezető úton minden balra lépés 0-ás bitet és minden jobbra lépés 1-es bitet jelent.

Készítsük programot s68 néven, amely a parancssor első argumentumaként megadott állomány bájtjainak egy lehetséges Huffman kódját előállítja, és a parancssor második argumentumaként megadott szöveges állományba írja soronként az egyes bájtokhoz rendelt új bitsorozatot és azok hosszát a kapott kód hossza, illetve azon belül ABC sorrendben a mintának megfelelő formában. Az ASCII tábla szerint nem nyomtatható karakterek és a szóköz helyett a karakter kódja jelenjen meg. A program ezen kívül írja a standard kimenetre a bemeneti állomány eredeti és kódolt méretét bit mértékegységben.

Beküldendő egy tömörített s68.zip állományban a program forráskódja (s68.pas, s68.cpp, ...) az .exe és más fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s68.txt, s68.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás melyik fejlesztő környezetben fordítható.

A megoldás teszteléséhez fölhasználható állományok: s68.zip

(10 pont)

megoldás, statisztika


Figyelem!

Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.