Zkouška 28.6.2010

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.
mrwep
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 13. 2. 2010 15:06
Typ studia: Informatika Bc.

Zkouška 28.6.2010

Příspěvek od mrwep »

Dneska šlo o písmenka.

Na vstupu jsme dostali slovo \leq 100 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é.
Martina

Re: Zkouška 28.6.2010

Příspěvek od Martina »

Ú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
mrwep
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 13. 2. 2010 15:06
Typ studia: Informatika Bc.

Re: Zkouška 28.6.2010

Příspěvek od mrwep »

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.
Odpovědět

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