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 I. 216. feladat (2009. május)

I. 216. A márciusi számban már megismerkedtünk a ,,MasterMind'' játékkal. Barátunk - elmondása szerint - a következő egyszerű algoritmust használva játszik: a lehetséges tippek lexikografikusan rendezett listájából mindig a legelsőt választja. Annak kiderítésére, hogy valóban ezt a módszert követi-e, írjunk egy programot, amely bármely kitalálandó sorozatra megadja a szükséges tippek számát és a tippek sorrendjét.

A program a standard bemeneten egyetlen sort várjon, a kigondolt karaktersorozatot (szóközök nélkül); a választ a standard kimenetre írja, n lépésben kitalálható feladvány esetén n+1 sorba.

Például, ha a kigondolt jelsorozat ,,DADA'', akkor a kimenet:

Beküldendő a program forráskódja (i216.pas, i216.cpp, ...) valamint a program dokumentációja (i216.txt, i216.pdf, ...), amely megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható.

(10 pont)

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


A feladat nem volt nehéz, ennek ellenére sajnos nagyon kevés megoldás érkezett.

A könnyű megoldáshoz vezető lényeges felismerés az, hogy az elrejtett és a tippelt sorozatok az értékelés szempontjából felcserélhetők. Ebből az következik, hogy egy tippre kapott válasz alapján csak azok a sorozatokat lehetségesek, amelyek a tippel összevetve ugyanezt a választ eredményezik, a többi figyelmen kívül hagyható.

A feladat megoldása során a legcélravezetőbb volt elkészíteni a lehetséges tippek lexikografikus sorrendjét, a lehetségesek közül az elsőt tippelni, majd a válasz alapján (az iménti felismerést felhasználva) a nem lehetségeseket kihúzni. A tippelést addig kell ismételni, amíg a lehetségesek listája nem szűkül egyetlen elemre.

A helyes megoldást adók közül Szabó 928 Attila munkáját közöljük. i216sza.zip


Statisztika:

4 dolgozat érkezett.
10 pontot kapott:Balla Attila, Englert Péter, Szabó 928 Attila.
0 pontot kapott:1 versenyző.

A KöMaL 2009. májusi informatika feladatai