Zkouška Pergel/Holan 26.6.

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouška Pergel/Holan 26.6.

Re: Zkouška Pergel/Holan 26.6.

od kamen » 28. 6. 2017 05:14

Zkoušku jsem dělal u Holana, docela podrobně chtěl vysvětlit, jak jsem postupoval. Já jsem si seřadil hrany podle bezpečnosti a binárně vyhledal takovou bezpečnost, při které když použiju jen bezpečnější hrany bude start i cíl v různých komponentách souvislosti. Sice je to méně efektivní než nahoře uvedený algoritmus, ale říkal, že se mu to líbí a dal mi za 2. Pak chtěl jen vysvětlit jak funguje Dijkstra a to bylo vše.

Zkouška Pergel/Holan 26.6.

od M_vys » 27. 6. 2017 17:50

Myslím, že to byla nová úloha.

Zadání:

Ve městě jsou ulice ohodnocené délkou a nebezpečností. Úkolem je najít co nejbezpěčnější cestu mezi dvěma místy ve městě. Nebezpečnost cesty závisí pouze na nebezpečnosti nejnebezpečnější ulice po cestě a pokud je víc stejně nebezpečných cest, chceme tu nejkratší. Je zaručeno, že aspoň jedna cesta existuje.

Vstup:

seznam ulic: odkud, kam, bezpečnost (ve tvaru 2^31 - # prepadeni), délka
start a cíl cesty

křižovatek <= 1000
pamět: 1GB


Výstup:
nebezpečnost nejbezpečnější cesty výpis ulic kterýma prochází zase odkud, kam


Byla jsem u Pergela, mojí písemku předtím očividně nečetl, chtěl po mě abych stručně shrnula svoje řešení.
Řešila jsem to tak, že jsem si seřadila hrany podle nebezpečnosti a postupně odebírala ty nejhorší (když jich bylo víc stejně nebezpečných odebrala jsem všechny) a zkoumala, jestli start a cíl jsou v té samé komponentě. Potom už nebyly, přidala jsem poslední potřebný našla nejkratší cestu pomocí Dijkstry. Vůbec se neptal na podrobnosti, reprezentaci čehokoliv nebo jak bych zkoumala ty komponenty, případně co složitost nebo paměť. Jen po mě chtěl ukázat jednu větu na papíře a řekl to vypadá věrohodně.
Z ústní mi dal dynamické programování a ptal se jaký znám použití, uzávorkování násobení matic je prý jeho nejoblíbenější.

Osobně jsem z toho měla smíšené pocity, Pergel vypadal, že to chce mít hlavně rychle za sebou (to jsem byli dva), taky to vypadalo že by se v tom i vrtal, ale říkal, že tohle řešení ještě neviděl, takže mi věří, že to tam všechno je. Ani u ústní se v tom moc nevrtal, potom řekl že jsem mu všechno řekla, algoritumus byl taky v pořádku, ale že na jedničku se mu to nezdá a dal mi dvojku. Já byla ráda že to mám za sebou, ale příde mi, že je to hodně o jeho náladě a pocitu.

Nahoru