Matfyz Wiki

zápočet 18.2.09 dopoledne

QZuzka at 2009-02-19 00:03:34

Zadání nevypadalo extra složitě..
vlastně takové malé eternity :) obdélníková mřížka, do které se skládají čtyřbarevné kostičky tak, aby navazovaly strany se stejnou barvou.. Vstupem jsou povolené kostičky a částečně předvyplněná mřížka, výstupem je vykreslení výsledného složení, kde vykreslení kostičky zajišťuje dodaná třída.. (tedy poté co se povede naimportovat ten jar archiv... :)) )
Jak nám zadávající oznámil, vzhledem k NP-úplnosti úlohy se nečekal nějaký geniální algoritmus..
Velikost vstupů, pro kterou to půjde, se předpokládala rozumně malá, byly k dispozici vzorové vstupy..

Vlastně když to teď popisuju, přijde mi to docela jednoduché.. Jen se ta úloha ukázala časově náročnější... nastavovalo se asi půl hodiny.. a stejně byla úspěšnost téměř zanedbatelná.. (cca 3 ok)

Armi at 2009-02-19 10:24:44

Pripajam zadanie z popoludnajsieho terminu :
Mali sme naprogramovat postupnost LTS automatov. LTS ma konecny pocet stavov, jeho hrany su ohodnotene vstupom asi takto:
?a LTS prima na vstupe znak a
!a LTS zapisuje na vystup znak a
?* LTS prima zo vstupu lubovolny znak
Pokial bolo na vstupe pismeno, ktore ziadna hrana veduca z daneho stavu neprima (napr. mame b a hrany veduce z tohto stavu su ?a ?A), tak sa pismeno presuva na vystup a LTS zostava v rovnakom stave.
Z kazdeho stavu mohla ist len jedina ! hrana alebo niekolko ? hran (zakazdym s inym pismenom, ak tam bola aj hviezdicka, hrany s pismenom mali prednost).
Subor s popisom LTS vyzeral asi takto :
0 1 ?a
1 0 !A
[prazdny riadok]
[dalsi automat]

Kazdy automat, vstup a vystup bol tvoreny jednym vlaknom, spolu bolo najmenej n+2 vlakien (n pocet automatov), ktore spolu komunikovali cez zdielane fronty. Vzdy vystup z jedneho LTS bol vstupom do nasledujuceho, posledny mal vystup do vystupneho suboru. Program skoncil, ked na vstupe uz nic nebolo a vsetko bolo zapisane.

Neviem ci to niekto z tohto pochopi, samotne zadanie sa vysvetlovalo asi tristvrte hodinu. Pripajam moje riesenie, snad to bude niekomu uzitocne. Nerobila som to cez zdielane fronty, ale cez PipedInputStream a PipedOutputStream, ale uznal mi to.

LTS.txt

Attachments: