Zkouška 25.5.2009

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.
Zabiják

Zkouška 25.5.2009

Příspěvek od Zabiják »

Zkoušel Töpfer, zadání zabralo asi půl hodiny, na práci byly 2 hodiny času.

Zadání: Obchodování na burze
Na vstupu data o požadovaných transakcích, kde jeden záznam obsahuje:
ID makléře (10 znaků)
ID klienta (10 znaků)
ISIN akcie (12 znaků)
název akcie (20 znaků)
typ (1 znak, P jako prodej nebo N jako nákup)
limitní cena (číslo na 2 desetinná místa, v případě prodeje minimální cena, v případě nákupu maximální cena)
počet kusů (longint, počet kusů které je maximálně možno prodat nebo koupit)

Cílem programu je pro každý druh akcií (pro každý ISIN kód) najít cenu, při které se zobchoduje největší počet kusů. ISIN je unikátní kód druhu akcie, stejně tak název je unikátní. Výstupem sada záznamů, které obsahují:
ISIN akce
název akcie
určená cena
počet kusů, které ze za tuto cenu zobchodují

Omezení:
maximálně druhů akcií ... 3 000
maximálně požadavků ... 100 000 000
maximálně makléřů ... 10 000
maximálně klientů ... 10 000 000
cena akcií od 0,01 do 43 000 Kč
dostupná paměť RAM ... 1 MB
dostupná paměť na disku ... neomezeně

Požadavky je možné splnit částečně (někdo chce koupit 10 kusů, ale je k dispozici jen 5, pak se provede obchod na 5 akcií).
Velyger
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 29. 10. 2008 14:49
Typ studia: Informatika Bc.

Re: Zkouška 25.5.2009

Příspěvek od Velyger »

mne to pripada take ze cely cas do nas cpu grafove algoritmy, kdejake zoznamy a stromy a tu to slo len cez subory...
ale nebolo to ak take tazke, hlavne je pochopit o co tam ide. po vysvetleni zadania malo este dost vela ludi otazky
Zombie killer
Obrázek
Zabiják

Re: Zkouška 25.5.2009

Příspěvek od Zabiják »

Řešil jsem takto:

Vstup si nejprve rozkouskuju do souborů podle ISINu (vnějším tříděním). Jednotlivé soubory pak seřadím vzestupně podle ceny (a případně ještě podle typu požadavku N/P). Přitom si ISINy a názvy akcií uložím do paměti (třeba jako pole) a toto pole seřadím vzestupně podle názvu. Pak s každým souborem (v pořadí v jakém mám seznam ISINů) udělám toto:

Budu mít dva čítače, jeden na prodeje, druhý na nákupy. Nejprve si soubor celý jednou projdu a sečtu počty kusů všechny nákupů. Nastavím čítač nákupů na tuto hodnotu. Pak procházím postupně všechny záznamy v souboru (jsou seřazené podle ceny vzestupně) a když najdu prodej, přičtu počet kusů k čítači prodejů, když najdu nákup *odečtu* počet kusů od čítače nákupů. Co je důležité je nejprve počítat prodeje a až pak nákupy. A v každém bodě je podívám na menší z těchto dvou čítačů. To určuje kolik je možné zobchodovat akcií při aktuální ceně. Pro každou cenu (a případně pro každé rozmezí mezi dvěma cenami) se podívám na dosavadní maximální možnost zobchodování akcií a kdyžtak vylepším. Na konci mám výsledek (a ještě si pochopitelně při nalezení lepšího čísla zapamatuji cenu).

Složitost je O(n.log n) kvůli vnějšímu třídění, procházení je pak lineární. Na ústní mi Holan pověděl, že je to v pořádku, ještě se mě zeptal, co jsou virtuální metody a kdy se vytváří ukazatel na tabulku virtuálních metod. Obojí jsem věděl, takže za 1.
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 25.5.2009

Příspěvek od marion »

Mě se na ústní ptal na dynamiku a pak jsem předváděla postup jak co nejlépe uzávorkovat n matic při násobení tak, aby se provedlo co nejméně násobení.
vlastagf
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 26. 5. 2009 14:42
Typ studia: Informatika Bc.

Re: Zkouška 25.5.2009

Příspěvek od vlastagf »

Ta pisemna mi prisla celkem jednoducha, u ustni se me Holan ptal na haldu, na virtualni metody a jejich tabulku v C#.
Drakoii
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 12. 10. 2008 23:47
Typ studia: Informatika Bc.

Re: Zkouška 25.5.2009

Příspěvek od Drakoii »

Na ústní části se mě Topfer ptal na vyhodnocování aritmetických výrazů a na dolní odhad složitosti třídění založeném na porovnávání.
Odpovědět

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