Az I. 484. feladat (2019. május)

I. 484. A Hanoi tornyai nevű játék rendkívül egyszerű. Három rúddal és \(\displaystyle N\) darab különböző méretű koronggal játszható. Kezdetben az egyik rúdon \(\displaystyle N\) korong helyezkedik el, alul a legnagyobb, majd fölötte rendre a kisebbek. Ekkor a másik két rúd üres. A játék szabályai szerint az egyik rúdról egy másikra kell átrakni a korongokat úgy, hogy minden lépésben egy korongot lehet áttenni, de nagyobb korong nem tehető kisebb korongra.

Peti is elkezdte játszani a játékot, de nem ért a végére. A játékot egy ilyen állapotban találjuk meg. Készítsünk programot, amely megad egy lehetséges lépéssorozatot, amellyel ez az állapot előállítható.

A program standard bemenetének első sorában annak a rúdnak a sorszáma szerepel, amelyen kezdetben az összes korong volt. A következő sorban három szám, az egyes rudakon található korongok száma van. A következő három sorban az adott rúdon található korongok mérete szerepel csökkenő sorrendben. A kimenet első sora egyetlen számot tartalmaz, az állapot eléréséhez szükséges lépések L számát. A következő \(\displaystyle L\) sor mindegyikében két szám található, egymástól pontosan egy szóközzel elválasztva. Az első szám megadja a rudat amelyről, a második pedig azt a rudat, amelyre átkerül a felső korong. Feltételezhetjük, hogy Peti legfeljebb 10 koronggal játszik.

Beküldendő egy i484.zip tömörített állományban a program forráskódja és a hozzá kapcsolódó dokumentáció. Utóbbi a problémamegoldás lényeges elemeire világít rá, valamint tartalmazza, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2019. június 11-én LEJÁRT.

A feladat a Hanoi tornyai feladatnak egy újraértelmezése. A versenyzők mindegyike sikerrel megoldotta a feladatot, bár a nagyobb számokat tartalmazó eseteknél nem mindenki találta meg a legrövidebb utat a célállapothoz. A következő teszteseteket használtuk az értékeléshez: i484teszt.zip

Ezúttal a legkisebb lépésszámú megoldást nyújtó programot tesszük közé, amelyet Ürmössy Dorottya készített. i484UD.cs i484UD.pdf

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Nagy 793 Márton, Ürmössy Dorottya.

A KöMaL 2019. májusi informatika feladatai