Dnešní zkouška - nemáte zprávy?

Uživatelský avatar
Trupik
Matfyz(ák|ačka) level III
Příspěvky: 251
Registrován: 3. 1. 2005 14:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Dnešní zkouška - nemáte zprávy?

Příspěvek od Trupik »

Tak co, co tam bylo? Dali jste to?
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz

Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Uživatelský avatar
David Nohejl
Matfyz(ák|ačka) level III
Příspěvky: 135
Registrován: 10. 10. 2004 17:23
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek od David Nohejl »

ne

teda ustni mam az za dve a ctvrt hodiny, ale pisemnou cast sem *docela* pokazil :oops:

Jako lehky ukol sem mel obratit jednosmerny spojak ( aniz bych vytvarel novy nekde bokem)

Jako tezky bylo takovy CVS - hmm jak to jenom bylo... mas naky soubor se seznamem verzi ( treba projektu) setridena od nejstarsi po nejnovejsi, kazda verze obsahuje seznam souboru. Mas funkce RozbalVerzi() a SmazAdresar() . Mas do adresare "vystup" - kurna na ten sem zapomel - vypsat nejnovejsi verzi, a na kazdy radek do kazdyho souboru pripsat poznamku "// nejstarsi verze ktera tento radek obsahuje ", pricemz nejstarsi verzi se mysli ze od te verze ten radek je na svem miste.

Aspon tak nejak sem to pochopil... no ale na reseni se mne neptej :((

Jo a pak naky omezeni, jako ze mas 1MB pameti a ze na disk se ti vejde max 10 verzi rozbalenejch, verzi je max 1000 a kazda obsahuje max jauznevimkolik souboru atd...

Jo taky vis ze ta funkce RozbalVerzi() je hrozne pomala...

Me to prislo docela tezky (cti: nemam narok)
Never forget: Stay kul and happy (I.A.)
Angel

pisemka

Příspěvek od Angel »

No, ja jdu na ustni za pul hodky, me zase prislo tohle zadani jedno z lehcich, protoze se dalo za ty tri hodiny stihnout cely naprogramovat, zadna optimalizace zisku, to nesnasim :-)....

Jestli udelam ustni, tak vam mozna napisu, jak jsem to resil...


Jako malej priklad sem mel prevest ze vstupu vyraz z prefixu do binarniho stromu... Akorat ted premejslim, snad sem neprecetl blbe a nebylo tam z postfixu :D.
Angel

jo!

Příspěvek od Angel »

Tak to mam za 2, pac sem dostal na ustni B-stromy, ktery sem fakt nechtel a moc sem je nedaval, odmlel sem mu tam neco co sem zaslechl v tramvaji o AB stromech a nejak sem se z toho vykroutil...

Reseni velkyho priklad se mu docela aji libolo. Mel sem ho naprogramovany skoro cely, kod ale vubec necetl, pac sem k tomu mel stranku povidani...

hlavni rysy meho reseni:
- rozbalit nejnovejsi verzi
- ke vsem radku ve vsech souboru si dat cislo teto nejnovejsi verze
( dale aktual verze )
- pomocny seznam souboru aktual verze

- while na verze postupne starsi (zase ale od nejnovejsi) ( dale tmp verze )
projit postupne soubory aktual verze, pokud soubor neni v tmp verzi, vyradit ho uplne ze seznamu (nema cenu ho dale zkoumat - 1. vec, ktera se libila), pokud je, tak:
ctu postupne radky ze souboru (samozrejme aktual verze). U techto radku uz mam verzi, pokud se ta verze lisi od tmp verze (tu prave zpracovavam) vic jak o jedna (tedy ta radka byla modifikovana v nejakem nebezprostredim cyklu), tak me tato radka dal nezajima a muzu jit na dalsi (todle je 2. podstatna vec, ktera se mu libila). Pokud ne, tak pomoci algoritmy zjistuji jestli neni v tmp verzi (algoritmus popisu pozdeji) jiz ta stejna radka, pokud ano, prepisu u teto radky verzi na tmp verzi. Radku potom zase zapisu do vysledneho souboru aktual verze...

Tot vse.

Nelibilo se mu, ze pracuji se soubory po radcich, same cteni a zapis, mel sem tam ale navrhnuto slovne reseni, kdy si cely file muzete hodit do pameti jako celek (pamet na to stacila) a pomoci ukazatelu a koncu radek si pak tyto radky vracet nejakou fci... (porad nemohl prenyst pres srdce ze to tak nemam a porad nechtel videt, ze to tam mam napsany jako alternativni lepsi reseni :-/.

Algoritmus na to, zda radky jsou jiz v souboru predesle verze nebo ne se me uz psat nechce, mel sem ho tam viceme spise slovne popsany, kazdopadne pozorny ctenar si ho sam odvodi ;-).
Angel

oprava...

Příspěvek od Angel »

Oprava: ... ne bezprostredne predchozim cyklu ...
Návštěvník

Příspěvek od Návštěvník »

Taky jsem rad ze bylo zrovna tohle zadani, bylo to jedno z tech lidstejsich, kde si clovek mohl vyhrat i s kodem :)

Moje reseni se mu libilo, upozornil me jen na to (ale o tom jsem vedel a taky jsem to tam napsal), ze je dost neprakticky porovnavat radek po radku, protoze jeden prazdny radek vam to cely rozhazi. To by se dalo resit porovnavanim nejakeho vhodne velkeho okoli, ale to uz jsem nestihl.

Zeptal se me na minimax a alfa-betu, coz bylo tema ktere jsem si opravdu pral ze vsech nejmene, protoze jsem o tom nejmene vedel. Nicmene i pres muj objektivne bidny vykon v ustni casti mi dal dvojku a tak jsem stastny jako blecha :D
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Jak sem to mel ja

Příspěvek od hippies »

no ja sem totalne podelal malou ulohu,... mel sem z BVS vyhodit interval, chtel sem to delat cyklem po jednom prvku, protoze jinak tam mohou nastat dost slozite situace, ktere bych fakt nerad osetroval, ale udelal sem tam takovou "drobnou" botu... Zapomnel sem uplne prepojovat koren, teda ja sem si ho vracel, ale daval sem ho do lokalni promenne, coz pres srdce neprenes a 4.
Velkou ulohu si myslim, ze sem mel docela dobre, taky sem sel odnejnovejsi verze, taky sem otviral jen soubory, ktere jsou jeste k oprave, ale taky sem to nacital po velkych blocich a hezky to porovnaval aby me vlozene prazdne radky ani ty smazane nenarusily ten zbytek,... bylo to v kvadratickem case, jak to meli asi vsichni a on mi akorat rekl, ze na kazdou verzi existuje protipriklad a ze nejlepsi je porovnavat to po skupinach radku,... tak mi za to dal 2-
Pak se zeptal na vnejsi trideni to bylo v pohode, jednofazovy, vice,... k cemu,.. jak,... proc,.... no a pak se ptal, co by se stalo, kdyby pri slevani byl vynechan krok, kdyz dojde beh, druhej bech vysyp, ale proste se pokracovalo (no vyrazne by se to zpomalilo,... rek sem to dobre, on si ale nebyl jistej, jestli by se to taky nemohlo zastavit, coz si myslim, ze ne)
No a tak vahal mezi 2 a 3 a zeptal se na doplnujici otazku,... k cemu a co to je konstruktor,... tak sem mu rek uplne vsechno co se vo nem rict da, ale na to jediny co chtel slyset sem si nevzpomnel, ze nastavuje VMT, takze za 3, ale z blbosti, jinak byl fakt hodnej, ....
... ze zvatlam mi rekl asi jen 1x maximalne 2x :wink:
Uživatelský avatar
MSm
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 9. 12. 2004 14:38
Typ studia: Informatika Bc.
Bydliště: Praha 3, Žižkov
Kontaktovat uživatele:

Příspěvek od MSm »

Tak jsem byl dneska na ustnim u p. Kryla...
Ve velkym prikladu jsem ja hlupak bral soubory od nejstarsiho, ale celkem prijemne jsme si o tom popovidali a spojaky jsem mel v pohode (taky otocit jednosmernej), vysledek horsi dvojka. Krome zakladnich myslenek ho ten velkej program IMO skoro nezajimal - bud umi strasne rychle cist, nebo to klidne mohla bejt svahilstina doplnena rovnitkama a strednikama.
Pak mi dal QuickSort - samozrejme jsem vedel zaklady, ale kdyz se zacal vyptavat na pametovy naroky, porovnani s HeapSortem a jeste naky dalsi detaily, tak jsem v tom dost plaval. Nakonec to probihalo stylem "Kolik je 1+1?" "Jestli se nepletu, tak dve." "Ano, spravne." A pak jsem se dozvedel, ze jednicka uz to asi nebude, takze za dve :shock:
Inu, hodne stesti vsem!
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

U Holana a moje reseni

Příspěvek od pasky »

Byl jsem sice u Holana, ale priklad jsem resil stejny jako vsichni ostatni, takze to napisu sem... (Mam pocit, ze v pripade programka to rozdeleni na vyucujici moc nefunguje.)

V malem prikladu jsem mel jen chybu v prioritach operatoru (klasicka chyba s and a or, kterou udela vetsina lidi, kteri uz pascal par let nevideli :wink:), ale jinak v pohode, takze ten byl za jedna.

Ve velkem prikladu jsem mel kodu jen hodne malo, zato asi 2.5 A3 povidani, i kdyz pravda zmateneho, a zaroven jsem to jeste behem psani domyslel, takze na konci jsem popisoval uz trochu neco jineho nez na zacatku a bylo to dost neprehledne. Ale vlastne jen tu pisemku prede mnou otevrel a chtel po mne, abych popsal, jak jsem to teda delal, a pri tom jsme se snazili drzet toho, co jsem na ten papir napsal. Na kod se ani nepodival, ale algoritmus se mu libil (i kdyz tam byly nektere mensi veci trochu nedomyslene) - rekl, ze je to perfektni, a at mu dam index. :D Takze pokud mate hezke reseni, ktere se mu zalibi, ani nemusi dojit na zadnou teorii.

Moje reseni spocivalo v zasade v tom, ze pro kazdy soubor jsem si v pameti drzel tabulku radku s verzemi, kdy byly naposledy zmeneny, a jak jsem se soubory sel do minulosti, musel jsem si drzet mapovaci tabulku na cisla radek v posledni verzi souboru - protoze kdyz jsem treba do souboru pridal radek, cisla vsech nasledujicich radek se mi posunuly o jednicku, a musel jsem si index upravit, abych sahl na spravny radek v tabulce poslednich zmen (to tu tak rozvadim proto, ze se na to pry hodne zapominalo).

Vzdy jsem si rozbalil deset verzi najednou, a pak jsem je postupne vzdy prochazel po souboru - nacetl jsem si uplne soubor z verze #10 a #9, spocital jsem diff (a podle nej upravil tabulku zmen a mapovani), pak jsem zahodil buffer verze #10 a nacetl verzi #8, a tak dale - tohle jsem udelal pro vsechny soubory, dokud jsem nenarazil na prvni verzi nebo jsem uz mel vsechny radky ve vsech souborech.

Diffovani jsem delal tak, ze jsem si pri nacitani do bufferu kazdy radek zahashoval a udelal jsem si hashovaci tabulku, ktera ukazovala na cislo radku. Kdyz jsem narazil na radek, ktery je v kazde verzi jinak, podival jsem se do hashovaci tabulky druhe verze, kde ten radek az je - a vybral jsem tu verzi, kde je rozdil mensi. To sice nezaruci minimalni diff, ale dava to relativne dobre vysledky, je to linearni (pokud nam hashe preji) a zere to malo pameti.

Doufam, ze to neni az prilis zmatene popsane...
Next lecture on time travel will be held on previous Monday.
ON.

ustni s Holanem

Příspěvek od ON. »

tez sem se ucastnil a jdu vam teda sdelit nejake postrehy :

jednoduchy priklad sem mel, destruktivni sjednoceni dvou lin. seznamu, tzn. spojit je ale kdyby se tam mel nejaky prvek objevit dvakrat tak jednoho z nich odalokovat...mel sem tam nejake nedorozumeni. Perfektni bylo ze mi Holan rekl kde je chyba a ze mam vymyslet jak to zpravit, a sam si sel neco delat ke kompu..

velkeho prikladu sem se dost desil, mel sem tam vsehovsudy tak 15 :!: radek nesmyslneho kodu, asi 2 stranky obrazku uplne k nicemu, a jediny jeden papir nejakeho toho shrnuti. hlavni myslenky sme stejne probrali spolu a ze tam nemam nic naimplementovaneho mu vubec nevadilo..

zeptal sem me potom na klasiku se statickyma a virtualnima metodama v packalu a uz sem podaval index - takze dvojecka :D

jinak Holan byl perfektni, kdo by teda nechtel byt narknut ze zvatla tak sem se pri rozpisu na ustni psal do druheho sloupce :wink: ( jestli to je pravidlo ale fakt netusim :) )
Stefan

Re: ustni s Holanem

Příspěvek od Stefan »

ON. píše:jinak Holan byl perfektni, kdo by teda nechtel byt narknut ze zvatla tak sem se pri rozpisu na ustni psal do druheho sloupce :wink: ( jestli to je pravidlo ale fakt netusim :) )
Bohužel není. Týden po tobě patřil druhý sloupeček Krylovi. Vyhlédl jsem si ho a vymstilo se mi to. Asi je to náhodným výběrem, takže spíš si to dej hodně pozdě, pak se podívej až to vyvěsí, a pokud dostaneš Kryla, tak se nauč všechno ještě jednou
Odpovědět

Zpět na „2004“