zkouska 12. 9.

Seizekatze
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 14. 2. 2006 14:22
Typ studia: Informatika Bc.
Bydliště: česká republika

zkouska 12. 9.

Příspěvek od Seizekatze »

Tak tentokráte to bylo až přiliš jednoduché. Postup byl stejný jako minule. Tedy rozdal malý příklady. většina lidí měla něco s lineárními spojáky. Konkrétně já měl nedestruktivní průnik dvou spojových sezanamů. Jinak tam byli klasické příklady. Jeden co vím tak tam byl navíc. Měla se udělat ekvivalence mezi dvěma BVS. Ekvivalence znamenala, že mají stejné prvky na hladinách.

Velký přiklad:
Je výstava hráček a kupují se slosovatelné lístky. Na konci se pozvou děti, které vyhráli na recepci. A tam je pro N dětí přípraveno N navzájem různých dárků. (nepodstatně říkal, to jsou ty hračky, co byli na výstavě) A každé dítě své mamce řekne právě jednu hračku kterou chce ( více dětí může chtít jednu hračku, ale jedno dítě nemůže chtít více hraček ).
Ovšem hračky už jsou na počátku nějak rozděleny a tak se maminky dohodnou, že si děti hračky mezi sebou vyměnit. Ale dítě, nepřistoupý na výměnu pokud nakonci výměn nedostane tu hračku, kterou chce. Nakonci výměn, no tak výměna se provede třeba tak, že maminky odeberou hračky svým dětem a nějak si je prohází ( není podstatné jak ) a pak je vrátí dětem, a přitom dítě dostane hračku kterou chce nebo hračku kterou mělo.
My jsme měli naprogramovat program, který určí maximální možné uspokojení dětí. A vypíše děti, který si vyměnili své hračky.
Seizekatze
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 14. 2. 2006 14:22
Typ studia: Informatika Bc.
Bydliště: česká republika

rešeni

Příspěvek od Seizekatze »

Řešení velké úlohy. Já měl dvě pole. Jedno bylo pole dětí přímo indexované jimi. A obsahovalo jakou hračku ma, a jakou chce a pak jestli je ještě v možné výměně ( boolean ). Druhé - pole hraček bylo indexováno přímo čísly hraček a v něm jsem měl uloženo. kolik dětí chce tu hračku.
Myšlenka je jednoduchá. Z pole dětí jsem "odebýral" děti co mají hračku co nikdo nechce. A přitom změnil počet chtění u té hračky kterou chtějí. A to jsem dělal tak dlouho dokud se nějaké odebrání provedlo. No a děti které zbyli v poli si už mohou vyměnit hračky mezi sebou podle přání.
Správnost je zaručena tím, že jsou hračky navzájem různé a tak každé dítě z nich musí chtít navzájem jinou hračku, jinak by totiž existovalo dítě které má nechtěnou hračku. Časová složitost je kvadratická.
Kryl řekl dobře. Ale slyšel jsem že to někdo naprogramoval v lineárním čase, ale to nevím ani jak bylo a ani jestli to bylo spravně.
lyduskag
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 7. 9. 2006 18:08

ustna

Příspěvek od lyduskag »

Ja som si potiahla nedestruktivny prienik LSS a este navyse k tomu, boli usporiadane, takze som to mala za 15 minut hotove.
Ustna: prvy priklad som mala dobre a druhy si musel premysliet.. a pocas toho mi dal Dijkstrov algoritmus (zaskocil ma tym). Dr.Kryl povedal, ze ma akoby skusal tak, ze nemam druhy priklad, ze na neho nebude brat ohlad, aj ked som ho mala vraj dobre, ale nechcelo sa mu dalej ho opravovat. Dijkstra som mu povedala skoro hned a pytal sa ma na dokaz spravnosti toho algoritmu, no a to som netusila, tak mi povedal, ze to az tak nevadi, ze to potrebujem na Diskretnu matematiku, ze na programovani to rozhoduje iba na tom, ci budem mat 1 alebo 2 a tak sa ma este opytal na parameter volany HODNOTOU a ODKAZOM, mala som vediet tie blbosti, ze co to robi, ze pri hodnote to kopiruje do novej lokalnej premennej a take hovadiny, ze odkazom mozem volat IBA premennu a ziadny vyraz alebo cislo, ako to mozem hodnotou.. a ci mozem pouzit pole, zaznam a subor pri oboch a potom som musela vysvetlit, ze subor nemozem pri hodnotou a preco (kvoli pamatovej zlozitosti).. (to sa niekoho pytal minule, tak som bola na tu otazku pripravena).. Potom nasledovala veta, ze mi da 1, AK MI TO NEBUDE VADIT (to bola ale otazka!!!) a potom uz len vyhukane pohlady kamaratov, ktori nechceli verit, ze mam za 1 (pretoze pred tyzdnom ma vyhodil)..
:wink:
inak, aj u mna pouzil znamu vetu "to nechme konovi"..
Odpovědět

Zpět na „PRM044 Programování I“