Zkouška 28.06.2021 - Autíčka - Holan/Pergel

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.
neznamymatfyzak
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 28. 6. 2021 20:50
Typ studia: Informatika Bc.

Zkouška 28.06.2021 - Autíčka - Holan/Pergel

Příspěvek od neznamymatfyzak »

Originální pdf zadání zde
210628_zk_auticka.pdf
(73.04 KiB) Staženo 359 x
Pro ty, co nechtějí stahovat, následuje přepis zadání:

Písemná část
1 úloha
Po zodpovězení všech otázek k zadání jsme měli 2 hodiny čistého času na řešení

Autíčka
Autíčka se pohybují v krocích po celočíselných souřadnicích (čtverečkovaný papír). Cílem je dojet ze startu do cíle na co nejmenší počet kroků.
Rychlost znamená vektor – rozdíl mezi minulou a aktuální polohou.Na začátku má autíčko rychlost (0,0).
Krok spočívá v tom, že se autíčko posune o rychlost, ale může k níve směru X i ve směru Y přičíst nebo od ní odečíst jedničku, tj. přesune se na políčko v jedničkovém okolí políčka, na které by ho zanesla dosavadní rychlost. Tím bude určena rychlost pro příští krok.
Autíčko se pohybuje po průsečících čtverečkové sítě, některé hranyčtverečků mohou tvořit překážky. Překážka má vždy podobu hrany jednoho čtverečku. Autíčko při pohybu nesmí projet překážkou.
Cílová páska je úsečka spojující dva celočíselné body (průsečíky). Projetí cílové pásky autíčkem je cílem závodu.
Vstupní data jsou v textovém souboru, přičemž první znak na řádce vždy určuje, jakou informaci řádka obsahuje:
S start: x (int) a y (int)
C cílová páska: x1 (int), y1 (int), x2 (int), y2 (int),
P překážka: x1 (int), y1 (int), x2 (int), y2 (int)

Zadání
Navrhněte program, který ze zadaných vstupních dat spočte nejmenší počet kroků potřebných k tomu, aby autíčko projelo cílovou páskou.
Počty a omezení:
rozměry hrací plochy: <= 100×100
maximální rychlost autíčka: 10 v každé ose v každém směru.
paměť = 10MB, v případě nouze bez omezení,
čas = přiměřeně (sekundy až minuty).
V odpovědi popište
1) postřehy
2) zdůvodněnou volbu algoritmu
3) representaci dat
4) dekompozici programu
5) diskusi,
v případě potřeby i 0) upřesnění zadání.

Řešení, které mě napadlo:
BFS

Ústní část
Témata, na která se ptal Pergel: halda a její definice, vnější třídění, diskrétní simulace, dynamické programování, virtuální metody
(u diskrétní simulace a dynamického programování chtěl slyšet co to zhruba je a následně to i předvést na nějakém příkladu - např. převod Dijkstrova algoritmu na diskrétní simulaci, násobení matic)
Témate, na která se ptal Holan: tabulka virtuálních metod, co je to dynamické programování + příklad, hešování, unit testy, vnější třídění, halda, generické třídy
Odpovědět

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