skuska 27.6.2011

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.
squo314
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 8. 6. 2011 15:01
Typ studia: Informatika Bc.

skuska 27.6.2011

Příspěvek od squo314 »

zadanie:
mame krizovatku(=sachovnicu) s autami 8x8. Je zaplnena autami. Na kazdom policku je bud auto, ktore sa pohybuje dolava, alebo auto, ktore hybe hore. Alebe je policko prazdne.
Na kazdom policku moze byt maximalne jedno auto. Kazdu minutu sa mozu auta pohnut o jedno policko. Ulohou je napisat algorutmus, ktory vypise, ze za kolko minut sa dana krizovatka vyprazdni pri optimalnom pohybe aut.
(Urcujeme teda, v ktorej minute sa ktore auta maju pohnut a zistujeme pocet minut).

ukazka najlepsieho tahu na krizovatke 3x3.
Predstavme si pociatocnu poziciu:
0L0
0UL
000

// 0 = prazdne policko, L->left- auto, ktore sa hybe dolava, U->up
po prvej minute dostaneme:
LU0
0L0
000

teda tato krizovatka sa da vyprazdnit za 3 minuty.

obmedzenie:
pocet aut <= 20
pamat 2.8 MB
-------
riesenie: moje riesenie sa topferovi na zaciatku nelibilo, lebo mi hadzal rozne kontrapriklady, ale nakoniec som mu ukazal, ze moj algoritmus vsetky tieto kontrapriklady riesi, takze je fakt dobry. Riesenie sa mu teda nakoniec libilo za jedna :)

samotne riesenie:
cele si to mozem predstavit ako graf, kde vrcholy su dane konfiguracie mapy(rozostavenia aut) a hrany znacia, ze sa z jednej konfiguracie posunutim niektorych aut viem dostat do dalsej konfiguracie.
Cena hrany bola rovna poctu aut, ktore sa pohli. Ako pozorovanie je zaujimave, ze nech sa hybem v tomto grafe hocijak, pokial sa stale aspon jedno auto pohne, dostanem riesenie.(prazdnu mapu=krizovatku=sachovnicu=konfiguraciu). Ja som postupoval takto: najprv som auta, ktore mozu ist prec z krizovatky, odstranil. Potom som prechadzal celu mapu(z horneho laveho policka ju treba prechadzat dole doprava) a pokial na dane policko moze ist jedno auto, tak ho tam presuniem. Pokial na dane policko mozu ist dve auta(tento stav nazyvam kolizia), tak skusim rekurzivne obe moznosti. Takto vlastne prejdem mapu do hlbky jedna a za najlepsiu konfiguraciu budem povazovat najhodnotnejsiu hranu.
Tod vse :)

na druhu cast so dostal dokaz zlozitosti porovnavacich triediacich algoritmov, ze su v omega n log n...
to som nevedel, tak som dostal nahradu vyhodnoceni infixoveho vyrazu...

nakoniec za dva :) Dojmy - bola to pohodova skuska, len trebalo fakt svoj program vediet obhajit :)
Viki.n
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 20. 5. 2016 15:13
Typ studia: Informatika Bc.

Re: skuska 27.6.2011

Příspěvek od Viki.n »

Ahoj, není na tento algoritmus například toto protipříklad?
P0000
0U000
0U000
Podle mě ti to napřed nechá popojet nahoru obě U auta ikdyž evidentně optimální je pustit v 1. tahu P-auto
mykem
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 13. 2. 2011 18:52
Typ studia: Informatika Ph.D.

Re: skuska 27.6.2011

Příspěvek od mykem »

Ahoj, není, v zadání se píše jen o L-autech a U-autech :)

Ale ani

Kód: Vybrat vše

00L00
0U000
0U000
by protipříkladem nejspíš nebylo, když se v řešení píše, že se při kolizi vyzkouší rekurzivně obě možnosti.
Odpovědět

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