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 |
Toto je stará verze stránky Programování/ZkouškaLS2007 z 2007-06-02 11:14:12..

Programování II – Zkouška LS 2007


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, ...

28. 5.


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. (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í:


 
Na stránce nejsou žádné soubory. [Zobrazit soubory (formulář)]
Na stránce je jeden komentář. [Zobrazit komentáře (formulář)]