A számítástechnika-versenyben kitűzött feladatok 2004. december

Kérjük, olvassa el a versenykiírást.

Az I pontversenyben kitűzött gyakorlatok

I. 91. Kísérletezzünk, gondolkozzunk!

Az ABCDEF szabályos hatszög A csúcsát rögzítjük, a C csúcs pedig végigfut egy adott e egyenesen. A C pont minden egyes C' helyzetéhez tekintsük az eredetihez hasonló AB'C'D'E'F' szabályos hatszöget.

a) Az Euklides programmal készítsünk animációt a mozgás szemléltetésére. Az animáció és a program egyéb beépített szolgáltatásai segítségével (például az animáció fázisainak egyidejű megjelenítésével) vizsgáljuk meg, hogy a hatszög csúcsai milyen pályát írnak le. Indokoljuk meg a sejtés helyességét.

b) Milyen tartományt súrol mozgás közben a szabályos hatszög köré írt (változó méretű) körlemez?

Beküldendő a megfigyeléseket és indoklásokat tartalmazó szöveges TEXT (!) állomány (i91.txt).

(10 pont)

Megjegyzés: Már szeptemberi számunkban javasoltuk olvasóinknak, hogy az interneten keressék meg az Euklides nevű (magyar nyelven is értő) programot, és ismerkedjenek meg használatával.

I. 92. Mikulás főhadiszállásán a manók szigorú titokban csomagolják a mikuláscsomagokat. Mikulásnak nincs főnöke, de (közvetve) minden manó a beosztottja. Minden manó csak a saját közvetlen főnökét és a közvetlen beosztottjait ismeri. Mikulás hirtelen úgy dönt, hogy minden csomagba berakat egy KöMaL-t is. Sürget az idő, ezért azt szeretné, hogy a lehető legkevesebb időt kelljen várni, hogy minden manó értesüljön a döntéséről. A manók egyesével tudják értesíteni közvetlen beosztottjaikat, mindegyiket egységnyi idő alatt. Mennyi idő szükséges minden manó értesítéséhez? Milyen sorrendben értesítsék ehhez az egyes manók a beosztottjaikat?

Készítsünk programot, amely adott főnök-beosztott gráfhoz kiírja a legrövidebb időt igénylő értesítési rendet.

Beküldendő a program (i92.pas).

(10 pont)

I. 93. Egész aritmetikás alapműveletek szemléltetése, legfeljebb 50 jegyű számokra:

Készítsünk táblázatot, amelynek második és harmadik sorába (cellánként egy-egy számjegyet írva, helyi érték szerint helyesen egymás alá) beírunk egy-egy számot, és a negyedik, ötödik, ill. hatodik sorban jelenjen meg a két szám összege, különbsége, ill. szorzata.

Beküldendő a táblázat (i93.xls).

(10 pont)

Az I-jelű feladatok megoldásai a következő címre küldendők:

Az S pontversenyben kitűzött feladat

S. 4. A Sokoban nevű számítógépes játék egy négyzethálós pályán folyik, ahol n darab ládát helyeztek el, ezeket a - szintén n darab - megjelölt mezőre kell tologatnunk a pályán mozgó emberkével. Az emberke vízszintesen és függőlegesen, összesen négy irányban mozoghat. Minden lépéskor vagy szomszédos üres mezőre kell lépnie, vagy pedig egy ládát kell maga előtt arrébb tolnia. (Egy mezőre természetesen csak egy láda kerülhet.) Bizonyos mezők ,,falak'', ahova nem léphetünk és ládát sem tolhatunk.

Írjunk programot a játék megoldására. A program a standard bemenetről olvassa be a kiinduló állást. Az első sorban a pálya magassága és szélessége fog állni, az utána következő sorok a pálya sorai lesznek. A mezőket a következő karakterekkel kódoljuk:

A program keresse meg a legrövidebb lépéssorozatot, amellyel a ládákat a helyére tolhatjuk (ha több legrövidebb is van, akkor bármelyiket választhatja), és írja ki a standard kimenetre. Az első sorba írja a lépésszámot, a második sorba pedig a lépéseket. A lépéseket az F (fel), L (le), B (balra) és J (jobbra) karakterekkel kódolja. Ha nincs megoldás, akkor írja ki azt, hogy NINCS.

A pálya legfeljebb 15x15-ös lesz (a szélső sorok és oszlopok csupa falból fognak állni), a ládák száma legfeljebb 3. A bemenetként kapott adatok mindig helyesek lesznek. Az outputon kívül más szöveget ne írjon ki a program.

Példa:

6 7
#######
#@#.###
#  *  #
#  $  #
#     #
#######

14
LJJBLLJFFLJJFB

(10 pont)

Az S-jelű feladatok megoldásai a következő címre küldendők:

A beküldési határidő: 2005. január 15.