Zkouška 28.5.2007
Zkouška 28.5.2007
"Malou úlohu" na dynamické datové struktury dostal každej jinou, typicky něco na LSS a binární stromy - seřadit, zrušit, sečíst dlouhá čísla, vyhodnotit výraz atd...
Velká úloha:
Máme tabulku čokolády 10x10 políček. Délka strany políčka je 1. V čokoládě jsou oříšky a rozinky (kulaté, na vstupu jsou jejich souřadnice a poloměry), jejich počet je <= 1000. Máme napsat program, který určí, jak nesnadněji rozřezat čokoládu na 3 díly. Nejsnadněji s míní s co nejmenší prací, přičemž rozříznuzí čokolády o délce 1 stojí práci 1, ořechu o délce 1 stojí práce 5 a rozinky o délce 1 stojí práci 1/2. Každá hrana stojí práci v poměru kolik je tam čokolády, rozinek a ořechů. Řezat se smí jen po hranách, ale libovolně klikatit atd. Čokoláda má konstantní výšku, řezání ořechu středem i u kraje stojí stejně práce (nezáleží na výšce ořechu), prostě je to všechno jen 2D. Řezáním čokolády nesmí v žádném kusu vzniknout díra. K dispozici je paměť maximálně 1MB. Dále nám dali k dispozici funkci DélkaTětivy(xstřed,ystřed,R,y), která vrátí délku tětivy ořechu nebo rozinky o poloměru R, která protíná hranu na souřadnici y. Výstupem programu mají být hrany, které se mají řezat a cena (práce).
Velká úloha:
Máme tabulku čokolády 10x10 políček. Délka strany políčka je 1. V čokoládě jsou oříšky a rozinky (kulaté, na vstupu jsou jejich souřadnice a poloměry), jejich počet je <= 1000. Máme napsat program, který určí, jak nesnadněji rozřezat čokoládu na 3 díly. Nejsnadněji s míní s co nejmenší prací, přičemž rozříznuzí čokolády o délce 1 stojí práci 1, ořechu o délce 1 stojí práce 5 a rozinky o délce 1 stojí práci 1/2. Každá hrana stojí práci v poměru kolik je tam čokolády, rozinek a ořechů. Řezat se smí jen po hranách, ale libovolně klikatit atd. Čokoláda má konstantní výšku, řezání ořechu středem i u kraje stojí stejně práce (nezáleží na výšce ořechu), prostě je to všechno jen 2D. Řezáním čokolády nesmí v žádném kusu vzniknout díra. K dispozici je paměť maximálně 1MB. Dále nám dali k dispozici funkci DélkaTětivy(xstřed,ystřed,R,y), která vrátí délku tětivy ořechu nebo rozinky o poloměru R, která protíná hranu na souřadnici y. Výstupem programu mají být hrany, které se mají řezat a cena (práce).
Prý může být ještě hůř, někdo tam měl dokonce násobení čísel ve spojáku nebo tak. Je pravda, že tam zase skoro odpadá problém se zápornými.
Já teda osobně měl klasiku - průnik dvou binárních stromů - a taky mi to zabralo skoro celou hodinu.
Jinak ta velká úloha vypadá těžká, ale zase tak složité řešení nemá. Po konzultaci s Topferem (trochu mi vypíchl věci, které se daly ušetřit) by to mělo být asi takhle:
Nejprve uděláme ohodnocený graf, ideálně přímo v matici (to je docela dobrá reprezentace).
Pak si uděláme pomocí Floyd-Warshalla nebo Dijkstry tabulku všech vzájemných vzdáleností v tom grafu.
Máme tři možnosti, jak to může vypadat:
a) Disjunktní hrany - čili najdeme dvě nejmenší vzdálenosti mezi body na okraji
b) Jeden společný bod - pro každý vnitřní bod najdeme tři nejbližší okrajové body a hledáme minimum součtu
c) Dva společné body (oko s cestami na okraj) - pro všechny dvojice bodů spočítáme minimum součtu nejbližších vzdáleností těch bodů od okraje + dvou nejkratších cest mezi nimi (nejkratší máme v tabulce, druhou nejkratší ještě nějak musíme ošetřit)
Výsledek je minimum z a), b), c).
Neměl jsem pořádně domyšlené to c), takže mi to vycházelo O(n^8), jde to i na O(n^6) - jenom se musí dovymyslet ta druhá nejkratší cesta. Jako n beru 10 - čili šířku tabulky.
Já teda osobně měl klasiku - průnik dvou binárních stromů - a taky mi to zabralo skoro celou hodinu.
Jinak ta velká úloha vypadá těžká, ale zase tak složité řešení nemá. Po konzultaci s Topferem (trochu mi vypíchl věci, které se daly ušetřit) by to mělo být asi takhle:
Nejprve uděláme ohodnocený graf, ideálně přímo v matici (to je docela dobrá reprezentace).
Pak si uděláme pomocí Floyd-Warshalla nebo Dijkstry tabulku všech vzájemných vzdáleností v tom grafu.
Máme tři možnosti, jak to může vypadat:
a) Disjunktní hrany - čili najdeme dvě nejmenší vzdálenosti mezi body na okraji
b) Jeden společný bod - pro každý vnitřní bod najdeme tři nejbližší okrajové body a hledáme minimum součtu
c) Dva společné body (oko s cestami na okraj) - pro všechny dvojice bodů spočítáme minimum součtu nejbližších vzdáleností těch bodů od okraje + dvou nejkratších cest mezi nimi (nejkratší máme v tabulce, druhou nejkratší ještě nějak musíme ošetřit)
Výsledek je minimum z a), b), c).
Neměl jsem pořádně domyšlené to c), takže mi to vycházelo O(n^8), jde to i na O(n^6) - jenom se musí dovymyslet ta druhá nejkratší cesta. Jako n beru 10 - čili šířku tabulky.
jako malý příklad jsem měl stvořit ze vstupní posloupnosti čísel BVS mimo 3 největších čísel
- celkem jednoduché jen jsem se lehce zamotal do uchovávání těch 3 hodnot
velký příklad jsem řešil podobně jak je popsáno v příspěvku o jedno výš, pospal jsem 5 A4, problém byl ale v tom, že mi byl ukázán protipříklad
z teorie jsem dostal vnitřní třídení
- celkem jednoduché jen jsem se lehce zamotal do uchovávání těch 3 hodnot
velký příklad jsem řešil podobně jak je popsáno v příspěvku o jedno výš, pospal jsem 5 A4, problém byl ale v tom, že mi byl ukázán protipříklad
z teorie jsem dostal vnitřní třídení
To sem mel taky
Tady je docela dobry napad pocitat si zvlast kladne a zvlast zaporne a az nakonec to odecist (odecist mensi od vetsiho a znamenko doplnit).Wolda píše:Jo, to moje "mala" uloha byla velmi opravdu bezva, mate soubor, ve kterem jsou cisla (obecne dlouha cisla), ktera mohou byt i zaporna, a ta se maji vsechna secist. Paradni uloha, akorat na 1h docela zabijejici, rekl bych.
Pri prubeznem odecitani by bylo asi docela blbe resit "zaporne + zaporne", "zaporne + kladne s prelezem pres nulu" a tak..
-
- Matfyz(ák|ačka) level II
- Příspěvky: 69
- Registrován: 4. 10. 2008 11:05
- Typ studia: Informatika Mgr.
- Login do SIS: 36138549
- Kontaktovat uživatele:
Re: Zkouška 28.5.2007
Z toho zadání mi není úplně jasné, jaké jsou přípustné řezy. Je to myšleno na 3 díly o stejném obsahu? Protože pokud ne, tak mi z toho vychází, že můžu odříznout třeba 2 čtverečky, čímž mi vzniknou 3 díly. To sice nic nemění na faktu, že tam můžu najít delší cestu u které se míň nadělám, ale daly by se tam potom možná vymýšlet nějaké heuristiky.