Zkouška 28.5.2007

Návštěvník

Zkouška 28.5.2007

Příspěvek od Návštěvník »

"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).
Uživatelský avatar
nardew
Matfyz(ák|ačka) level II
Příspěvky: 59
Registrován: 2. 11. 2006 10:15
Typ studia: Informatika Bc.
Bydliště: Otava - Jizni Mesto

Příspěvek od nardew »

ja som mal ako mini program spravit vypisanie stromu pomocou priechodu do sirky.. nezabudnite ze frontu musite odalokuvavat, ako sa to stalo mne..
Wolda
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 25. 10. 2006 22:27
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od Wolda »

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.
--
Wolda
Návštěvník

Příspěvek od Návštěvník »

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.
archon
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 10. 1. 2007 12:33

Příspěvek od archon »

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í
Invasion

To sem mel taky

Příspěvek od Invasion »

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.
Tady je docela dobry napad pocitat si zvlast kladne a zvlast zaporne a az nakonec to odecist (odecist mensi od vetsiho a znamenko doplnit).
Pri prubeznem odecitani by bylo asi docela blbe resit "zaporne + zaporne", "zaporne + kladne s prelezem pres nulu" a tak..
dmt
Matfyz(ák|ačka) level I
Příspěvky: 29
Registrován: 7. 5. 2006 21:52
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od dmt »

ano ale ono je to aj tak problem stihnut, dokonca by som povedal ze je to nemozne. ja som mal tu istu ulohu a nestihol som ani polovicu. ke som si to potom cvicne napisal doma tak to vyslo na viac ako 150 riadkov...
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouška 28.5.2007

Příspěvek od marion »

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.
Odpovědět

Zpět na „2006“