Zkouška 6.6.2011

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.
Drozi
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 25. 1. 2010 11:59
Typ studia: Informatika Bc.

Zkouška 6.6.2011

Příspěvek od Drozi »

Zadání a řešení (aspoň doufám! :)) podobné tomuto:

http://forum.matfyz.info/viewtopic.php?f=247&t=6839

Akorát formulované hudebně (úloha Pavarotti) :D

Na ústní jdu až zítra, takže na jaké VMT a b-stromy se ptají, musí někdo doplnit.
Premun
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 6. 6. 2011 22:52
Typ studia: Informatika Mgr.

Re: Zkouška 6.6.2011

Příspěvek od Premun »

Tak ja sem napisu plny zneni, treba to nekoho zachrani :)

Jmenovalo se to teda nejspis Pavarotti a za ukol bylo zjistit jestli a kolikrat je mozne sestrihat dlouhy koncert tak, aby po slepeni dal vasi kratsi pisnicku. (useky se nedaly prehazovat)

Vstup:
1. radek obsahoval pisnicku ve tvaru:
[slabika]-[ton]-[delka] [slabika]-[ton]-[delka] [slabika]-[ton]-[delka] ...

2. radek byl koncert ve stejnem formatu


Vystup:
pocet moznosti sestrihani koncertu, aby poslepovane kousky daly pisnicku


Omezeni:
pisnicka - max 100 000 trojic [slabika]-[ton]-[delka]
program koncertu - hodne dlouhy
vystupni hodnota - vejde se do 2^63
pamet - 2 MB (HDD neomezene)
slabika - 3 a min znaku
delka - 4B int, 1 az 240 000
ton - jeden nebo dva znaky (CDEFG.., C# D#..., Cb..., c1 d1..., c2 d2... tyhle kombinace)
celkem 86 tonu


A pouzit slo jen trojici, ktera presne odpovida te v pisnicce (takze presne stejna slabika, ton, delka).

Jinak problem je asi algoritmicky stejnej jako ten, co posilal kolega vejs ^^

Tak hodne stesti :)
Ant

Re: Zkouška 6.6.2011

Příspěvek od Ant »

Na ústní jem byla v den zkoušky, pravý sloupeček byl Topfer. Šla jsem úplně poslední, ptal se na vnější třídění a když mi tu otázku vymýšlel, tak řekl, cituji: "Já jsem se dneska ptal snad už úplně na všechno, na co já se vás zeptám?"
V písemce jsem si špatně spočítala kolik bytů zabere jeden prvek a nevešla jsem se do zadaných 2MB protože jsem použila spoják a ne pole. Jinak jsem ji měla dobře. Vnější třídění jsem uměla, ale nějak mi nešlo se pořádně jasně vyjádřit, takže za dva.
Drozi
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 25. 1. 2010 11:59
Typ studia: Informatika Bc.

Re: Zkouška 6.6.2011

Příspěvek od Drozi »

Ještě bych u toho doplnil jednu úvahu, která mi prošla a řekl bych, že je docela dobrá (pokud sem teda tradičně neobjevil Ameriku :D):

Když si do pole načtete první řádek...tak to je vlastně posloupnost znaků určité abecedy. A všechny trojice sou pak znaky téhle abecedy. Úvaha je taková, že koncert = hodně hodně velká množina různých znaků a naše písnička tvoří jenom malinkou podmnožinu. Když bude mít 100 000 znaků a koncert řádově moc, tak s docela "dobrou" pravděpodobností se nám stane, že tabulku velikosti 100 000 procházíme zbytečně, protože ten znak vůbec nepotřebujeme.
Takže by nebylo od věci si pro každý znak nejdřív nějak "dostatečně rychle" otestovat, jestli ho vůbec použijeme a vyhnout se tak procházení polem.
Já sem zvolil Dictionary (o kterym si myslim, že je to "hashovaná tabulka"), takže otestovat, jestli tam nějaký znak je máme skoro v konstantním čase.
Výsledná časová složitost v nejhorčim případě sice zůstane stejná, ale když byste si to třeba zkusili naimplementovat, tak zrychlení tam je opravdu velký.
Sice tim slovníkem asi přetečete paměť, ale mega paměti si koupíte. Hodinu života ne :).

Vše samozřejmě bez záruky :D
Odpovědět

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