Zkouška 9. 6. 2009 - Scrablle

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.
Sylverlin
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 9. 6. 2009 21:48
Typ studia: Informatika Bc.

Zkouška 9. 6. 2009 - Scrablle

Příspěvek od Sylverlin »

Zadání: Scrabble.
http://www.forum.matfyz.info/viewtopic.php?f=351&t=3272

*SPOULER WARNING*

Řešení:
- je to (evidentně...) úloha na prořezávání stavového prostoru
- slovník reprezentovat dvakrát: prefixová, resp. sufixová trie (tzn. jednou udělaná odzadu, jednou odpředu - kontrolování slov po směru a proti směru)
- a podle slovníku prořezávat
- pozor na speciální případ, kdy přidávám na konec nebo začátek nějakého existujícího slova, ale stavím kolmo na něj - tady je potřeba prořezávání vypnout a prostě projít všechny možnosti. Na druhou stranu, dá se taky zkusit začít kdekoliv, ne jenom na políčkách sousedících s existujícími slovy, což - myslím - tenhle problém obchází. (Což mě napadlo, bohužel, přesně ve chvíli, kdy jsem dostal podpis do indexu. For the record za 1. :-) )
Tohle jsou klíčové body. Další užitečnost je např. v reprezentování políček hracího plánu: mít odkazy na obsazené sousedy - výrazně to ulehčuje potom načítání slov vytvořených "bokem", dají se asi vymýšlet všelijaké heuristiky (např. projít si na začátku písmenka a zkusit v nich předpřipravit nějaká hotová slova, která by se dala přikládat různě podél existujících slov...), ale hlavní je prořezávání přes ty dvě trie, respektive když se začíná odkudkoliv, stačí jedna.

Jo, nejsem si jistý, jestli se to říkalo v zadání, ale Holan s Töpferem hrajou scrabble tak, že přidávají jenom souvislá pole, tzn. nekříží. Moje řešení fungovalo i pro křížící se slova (hrajeme halt doma scrabble jinak. :-) ), ale to jsou detaily, které se snadno vyřeší na ústním. Tím mým směrem aspoň se to vyřeší snadno a rychle.
Odpovědět

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