Zkouška 18. 6. 2012

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
mjk
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 6. 9. 2011 17:40
Typ studia: Informatika Bc.

Zkouška 18. 6. 2012

Příspěvek od mjk »

Dostali jsme úlohu s písmenky, která tu na fóru už je (http://forum.matfyz.info/viewtopic.php?f=247&t=6897), ale připadala mi nejasně napsaná a tak jsem si ji doma nepromyslel. Zkusím ji napsat ještě jednou, třeba to někomu ušetří hodinu nervů na písemce :-)

Zadání:
Na vstupu dostaneme slovo S dlouhé nejvýše 100 znaků. Dále pak nejvýše 100 přepisovacích pravidel ve tvaru a->b nebo a->bc, kde a, b, c jsou písmena z anglické abecedy {a..z}.
Na výstup máme napsat všechna písmena, ze kterých jde postupným uplatňováním přepisovacích pravidel vytvořit slovo S. Můžeme přepsat kterýkoli znak chceme, pravidlo se nepoužije na celé současné slovo najednou.
Např:
Mějme vytvořené slovo "slovo" a přepisovací pravidla s->o, v->ni, o->ce. Můžeme vytvořit třeba slova "slonice", "olovo", "slonio", "celonice".

Paměti máme k dispozici 400 kB a mělo by to seběhnout v rozumném čase.

Ukázkový vstup
abacb
a->b
a->c
a->ab
c->ac
c->b (přidali, když zjistili, že jen s prvními čtyřmi to nedává ukázkový výstup)

Ukázkový výstup
a c

(Např: a -> c -> ac -> abc -> abac -> abaac -> ababc -> abacc -> abacb)

Řešení
Dynamické programování.
Nejprve si vygenerujeme všechny náhrady a->bc, které můžeme získat složením náhrad zadaných na vstupu. Do trojrozměrného pole P 26*26*26 booleanů si pak na pozici (a, b) uložíme množinu všech písmen, která mohou být skládáním pravidel změněna na ab.

Označme n délku slova S. Vytvoříme si trojrozměrné pole n*n*26 booleanů, kde na pozici (i,j) je množina písmen, ze kterých se dá vygenerovat úsek slova S o délce i a začínající na pozici j. (Na i-tém řádku využijeme jen prvních (n - i +1) políček, další úseky už by přečuhovaly.)
První řádek vyplníme snadno. Na j-tém políčku jsou v něm písmena, ze kterých se dá změnami typu a->b vytvořit j-té písmeno slova S a také toto písmeno (pro případ, že by slovo S mělo délku 1 (nebo to můžeme ošetřit nějak jinak)).
Úseky na (i+1)-ním řádku (délky větší než 1) určitě vznikly ze dvou písmen (a ty dvě z jednoho), z prvního první část úseku a z druhého druhá. Předěl může být za prvním až předposledním znakem úseku, a tak všechny tyto pozice vyzkoušíme. Pro každou se podíváme na příslušné již spočítané podúseky, u každého máme uložená písmena, ze kterých se dá vygenerovat. Projdeme všechny dvojice (a,b) kde a generuje první podúsek a b druhý a pro každou dvojici zjistíme (z pole P na pozici (a,b)) všechna písmena, která ji generují. Ta přidáme do množiny generátorů právě počítaného úseku na řádku i.
Nakonec budeme mít na pozici (n,1) výslednou množinu písmen, ze kterých se dá vygenerovat celé slovo S.

Vejdeme se do 300 kB a časová složitost je O(n^3) (pokud považujeme počet písmen za konstantu + by bylo lepší tam započítat i počet pravidel).


Někde jsem tu četl doporučení jít na ústní ten samý den, než si ty papíry zkoušející stačí pořádně přečíst. Podle toho, co říkali při zadávání, i podle toho, jak probíhala ústní, bych řekl, že je naopak (moc) nečtou. Protože jsem šel na ústní až následující den, měl jsem možnost si to pořádně promyslet, zjistit co mi v písemce chybí a na zkoušce to v podstatě přednést znovu. Tak se zařiďte podle sebe :-)
Odpovědět

Zpět na „PRG031 Programování II“