Skuska 8. 6. 2015 (Lode)

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

Skuska 8. 6. 2015 (Lode)

Příspěvek od Jankus »

Dnes sme mali na skuske ulohu s lodami.
Na vstupe je subor, v ktorom su riadky obsahujuce
- typ lode (nazov, rozmery, pocet lodi daneho typu)
- potopene lode (nazov typu, umiestnenie, natocenie)
- zasahy do vody (umiestnenie)
- rozmer hracieho planu - moze to byt obdlznik

obmedzenia:
max. 20 typov lodi a max. 20 lodi (takze extremne 1 lod od kazdeho typu ci 20 lodi rovnakeho typu)
max rozmery planu 30 x 30
max rozmery lode myslim 10 x 10 (?)
pamat rozumne neobmedzena, disk nie je potreba
inac cela lod sa potopi na 1 zasah, lode su suvisle (policka susediace cez hranu), ale 2 rozne lode sa mozu dotykat hranami

vystup:
zoznam policok, na ktorych urcite lod je, a zoznam, na ktorych urcite nie je.

najprv si je treba asi zistit, ake kolko a akych lodi ostava.
prechadzanie vsetkych moznosti by trvalo asi dlho (pre 1 lod je prinajhorsom 30 x 30 x 4 [natocenie] = 3600 moznosti rozmiestnenia, teda celkom asi 3600^20 mi vyslo?), hladal som iba trivialne riesenia: pre kazdu lod som si presiel plan (iba pouzitelne policka (nie zasiahnute a potopene lode) a zistoval, kde moze byt (tu to chce este nejaku heuristiku vraj, akoze ked je lod 1 x 5 policok. a v riadku je prekazka, tak nema zmysel skumat, ci sa tam vojde 5x vzdy cez tu istu prekazku inym polickom) a zapamatal som si celkovy pocet umiestneni. ak pocet umiestneni na nejakom policku je rovnaky ako celkovy -> na tomto policku musi byt vzdy, takze ho mozme pridat to zoznamu. rovnako si zapamatam policka, kde dana lod nie je a ak si to pre nejake policko pamatam u vsetkych lodi, mozem ho pridat do druheho zoznamu.
pokus o najdenie dalsich (o trochu menej trivialnych) rieseni som myslel ze by mohol byt taky: vytvorit si dve nejake funkcie, kde by sa jedna snazila pre ostatne policka (pouzitelne, ale nie v zozname) rozmiestnovat lode a umiestnit nejaku lod na dane policko a ak sa jej to nepodari, vyhlasi ho za nutne prazdne a druha naopak na dane policko nic neumiestnit a ak sa jej to nepodari, vyhlasi ho za nutne obsadene. asi to chce nejaky spolahlivy algoritmus pre nich, nejaku heuristiku. ale dolezite je tie lode rozmiestnovat oba raz (alebo par krat) pre kazde policko - nebacktrackovat. vsetky data som ukladal v dvojrozmernych poliach velkosti planu.
rozhodne to nenajde vsetky riesenia, casto iba mensinu, ale nemalo by to mat problem s rychlostou ci s pamatou (ma to tusim kvadraticku zlozitost pocet lodi x pocet policok ?)

Holanovi sa to pacilo na 1-, potom som dostal iba countsort, kde som nepovedal, ze je linearny nielen v zavislosti na pocte triedenych cisel, ale aj na rozsahu a nevedel som kolko je 2^32, takze nakoniec mi dal 2 :D
Odpovědět

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