6.6. 2016 - Holan - Labyrint

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

6.6. 2016 - Holan - Labyrint

Příspěvek od hlupaco »

Theseus, Minotaur a Ariadna v labyrintu, plus vtipné lore proč se snaží každý vyhnout každému :-)

V labyrintu je maximálně 100 místností, na vstupu jsou v podstatě hrany (seznam chodeb místnost - místnost), počáteční místnost a koncová místnost pro každou postavu zvlášť.

Každá postava projde za 1 minutu 1 chodbu, nebo se může rozhodnout minutu čekat.

To, že se nechtějí potkat zahrnuje, že se nechtěji ani vidět, tj nesmí se nacházet v jednu minutu ve dvou sousedních místnostech.

Úkol je zkrátka jen vrátit číslo jako nejnižší počet minut za který se mohou každý dostat do cíle se zachováním výše uvedených pravidel.

Paměť 512 kB.

Na ústní už asi nepůjdu protože jsem nedal zápočet ^^ Ale kdybych se tam ještě stavil, připíšu nějaké dojmy odtud.

Řešil jsem to BFS - nejkratší cesta, pak lokalizace prvního konfliktu co nastane, jeho vyřešení, nové BFS odtud a opět řešení prvního konfliktu pokud nějaký je, plus každé řešení konfliktu vyvolá až 3 faktoriál nových BFS větví, protože vždy zkusím dávat přednost postavám v jiném pořadí abych je vyzkoušel všechny. Zde se mi to rozdělí doufám nanejvýš 6krát (kromě případu kdy dva půjdou za sebou a narazí na třetího později, který je potřeba zvlášť ošetřit), a BFS na neohodnocených hranách je O(n) -> cca 600 kroků je pořád úplně cajk, pointa je že bude dost narůstat konstanta s tím ověřováním kdo kdy blokuje jakou místnost :-)

Na druhou stranu se každá postava s každou dostanou do konfliktu nanejvýš jednou, protože všechny chodby jsou obousměrné a projde nimi každý.

Vim že to řešení je silně krkolomný, pokud ste někdo udělal něco hezčího dejte vědět.
karab
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 7. 6. 2016 10:27
Typ studia: Informatika Bc.

Re: 6.6. 2016 - Holan - Labyrint

Příspěvek od karab »

Opakovalo se zadání a je zde i řešení:
http://forum.matfyz.info/viewtopic.php?f=247&t=6881

Jen paměť byla menší a jde to vymyslet i bez fronty.
hlupaco
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 1. 6. 2016 21:58
Typ studia: Informatika Bc.

Re: 6.6. 2016 - Holan - Labyrint

Příspěvek od hlupaco »

Mám po ústním.
Algoritmus zase chtěl uplně snadně stavovym grafem, nelíbilo se mu že sem to trochu zamotal a našel mi protipříklad co mi ten muj postup rozbil :-(
Očividně na dovolený paměti tak přísně nebazíruje jako spíš aby ten alg byl správně, i na její úkor. Koneckonců ten graf byl maličkej.

Z teorie jsem dostal AVL stromy.
Vůbec ho nezajímaly důkazy toho kde je kolik minimálně a maximálně prvků.

Co chtěl byl invariant a základní myšlenka (ani se neptal jak z toho vyplývá např. že je hloubka logaritmická) a pak mi pořád přidával a ubíral prvky a nechal mě provádět algoritmus, tj určitě chce všechny operace - nechal mě udělat rotaci, i dvojitou, propagování změn, odstranění kořene, ...
Snadný, opravil jsem si tim známku z 3 na 2, žádná další otázka.
Má rád když se to hezky vysvětluje, ale to je asi všude stejný :-)

BTW: Pozor, zkouší prej i z technickejch věcí co nikdy nevysvětloval nebo uplně okrajově jako co je to statická X abstraktní X sealed třída... Ale tu informaci nemám od něj, jen šeptanda.
Odpovědět

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