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. 65. feladat (2011. október)

S. 65. Már a korabeli azték birodalom fénykorában is szükségesnek látták az uralkodói üzenetek titkosítását. A neves régész, Kamoo professzor szerint a kódolás alapja Ometeotl, a kettőség istenének két jele: a férfias erőt (<) és a női gyengédséget (>) jelképező két szimbólum volt. Ezekből az istenség parancsára csak az alábbi két szabály betartásával volt szabad jelsorozatokat létrehozni:

-- érvényesülnie kellett az egyensúlynak, tehát azonos számú < és > jel szerepelt minden sorozatban;

-- balról-jobbra olvasva a sorozatot annak tetszőleges jeléig mindig több, vagy azonos számú férfi szimbólum szerepelt, mint női szimbólum, tehát az erőt és aktivitást jelképező szimbólumok mindig megelőzték a gyengédséget és passzivitást jelölő szimbólumokat.

A vázolt módon létrehozhatóak különböző hosszúságú jelsorozatok, melyek sorba rendezhetők a hosszúságuk, illetve a < jelek elhelyezkedése alapján:

(1) A rövidebb jelsorozatok előbb vannak, mint a hosszabbak;

(2) az azonos hosszúságúakon lexikografikus rendezést alkalmazunk (ha tudunk, akkor az első betű alapján döntünk; ha ezek megegyeznek, akkor a második alapján stb.).

Például a legföljebb hat hosszúságú jelsorozatok sorrendje:

<>
<<>>
<><>
<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

Ennek alapján tehát van egy (végtelen hosszú) rendezett R listája a < és > szimbólumokból álló jelsorozatoknak. Ezután a kódolás egyes lépései a következők voltak:

(1) A nyelv betűi (az egyszerűség kedvéért az angol ábécét használjuk) és a szóköz megfelelnek a 27-es számrendszer számjegyeinek (\mathrm{a}=0, \mathrm{b}=1, \mathrm{c}=2, ..., \text{szóköz}=26);

(2) az üzenetet b hosszúságú blokkokra bontjuk (ha a szöveg hossza nem osztható b-vel, akkor szóközökkel kipótolják a végét);

(3) az egyes blokkokat kiolvassuk 27-es számrendszerbeli számokként;

(4) az így kapott számoknak megfelelő sorszámú jelsorozatokat kiválasztjuk a fenti R listából és ezeket szóközökkel elválasztva egymás után írjuk.

Készítsünk programot ami képes kódolni, illetve dekódolni az uralkodó üzeneteit.

A bemeneti állomány első sorában a blokkok b hossza szerepel (1\leb\le12). A második sorban egy kódolandó vagy dekódolandó karaktersorozat szerepel. A szóközökön kívül, az előbbiekben csak az angol ábécé kisbetűi, az utóbbiakban pedig csak a < és > karakterek szerepelnek. Feltehetjük, hogy a bemenet nem kezdődik szóközzel.

A kimeneti állomány egyetlen sorába a kódolás vagy dekódolás eredményét írjuk.

Megjegyzés: A példákban a kódolt üzenetekben a szóközök helyett néhol sortörések látszanak.

(10 pont)

A beküldési határidő 2011. november 10-én LEJÁRT.


A feladatot dinamikus programozással lehetett hatékonyan megoldani. Mintamegoldásként Adrián Patrik, és Marussy Kristóf megoldásait közöljük.

AdrianPatrik.zip

MarussyKristof.zip

A két megoldás hasonló, viszont utóbbiban egy formálisabb, részletesebb leírás található.


Statisztika:

11 dolgozat érkezett.
10 pontot kapott:Adrián Patrik, Havasi 0 Márton, Marussy Kristóf, Nagy Róbert, Strenner Péter, Szabó 262 Lóránt, Szilágyi Dániel.
9 pontot kapott:Szabó 928 Attila.
7 pontot kapott:1 versenyző.
5 pontot kapott:1 versenyző.
3 pontot kapott:1 versenyző.

A KöMaL 2011. októberi informatika feladatai