 |
Az S. 10. feladat (2005. szeptember) |
S. 10. Írjunk programot 3×3-as bűvös négyzet kitöltésére, néhány előre megadott elem alapján. (Az iskolából is jól ismert bűvös négyzetek számokkal kitöltött, négyzet alakú táblázatok, amelyekben az elemek összege minden sorban, oszlopban és átlóban ugyanaz.)
A program a standard bemenetről olvassa be a kiinduló állapotot. A mezők tartalmát három sorban, szóközökkel elválasztva fogjuk megadni. Az előre beírt számok legfeljebb háromjegyű egészek lesznek, az üresen hagyott helyeket X jelöli. A program ugyanilyen formában írja ki a végeredményt a standard kimenetre. Az eredményben törtek is előfordulhatnak; ezeket kerekítsük két tizedes jegyre.
Lehetséges, hogy a megadott számok ellentmondást okoznak, és a bűvös négyzetet nem lehet kitölteni. Ilyenkor a program írja ki azt, hogy ,,Nincs megoldás''. Hasonlóan előfordulhat, hogy többféle (végtelen sok) megoldás létezik; ilyenkor a program írjon ki egy megoldást, és a következő sorba írja azt, hogy ,,A megoldás nem egyértelmű''.
Példák:
(10 pont)
A beküldési határidő 2005. október 17-én LEJÁRT.
Megoldás. Közismert - de egy kis számolással könnyen ellenőrizhető is - hogy minden 3×3-as bűvös négyzet a következő alakú:
|
A feladat tehát egy háromváltozós lineáris egyenletrendszer megoldása az x,y,z változókra. Minden olyan cella, amibe számot írtak, egy egyenletet jelent.
A program három részből áll: a beolvasásból, ami létrehozza a kért egyenleteket, az egyenletrendszer megoldásából és a megoldás kiírásából.
Az egyenleteket célszerű 4-elemű vektorokban tárolni, amelyek első három eleme az x,y,z együtthatója, a negyedik elem az egyenlet konstans tagja. Az input legfeljebb 9 egyenletet definiál.
A két lenti példaprogramban a jól ismert eliminációs módszert alkalmaztuk. Az elimináció háromféle lépésből áll:
a) egy egyenletet végigszorzunk/osztunk egy számmal úgy, hogy az egyik kiszemelt együttható értéke pontosan 1 legyen;
b) egy egyenlethez hozzáadjuk egy másik egyenlet számszorosát úgy, hogy az egyik kiszemelt együtthatója 0 legyen;
c) kicserélünk két egyenletet.
Mivel az egyenletrendszerünk hiányos is lehet, ehhez a következő lépést is megengedjük:
d) ha a megoldás nem lehet egyértelmű és ez nem okoz ellentmondást, akkor a rendszerhez hozzávehetjük az x=0, y=0 és z=0 egyenletek valamelyikét.
Az elimináció célja az, hogy az egyenletrendszert a következő alakra hozzuk:
1x+0y+0z=a,
0x+1y+0z=b,
0x+0y+1z=c.
Ha háromnál több egyenletünk van, akkor a többi egyenlet az elimináció után csak 0x+0y+0z=d alakú lehet. Ha valamelyik d nem 0, akkor az egyenletrendszer ellentmondó volt.
Első lépésként az első egyenletet normáljuk, azaz végigosztjuk úgy, hogy az x együtthatója 1 legyen. Ha az x együtthatója 0, akkor az első egyenletet kicseréljük egy másikkal. Ha az x együtthatója mindenhol 0, akkor a rendszer nem lehet egyértelmű, és hozzávesszük a rendszerhez az x=0 egyenletet.
Ezután a normált első egyenlet konstansszorosait vonjuk ki a többi egyenletből úgy, hogy az x együtthatója mindenhol kiessen.
A második lépésben az y együtthatóját normáljuk 1-re a második egyenletben, és a második egyenlettel elimináljuk az y együtthatóját az összes többiből. Ha az y együtthatója a második egyenlettől kezdődően mindenhol 0, akkor a rendszerhez hozzávesszük az y=0 egyenletet.
Végül ugyanez történik a z együtthatójával a harmadik egyenletben.
* * *
Példaprogramok:
* * *
A beérkezett dolgozatok tanulságai
A programokat összesen 1023 tesztadaton próbáltuk ki. A 9 mező összes részhalmazát kétféleképpen is kitöltöttük (kivéve az üres halmazt, amit csak egyféleképpen lehet. :-) ). Ahol lehetett, a kétféle kitöltés közül az egyik megoldható volt, a másik ellentmondásos.
Összesen három olyan program érkezett, ami mindegyik adatra hibátlan választ adott.
Néhány tipikus hibát kiemelnék.
1. A formai követelmények be nem tartása. Sok program nem soronként olvasott és nem a kért üzeneteket írta ki. Mivel a tesztelést automatizáltuk (egy tesztelő program futtatta le a megoldásokat mindegyik tesztadatra), ez sok nehézséget okozott. Különösen a Pascal programokra volt jellemző, hogy a program elején letörölték a képernyőt, a végén pedig az enter lenyomására vártak.
2. A leírás hiánya. A programokhoz elvárjuk, hogy a megvalósított algoritmust röviden írjátok le, és a programkódban elhelyezett kommentekből kiderüljön, hogy az egyes eljárások mit csinálnak, és a fontosabb változóknak mi a tartalma. Sokan ezt teljesen elmulasztották.
3. Struktúrálatlan, olvashatatlan kódok. Az eljárások nem különültek el (pl. nem volt közöttük üres sor), sokszorosan egymásba skatulyázott blokkok stb. A programokat érdemes kisebb eljárásokra bontani; akkor olvashatóbbak, az egyes eljárásokat külön-külön tudjátok tesztelni és a hibákat is sokkal könnyebb megtalálni.
Kérjük, hogy tanulmányozzátok a fenti megoldást és a példaprogramokat.
Kós Géza
Az 1023 tesztadat letölthető innen.
Statisztika:
25 dolgozat érkezett. 10 pontot kapott: Engedy Balázs, Grósz Dániel, Nikházy László. 8 pontot kapott: 1 versenyző. 7 pontot kapott: 1 versenyző. 6 pontot kapott: 5 versenyző. 5 pontot kapott: 3 versenyző. 4 pontot kapott: 3 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 2 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 5 versenyző.
A KöMaL 2005. szeptemberi informatika feladatai