Zkouška 28.6.2010

Dneska šlo o písmenka.

Na vstupu jsme dostali slovo {: alt="\leq 100" type="image/"} znaků dlouhé složené z písmen anglické abecedy (26), a dále pak seznam substitučních pravidel, kterých je také maximálně 100. Substituce jsou buď 1 písmeno za 1 písmeno (a->b) nebo 1 písmenko za 2 (a->bc).
Výstupem má být množina písmen, ze kterých jde dané slovo vystavět. Paměti máme 1MB.
Trochu vysvětlení: ve výstupní množině jsou ta písmena, z kterých postupnými substitucemi může vzniknout slovo na vstupu.
Příklad:
abac
a->b
a->c
a->ab
c->ac
Výstup: a, c

Osobně nevím, jestli jsem volil správný způsob řešení, tak raději nebudu kazit.
A když by někdo nastínil, jak by se to mělo řešit, bylo by to hezké.

Úloha šla řešit dynamickým programováním. Nejdřív je dobré si vygenerovat všechna substituční pravidla, která mění 1 písmeno za 2 (a která lze složit z těch zadaných). No a pak si všimneme, že na začátku máme jedno písmeno, to se nám změní na dvě a ta dvě si pak žijí nezávislý život a z každého vystavíme jednu část výsledného slova. Jenže nevíme, kde ten řez mezi nimi je...

Tolik komentář, teď algoritmus: ve výsledném slově si určíme pro každou dvojici po sobě následujících písmen, z jakých jednotlivých písmen ji můžeme vytvořit. Pak totéž uděláme pro trojice, čtveřice.... Jak? Úsek délky n můžeme (n-1) způsoby rozdělit na dva kratší a pro ty generující písmena známe a použijeme odvozená pravidla zmiňovaná v úvodu.

Stačí na to 300kB a při nadsazených odhadech vyjde asi 10^12 instrukcí, což při taktovací frekvenci 1GHz odpovídá asi 15 minutám.

Martina

A vřele doporučuji umět B-stromy, je to hrozně příjemná a jednoduchá otázka, a padá velice často. Dneska jsem koukal na papír kde měl poznámky k těm, co byli dnes předemnou, a snad každého se na ně ptal, a skoro všichni dostali za 4, tak se opravdu vyplatí je umět.