A KöMaL 2008. májusi informatika feladatai

I-jelű feladatok A beküldési határidő 2008. június 16-án LEJÁRT.

I. 187. Havazáskor a hópihék egymásra rakódnak. Bizonyos magasságot elérve a hótömeg megcsúszik, és veszélyes lavina alakulhat ki. A megcsúszás jelensége minden apró szemcsés, por állapotú szilárd anyagnál megfigyelhető. A jelenséget vizsgáljuk meg egy általunk készített szimulációs programmal.

A talaj az egyszerűség kedvéért legyen sík, N×M cellára (3N,M100) felosztva. A szimuláció minden lépésében essen 1 hópihe valamelyik véletlenszerűen kiválasztott cellára. A valóságban a hópihék időben párhuzamosan esnek, de sok szimulációs lépés végrehajtásával ezt jól közelíthetjük.

A hóréteg vastagsága fokozatosan növekszik, és ezt számoljuk minden cellában. Ameddig a HM (4HM12) kritikus magasságot nem éri el a hó, addig különösebb változás nem történik. Ha a cellában a hópihék száma eléri a kritikus értéket, akkor 4 szomszédjának átad egy-egy hópihét. (A cella értéke 4-gyel csökken és a négy oldalszomszédjáé 1-1-gyel nő.) Ennek hatására a szomszéd cellákban is megnő a hóréteg magassága és a kritikus magasság felett, az előbbiekhez hasonlóan azok is továbbadják a négy szomszédjuknak a hópihéket. Amennyiben a szomszéd cellában a magasság nem éri el a kritikus értéket, akkor az nem ad tovább és így a szomszédjait sem kell tovább vizsgálni. A vizsgált terület széléről ledőlő hó eltűnik. Ha az átadás több cellán keresztül végig vonul, akkor beszélhetünk megcsúszásról, és ha ez a terület nagy, akkor lavináról.

A program jelenítse meg minden hópihe leesése után a változást grafikusan. A jó megfigyelhetőség érdekében a cellákat 3×3-as, vagy 5×5-ös pixelekkel ábrázoljuk. Azokat a cellákat, amelyekben változás nem történt, színezzük egyforma színnel (háttérszín is lehet) és a megváltozott tartalmú cellákat egy másik színnel.

A szimuláció végrehajtása közben lépésenkénti és folyamatos üzemmódok közül lehessen választani. A program leállítását a felhasználó kezdeményezheti.

Beküldendő a program forráskódja (i187.pas, i187.cpp, ...), valamint a program rövid dokumentációja (i187.txt, i187.pdf, ...), amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika

I. 188. Aristid Lindenmayer (1925-1989), magyar származású holland biológus, matematikus a növényi fejlődést tanulmányozta algoritmusokkal. Szöveges képletekkel (generatív nyelvtannal) leírható vonalas fraktálokkal foglalkozott. Rendszerét nevének kezdőbetűje alapján L-Systemnek nevezik és ezt a teknőcgrafika előfutárának tekinthetjük. Szimbólumai a toll mozgásirányának és lépései hosszának információit hordozzák.

A fraktál rajzolásához egy axióma, egy szabály és a fordulás szöge szükséges. Az ábrák finomságát, felbontását a rekurzív helyettesítések száma adja meg.

Az egyik legismertebb vonalas fraktál a Koch-görbe.

Axióma: F
Szabály: F=F+F-F+F
Szög: 60
Helyettesítés: 3
Mi történik, ha az axiómát bővítjük?
A szabály a rekurzív helyettesítés formuláját adja.
Axióma: F-F-F
Szabály: F=F+F-F+F
Szög: 60
Helyettesítés: 3

Készítsük el az öt ábrán látható L-System fraktált az ingyenesen letölthető Inkscape vektorgrafikus rajzoló programmal. A 6. ábra saját alkotás legyen.

A programban kissé eldugott helyen található az L-System ábrákat generáló funkció. Indítás helye: Effektusok / Megjelenítés / L-rendszer.

Axióma és szabály elemek az Inkscape L-rendszerben:

Példa a verem használatára egy fa rajzolásánál:

Az elkészített ábrák könnyen színezhetők a vektorgrafikus rajzoló programmal.

Beküldendő az ábrákat leíró paraméterek listája (axióma, szabály, szög és a helyettesítések száma) egy rövid dokumentációban (i188.txt, i188.doc, ), valamint egy szabadon alkotott 6. ábra és annak paraméterlistája (i188.svg, i188.png, ...).

Az elkészítendő ábrák:

(10 pont)

megoldás, statisztika

I. 189. A Goldbach-sejtés szerint minden kettőnél nagyobb páros szám fölírható két prímszám összegeként. Vizsgáljuk meg, hogy a 100-nál nem nagyobb páros számok hányféleképp írhatók föl két prímszám összegeként. A megoldáshoz használjunk táblázatkezelőt: egy munkafüzet ,,Goldbach'' nevű munkalapján számítsuk ki a fenti páros számok lehetséges fölírásainak számát, és ábrázoljuk oszlopdiagramon a kapott eredményt. A megoldás során ne használjunk makrót vagy programmodult, kizárólag képleteket és beépített függvényeket.

Beküldendő a táblázatkezelő munkafüzet (i189.xls, i189.ods, ...), illetve egy rövid dokumentáció (i189.txt, i189.pdf, ...), amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve, verziószáma, valamint a megoldás vázlatos leírása.

(10 pont)

megoldás, statisztika

S-jelű feladatok A beküldési határidő 2008. június 16-án LEJÁRT.

S. 36. Egy ország városait vasútvonalak kötik össze az alábbiak szerint:

-az állomásokon kívül mindenhol csak egy vágány van, a vonatok csak az állomásokon tudják kikerülni, vagy megelőzni egymást;

-a vasútvonalak csak az állomásokon találkoznak, máshol nem keresztezik egymást;

-a vasúthálózat összefüggő, azaz bármely városból bármely másik városba vezet vasútvonal vagy közvetlenül, vagy más városok érintésével;

-a vonatok mindegyike ugyanazzal a sebességgel halad bármely vasútvonalon.

Készítsünk programot, amely az ország vasúthálózata és a vonatok jelenlegi helyzete ismeretében menetrendet készít, azaz megadja, hogy mely vonatok mikor és merre haladjanak, hogy eljussanak a célállomásukra úgy, hogy az utolsóként beérkező vonat beérkezési ideje a lehető legkisebb legyen.

Az ország vasúthálózatát egy szöveges állományban adjuk meg, amelynek minden sorában két város betűjele és a városok közötti útvonal megtételéhez szükséges idő szerepel szóközzel elválasztva. Legföljebb 25 város van, az angol ABC nagybetűivel jelölve. Bármely két város közötti menetidő kisebb, mint 100 perc. A vonatok helyzetét szintén egy szövegfájlban adjuk meg, melynek soraiban elsőként annak az állomásnak a betűjele szerepel, ahol a vonat áll; a sor további betűi mind egy-egy vonatot jelölnek, melyek a betűikkel jelzett városokba szeretnének eljutni. A betűk között itt is egy szóköz az elválasztás.

A program feladata annak megadása, hogy az egyes városokból mikor és melyik útvonalon indítsuk el a vonatokat. A menetrendet egy szöveges kimeneti állományba írja a program, melynek egyes soraiban a vonat indításának perce, a vonat induló és célállomása egybe írva, valamint annak a két városnak a betűjele szerepeljen szintén egybe írva, amelyek között a vonat majd halad. A kiinduló állapotot tekintjük az időmérés kezdetének. A program írja egy másik szöveges kimeneti állományba a vonatok érkezésének idejét és az induló és célállomásuk betűjelét egybe írva. A kimeneti állományok egyes sorai legyenek az időpontok szerint növekvő sorrendben. A program négy parancssori paramétere közül az első a vasúthálózatot, a második a vonatokat tartalmazó bemeneti állományok nevei, míg a harmadik és negyedik a menetrendet és az érkezést megadó kimeneti állományok nevei.

Beküldendő a program forráskódja (s36.pas, s36.cpp, ...), valamint a program rövid dokumentációja (s36.txt, s36.pdf, ...), amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

statisztika