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

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ú:

x-y x+y+z x-z
x+y-z x x-y+z
x+z x-y-z x+y

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:

C++ program

Pascal program

* * *

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