Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Programování / Zkouška LS 2007
Přihlášení:  Heslo:  
Matfiz: Programování/ZkouškaLS2007 ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |

Programování II – Zkouška LS 2007

Obsah


Pisemna cast: napred je hodina na maly priklad z okruhu : spojaky (mergovani, zasobniky, fronty.......), stromy (vypisy, vytvareni, prochazeni, ....), neco malo z dlouhych cisel,... V zasade jde v malych prikladech o praci s dynamickymi strukturami a jejich konkretni pouziti (pascal) – dereferencovani, atp; tedy prakticke programovaci skills.
pak 5 minut pauza a dve hodiny na velky priklad.

Ustni zkouska probiha ( moje tak probehla ) tak ze nejdriv projde maly priklad zepta se na nejasnosti, necha vas abyste vymysleli napravu pripadnych chyb,... Pak prejde k velkemu – diskuse, ....


A nakonec se taze na nektere veci typu : reknete mi neco o : haldach, objektech, dynamickem programovani, ...

25.6. koncerty

dneska jsem to zahlíd na tabuli (pri jine zkousce) předpokládám že je to tohle:
http://forum.matfyz.info/viewtopic.php?t=1885

18.6. lovec autogramů

na grafy :) casem doplnim zadani bud ja nebo nekdo jinej

12.6. burza

Velky priklad: Napsat program pro stanoveni kurzu pro fixingove obchodovani na prazske burze. Zadani bylo strasne dlouhy, podstatny bylo, ze se pracovalo se “spoustou dat” (<=100M zaznamu) a “malem pameti” (1MB na data).
Vstup
soubor pokynů, textový, na každém řádku:
ID klienta: 10 znaků (např. KOMM8674 )
ID makléře: 10 znaků (např. KOMK526400)
ISIN (ident. cenného papíru): 12 znaků (např. CZ0168451265)
Název CP: 20 znaků (např. ČESKÝ TELECOM)
Pokyn: N nebo P (nakup, prodej)(např. N)
Limitní cena: real, (pro nákup maximální, pro prodej minimální) (např. 750)
Počet: longint (např. 10 000)
Výstup
soubor kursů, textový, na každém řádku:
ISIN
Název CP
Kurs (cena za 1 CP)
Počet obchodovaných
Omezení
různých CP <=3000
pokynů <=100 000 000
makléřů <=10 000
klientů <=10 000 000
min. cena 0,01(1 hal)
max. cena 43 000
paměť 1MB
disk rozumně neomezeně
Úkol
Stanovit kurs cenných papírů tak, aby se zobchodovalo co nejvíc CP. Pokud by se obchodoval maximální počet pro nějaký interval kursů, stanoví se kurs na střed intervalu.


Řešení: i pan Töpfer potvrdil ze byla v podstate dve (uvedl jsem obe a udelal sem dobre)

obe reseni zacinala stejne, rozdelit vstupni soubor do souboru jednotlivych cennych papiru, pro kazdy urcit nejlepsi kurz a pak to setridit a ulozit do vystupniho souboru
tohle vymyslel snad kazdy uloha tedy vlastne byla jak najit nejlepsi kurz.
KF (dopiste nekdo prosim zadani na to uz nemam cas)
doplněno, snad to není úplně zmateně Přístup zamítnuttk

4. 6. scrabble

Velký příklad: Nalézt nejlépe obodovaný tah ve scrabble. Vstup:


Smí se použít paměť až několikanásobku velikosti slovníku. Je vhodné zvlášť uvést nějakou inicializaci nezávislou na konkrétním tahu (zřejmě tedy předžvýkání slovníku). Platí běžná scrabblová pravidla.


Stejně jako «čokoláda» je tento příklad prý z minulého roku. — Adam


Řešení: By mělo obsahovat následující elementy: Vybudování stromů (já měl větvící se dle písmen, což je asi nejlepší) ze slovníku, ideálně ve směru čtení slov i po zpátku (tzn. první větvení dle posledního písmene, což mě nenapadlo, přitom, je to podle mě ten hlavní fígl), vybudování hashovací tabulky ze slovníku pro ověřování “bokem” vytvořených slov. A z toho vychází zbytek, tzn. že se vždycky vezme něco, co už na desce je podle toho se projde pár větvení jednoho ze stromů a dále se prochází podle podle slov, která mohu klást na desku, přičemž se průběžně počítají body a ověřují “bokem” vytvořená slova.

28. 5. čokoláda


Zadani velkeho prikladu: Mate ctvercovou cokoladu 10 * 10 s policky o stranach 1. V cokolade je nekolik (<= 1000) orisku a hrozinek kruhoveho tvaru. U kazdeho orisku a hrozinky znate jejich souradnice(realne) a polomer(realny). PROBLEM: rozdelte cokoladu na libovolne velke tri dily, s co nejmensi namahou (na rezani) a to tak, ze rezat muzete jen po hranach jednotlivych dilku a v cokolade nesmi byt vyriznuty otvor. Rezani cokolady stoji 1, rezani pres cast s oriskem 5 a rezani pres hrozinku 1/2 energie na jednu hranu (tzn kdyz pulku hrany zabira orisek a zbytek je cokolada, tak hrana stoji 3 j. energie)... Mate k dispozici 1MB pameti. (Napsal Pepa Moudřík, já to sem jen přesunul.)


Reseni: (aneb ja jsem to delal takhle) Napraed se vhodne ohodnoti hrany podle toho kolik je na nich orisku/hrozinek. ( treba pomoci delky tetivy ) Tim se problem prevede na grafovou ulohu, kterou lze resit ruznymy zpusoby. Delal jsem to pomoci F-W a vhodnym prozkoumanim minimalnich cest z okraje na okraj ( namalujte si to na papir a nemel by to byt velky problem ) – 1 rez – a pak vsech cest z (okraje + uzly prvni cesty) na (okraje + uzly prvni cesty) – minimum ze souctu delek je reseni. Bohuzel vsak tenhle algotritmus muze minout optimalni reseni pri zakerne zvolenem rozlozeni orisku a hrozinek. Holan to ale stejne celkem uznal ( prodiskutovali jsme taky nejake chyby a jejich napravu, ... ) a celkove se mi zdal na zkousce velmi prijemny...


30. 4. studentské ankety (ukázková úloha na přednášce)

Zadání

Vstup

Výstup


Střední kvadratická odchylka: Průměr čtverců rozdílů hodnot a střední hodnoty.

Omezení


Řešení


Úvaha: soubory se nám nechce číst moc často, ale asi to bude třeba


Zřejmě bude třeba třídit podle klíčů (Učitel, Předmět) (tzn. jeden průchod, dva klíče).


Postřeh: Σ (xi – R)2 / N = Σ (xi2 – 2xiR – R2) / N = (Σ xi2 – RΣ2xiR – NR2)/N


U – délka souboru Učitelé
L – délka souboru Lístky
UP – počet platných kombinací (Učitel, Předmět)


Návrh algoritmu:

  1. Setřídit Lístky podle (Učitel, Předmět).
  2. Setřídit Katedry podle (Učitel).
  3. Čtu souběžně oba soubory (sekvenčně), dokud stejný (Učitel, Předmět) přičítám sumy xi, xi2, jinak vypíšu. Zapisuju jeden soubor s Učiteli, druhý s Učiteli a Katedrami.
  4. Setřídím soubor s Učiteli a Katedrami podle (Katedra), zapíšu bez pole Katedra.

Tip: Neměl jsem foťák, ale bylo nám doporučeno, abychom si kreslili obrázky (aka data-flow diagramy) jako Holan na tabuli – data a akce pospojované šipečkami.

Části vypracování řešení úlohy


Do Upřesnění nebo postřehů:


Do Diskuse:

Do Shrnutí:

26. 1. (info o zkoušce na přednášce)



Jako příklad úlohy uváděl problém s letištěmi, který snad je/bude na jeho stránkách, ovšem s tím, že na zkoušku je tenhle příklad naddimenzovaný.


 
Soubory [Skrýt soubory (formulář)]
Na stránce je jeden komentář. [Zobrazit komentáře (formulář)]