Zkouška 13.6. Auto v mřížce

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.
Pzkw

Zkouška 13.6. Auto v mřížce

Příspěvek od Pzkw »

Zadání identické jako viewtopic.php?f=247&t=12189, až na to, že cíl bylo jen jedno políčko (bylo povoleno jej dosáhnout v jakékoli rychlosti). Vstup nebyl popsaný tak detailně a tak se ani nevyžadoval nějaký algoritmus na načítání.

Napadlo mě BFS, v některých případech mi nevycházela paměť - 10 MB mohlo v nejhorším případě dojít tak na 6 hladině BFS stromu. Napadlo mě taky uložit nejmenší počet tahů pro každý stav tj. kombinaci políčka a rychlosti a dělat nějaké dynamické programování, ale zdálo se mi, že jich je moc - počítal jsem až 100x100 políček x přibližně 100x100 rozumných rychlostí (tzn. mám políčko, ze kterého jsem se mohl tou rychlostí dostat do toho stavu a v dalším kroku se můžu vyhnout překročení hranice hracího pole) ve středu, méně směrem k okrajům. Holan říkal, že maximální rozumná rychlost je i ve středu asi max. +-10 pro každou souřadnici (i když nepřestřelím hned v následujícím tahu, přestřelím v těch dalších), kdybych počítal s tím, tak bych se do paměti vešel.

Ústní zkouška s Holanem: hashování (chybně jsem ho použil na "zlepšení" algoritmu).
Odpovědět

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