Kostičky 23.6. 2020 - 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.
toby22
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 14. 1. 2020 10:03
Typ studia: Informatika Bc.

Kostičky 23.6. 2020 - Holan/Pergel

Příspěvek od toby22 »

Krychličky
Prostorový útvar je složený z jednotkových krychliček a chceme spočítat, kolika různými způsoby ho lze rozdělit na dvě souvislé části.
Přitom:
 krychličky, ze kterých se útvar skládá, na sebe přiléhají stěnami
 útvar není větší než krychle rozměru 3x3x3 krychličky
 obě části musí být složeny z celých jednotkových krychliček
 souvislost je definovaná takto:
◦ jednotková krychlička je souvislá část
◦ spojením dvou disjunktních souvislých částí tak, že se
přinejmenším jedna jednotková krychlička z jedné části a
jedna jednotková krychlička z druhé části spojí některými
svými stěnami, vznikne také souvislá část
 můžeme předpokládat, že jednotkové krychličky jsou očíslovány, takže řešení, které se liší jen pootočením považujeme za různá řešení
 části naopak nebudou nijak pojmenované, takže je jedno, která část je první a která druhá
 dvě části, na které původní útvar rozdělíme, nemusí být oddělitelné, tedy například rozdělení, při kterém je jedna část pouze jednotkovou krychličkou ve středu krychle 3x3x3 a druhá část je zbytek této krychle, je přijatelné a budeme ho započítávat
Zadání
Navrhněte program, který zjistí, kolika způsoby lze zadaný prostorový útvar rozdělit na dvě souvislé části.
Vstup
Vstupem programu je seznam krychliček, ze kterých se útvar skládá,
každá krychlička je zadaná pomocí souřadnic svého levého horního
roku, například:
Výstup
0 00 100 010 110
Výstupem je číslo udávající počet možností, například:
6
(Vysvětlení: útvar popsaný vstupem sestává ze čtyř krychliček uspořádaných do čtverce 2x2, na dvě části ho můžeme rozdělit buď tak, že jedna část bude jedna krychlička a druhá část tři krychličky (4 možnosti) nebo tak, že jedna část budou dvě krychličky vedle sebe (2 možnosti).)
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í.
Počty velikosti
 paměť 500MB
Odpovědět

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