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 2013. novemberi 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ő 2013. december 10-én LEJÁRT.


I. 331. Az ókori egyiptomi matematika egyik érdekessége, hogy néhány kivételtől eltekintve a törteket mindig törzstörtekként írták föl. Például a 3/8 az egyiptomi papiruszokon 1/4+1/8 alakban szerepel, vagyis egység számlálójú törteket használtak. Az 1/8+1/8+1/8 triviális felírást nem alkalmazták, mivel más felírásokhoz képest hosszú eredményt adott. Ezenkívül minden műveletet igyekeztek az összeadás és a kivonás segítségével elvégezni, illetve szorzás és osztás helyett legtöbbször kétszerezést és felezést végeztek. Például a 13 szorozva 17-tel eredményét a következő gondolatmenet alapján számolták ki:

A jobb oldali oszlopban visszafelé kell haladni, így az eredmény 136+68+17=221.

Az egészek osztása sem volt egyszerű feladat, például 62 osztva 13-mal a fennmaradt papiruszok szerint a következő módon végezhető el:

Ezután következett a 10 osztása 13-mal, aminél először felezgettek (most a jobb oldali oszlopban is előre haladva kell gondolkodni):

Maradt tehát annak a végiggondolása, hogy az 1/4 melyik számnak a 13-szorosa, amihez a 13-adokat nézték meg:

Az eredmény tehát 4+1/2+1/4+1/52. Mivel a törtek számlálója mindig egy, ezért egyszerűen 4 /2 /4 /52 alakban tudjuk felírni az osztás eredményét.

Sain Márton Nincs királyi út című matematikatörténeti könyvében, amely a Magyar Elektronikus Könyvtárban online elérhető, további leírást találunk az egyiptomi számolásról.

Készítsünk programot i331 néven, amely az egyiptomiak által használt, fent leírt alapműveletek segítségével elvégzi két, egymilliónál kisebb egész szorzását vagy osztását. A program az argumentumként megadott állomány minden sorának műveletét számítsa ki és a második argumentumként megadott állományba írja soronként az eredményt.

Beküldendő egy tömörített i331.zip állományban a program forráskódja (i331.pas, i331.cpp, ...), valamint a program rövid dokumentációja (i331.txt, i331.pdf, ...), amely megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika


I. 332. Magyarország legnagyobb fáinak adatait nyilvános listákban gyűjtik több, mint tíz éve (http://www.dendromania.hu/index.php?old=foold). A gyűjtés során feljegyzik a fa fajnevét, körméretét, földrajzi koordinátáit és a feljegyzés évét. A Somogy megyei feljegyzések adatai a fa.txt állományban találhatók, és a helyzetük megadásához a hely.txt-ben a települések nevei és lakosainak száma áll rendelkezésre. Mindkét állomány letölthető honlapunkról.

1. Készítsünk új adatbázist somogyifak néven. A mellékelt állományokat, a fa.txt-t fa és a hely.txt-t hely táblanéven importáljuk az adatbázisba. Az állományok tabulátorral tagolt, UTF-8 kódolású szövegfájlok, az első soruk a mezőneveket tartalmazza. A fa táblához adjunk hozzá id néven egyedi azonosítót. A létrehozás során állítsuk be a megfelelő típusokat és a kulcsokat.

Tábla:

A következő feladatok megoldásánál a lekérdezéseket és a jelentést a zárójelben olvasható néven mentsük. Ügyeljünk arra, hogy a lekérdezésben pontosan a kívánt mezők szerepeljenek, felesleges mezőt ne jelenítsünk meg.

2. Készítsünk lekérdezést, amely ábécérendben jeleníti meg a 7-9 méter közötti kerületű fák fajnevét és körméretét méterben. (2vastag)

3. Az erdős területek aránya és ezzel együtt a nagy méretű fák száma településenként jelentős eltéréseket mutat. Lekérdezés segítségével listázzuk ki, hogy településenként hány fáról állnak rendelkezésre adatok. (3feljegyzesek)

4. Készítsünk lekérdezést, amely megadja, hogy az egyes településekhez hány tölgy feljegyzése tartozik. A listát darabszám szerint csökkenően, a település nevével együtt jelenítsük meg. Azonos darabszám esetén a település neve szerinti ábécérendben legyen a lista. (4tolgy)

5. Lekérdezés segítségével írjuk ki a legnagyobb kerületű fa fajnevét, körméretét, feljegyzésének évét és településének nevét. (5kover)

6. A barkócaberkenye Magyarországon 2000-ben az ,,Év fája'' volt. Lekérdezés segítségével gyűjtsük ki milyen fajú fák élnek azon a településen, ahol a barkócaberkenye. A listában a barkócaberkenye neve ne, minden további fajnév egyszer jelenjen meg. (6berkenye)

7. A fákra őrködő, vigyázó településeken többféle nevezetes fa lehet. Lekérdezés segítségével írassuk ki az ötnél több fajta fa feljegyzésével rendelkező településeket. A listában fajtaszám szerint csökkenően jelenítsük meg a települések nevét, lakosságszámát és a fajták számát. (7gazdag)

8. Lekérdezés segítségével listázzuk ki azokat a településeket ábécérendben, ahonnan valamilyen tölgy és bükk fajta feljegyzése is van az adatbázisban. A listában minden település neve egyszer jelenjen meg. (8egyszerre)

9. Készítsünk paraméterezhető lekérdezést, amelynek megadva egy földrajzi hosszúsági és szélességi koordinátát szögperc mértékegységben kiírja a legközelebbi fa faját, körméretét és települését. A gömbi koordinátákat tekintsük X--Y koordinátáknak és a szintkülönbségtől tekintsünk el. A sík két pontja, (x1,y1) és (x2,y2) közötti távolság: d=\sqrt{{(x_{2}-x_{1})}^{2} +{(y_{2}-y_{1})}^{2}}. (9kereso)

10. Készítsünk jelentést, amely azokat a településeket jeleníti meg, amely a Somogyban előforduló fenyők óriás példányainak előfordulási helyei. A jelentés tartalmazza települések nevét, a fák fajnevét és körméretét településenként csoportosítva, azon belül körméret szerint növekvő sorrendben. A jelentést a megfelelő mezőket tartalmazó lekérdezéssel vagy ideiglenes táblával készítsük elő. A mintát szövegszerűségben és a mezők sorrendjében kövessük, formázásban nem szükséges. (10fenyo)

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

Letölthető fájlok: fa.txt, hely.txt.

(10 pont)

megoldás, statisztika


I. 333. Minden gyerek és felnőtt szeret szappanbuborékot fújni. Sok érdekes jelenség figyelhető meg a buborék falát alkotó hártyán.

Készítsük el gif-animációs szerkesztőprogrammal a szappanbuborékot eregető pálcikaemberke mozgását. A megoldáshoz ajánljuk a Stykz vagy a Pivot Stickfigure Animator nevű (internetről ingyenesen letölthető) programot. (A programokról a http://blog.sulinet.hu/oktinf/category/palcikaanimacio/ oldalon rövid leírás olvasható, illetve oktatófilmek találhatók az ismert videómegosztókon.)

Az animációban a buborékfújást, majd a buborékok mozgását jelenítsük meg. Törekedjünk a filmszerű megjelenítésre. Például az ellibbenő buborék látványát a háttér elmozdításával is előállíthatjuk.

Az animációra végtelenített lejátszást és megfelelő képváltási sebességet állítsunk be.

Beküldendő tömörített állományban (i333.zip) az animációk gif, valamint forrásállománya a szerkesztőprogram alapértelmezett formátumában és egy rövid dokumentáció (i333.txt, i333.pdf, ...), amely tartalmazza vázlatosan a megoldás leírását és a használt szoftver nevét.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2013. december 10-én LEJÁRT.


S. 84. Péter az öccsével a következő játékot játssza: megkéri őt, hogy találjon ki egy N különböző pozitív egészből álló számsorozatot. Ezután ezt az öcsi úgy kódolja, hogy az i-edik helyen álló szám helyére a c számot írja, amennyiben az eredeti sorozat i-edik számával végződő leghosszabb szigorúan monoton növekvő (nem feltétlenül összefüggő) részsorozata c számból áll. Például a kigondolt, eredeti sorozat lehet a 3 1 2 4 8 20 10 sorozat. Ehhez a kódolt változat a következő: 1 1 2 3 4 5 5. Ezt a kódolt sorozatot kapja vissza Péter az öccsétől. Péternek az a feladata, hogy találjon egy olyan sorozatot, aminek a kódolt változata megegyezik az öccsétől kapott kódolt sorozattal. Készítsünk programot, amely segít Péternek játszani.

A program olvassa be a standard input első sorából N-et (N\le 500\;000), majd a következő sorból a kódolt sorozat elemeit, melyek szóközzel elválasztott egészek, és írjon a standard output első és egyetlen sorába egy olyan N db pozitív egészből álló sorozatot, melyet ha kódolunk, akkor pont a bemenetet kapjuk. Mivel több megoldás lehet, így mindegy, melyiket adjuk meg. A bemeneti számok egyike sem nagyobb 10000000-nál, a kimenet se legyen ennél nagyobb. A kimenet különböző számokból kell, hogy álljon.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. A megoldásért részpontszámok kaphatók, ha a program N\le5-re, illetve N\le500-ra megoldást ad.

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

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