Cafte ludia, co keby ste pustili do eteru nejake tie male priklady co ste mali na dnesnej skuske.
Moj bol nasledovny:
Napiste proceduru, ktora precita zo vstupneho textoveho sudoru postupnost kladnych cisiel a vytvory dokonale vyvazeny BVS. Dokonale vyvazeny stom ,je taky v ktorom sa pocet vrcholov lisi najviac o 1. Pocet cisiel na vstupe <= 100.
Velky priklad vam uz nepoviem, bo som na nom uz nebol. :wink:
Ked tak ho niekto doplnte....
MIKI wrote: Velky priklad vam uz nepoviem, bo som na nom uz nebol. :wink:
Ked tak ho niekto doplnte....
Oj, takze jsi toto nedal? :/ No ,ono to teda neni zas tak lehke... Bylo nejake omezeni na cas? Jako jestli chteli o(n log n) nebo neco tak? Protoze v case n log n je to pohodicka, jen musi clovek umet napsat nejaky dobry tridici algoritmus... ;)
Takze to funguje tak, ze clovek nejprv pise lehky priklad a az pak si vytahne ten tezky?
Ja jsem dostal megaprimitivni ulohu:
Sestavte dokonale vyvazeny binarni vyhledavaci strom z hodnot 1..N. Parada... mozna tam nejakou chybku s pointerama mit budu, ale napsal jsem to za 5 minut a pul hodiny kontroloval. Na maly priklad byla hodina casu.
Kdyby tu nebylo omezeni, ze mame pocitat s tim, kdyz bude v dynamicke strukture vetsi mnozstvi polozek nez je mozne ulozit do pole v BP, tak se jedna o druhou cast ulohy, kterou mel resit MIKI. Takhle to mel jeste tezsi.
Velky priklad byl z burzy, trosku zjednodusim vstup (byla tam halda zbytecnych veci). Na vstupu jsou prikazy makleru pro burzu:
Makler1 koupit 100 telecom 500
Makler1 koupit 500 nevim_co 4500.50
Makler2 prodat 350 telecom 700
...
(maximalne 100 000 000 pozadavku)
Na radku tedy je:
jmeno_maklere (prodat/koupit) pocet_akcii jmeno_spolecnosti cena_akcii_(s presnosti na halere)
Akce se skutecne koupi, pokud budou nabizeny za cenu ktera je mensi nebo rovna. K prodeji akcii dojde, pokud bude cena vetsi nebo rovna uvedene cenne.
Ukol: rano prisly na burzu tyhle pozadavky, nastavte ceny akcii vsech spolecnosti tak, aby se jich prodalo co nejvic.
jako prvni priklad jsem mel 2 mnoziny ulozene v spojacich.
mel jsem napsat proceduru na urceni pruniku techto mnozin. takze pohoda jestli jsem se nikde neupasal tak by to mohlo dopadnout, protoze ke druhemu jsem neco napsal ..... no uvidim zitra.
Mimochodem, Holan v prubehu upozornoval, ze po provedeni sjednoceni/pruniku budou z obou seznamu odstraneny duplicity (protoze takhle taky sjednoceni mnozin funguje - prvky uvedene vicekrat uvede jen jednou).
Ono to nakonec ten program zjednodusi.
Obtiznost maleho prikladu me docela zaskocila:
mate soubor, kde na kazdem radku je libovolne dlouhe cislo (i zaporna !)
vypiste soucet celeho souboru
cisla jsem reprezentoval jako spojaky cislic(zasobniky), Holan rikal, ze jsou to priklady na dyn. dat. struktury, nevim, jestli by se dalo pouzit nafukovaci pole.
no a mel jsem tam:
porovnej 2 spojaky (potreba u odecitani)
otoc spojak - kdyz scitam cisla, ctu odzadu, a hazu do zasobniku => vysledek je v zasobniku opacne, nez ho budu potrebovat pro dalsi krok
secti 2 spojaky
odeci 2 spojaky (odecitej mensi od vetsiho)
vysledek otoc a povazuj za novy scitanec
precti cely soubor a u kazde radky se podle 1. znaku rozhodni, jestli scitat nebo odecitat
nakonec vypis vysledek
za hodinu na papir kompletni kod, huste !
urcite to nemam nic moc, ale nebyl prakticky zadny cas o cemkoliv premyslet, mohl bych zaporne cisla reprezentovat v dopnkovem kodu a pak jen scitat - usetril bych odecti() a porovnej(), ale za boha jsem si nemohl vzpomenout, jak se to dela.
ted jsem si navic vzpomnel, ze treba pro 2 - 3 mi to vezme zavola odecti(3, 2) a vysledek je 1 :roll: u reprez. cisla si nikde nepamatuju znamenko, asi by to chtelo mit 2 spojaky - na kladne a zaporne cisla.
ve stredu jdu na ustni, pocit nic moc
Já měl prachobyčejný Delete na BVS.
Jak řekl sám Holan na zkoušce - kdo to nenapsal ani jednou, tak to určitě blbě vymyslí :)
Ahojky!!! Ja mela dneska tento priklad: Na vstupu je textovy soubor a v nem tri kladna desetinna cisla (neomezene dlouha, kazde samostatne na radku), vypiste soucet techto tri cisel ...bylo to celkem pracne, takze jsem to moc nestihala a asi to nedopadne nic moc :(((
ja mel vytvorit binarni strom z prefixoveho vyrazu pro jednociferne cisla ( pr. *+45-36 )
Takisto som dostal spravit prienik dvoch mnozin, reprezentovanych spojakmi.
Lenze som si poplietol prienik a zjednotenie. :oops:
Na ustnej to pan Topfer okomentoval slovami: "OK, tak se podivame na sjednoceni!" Mal som tam zopar chyb (napr. var navyse, chybala vetva else pre pripad, ze by aspon jeden zo spojakov bol nilovy :roll: ) a hlavne mi chybalo dokoncenie pomocnej procedurky, takze verdikt znel: "Tak, maly priklad za tri, velky vam nesed, takze taky za tri a usti - zadna slava, to bylo za ctyri, takze nic z toho nebude." :cry: Preto idem este raz zajtra.
Když tak koukám :shock: na všechny ty zadání, tak mám pocit že tu neni skoro nic z grafových algoritmů... Taky vám to tak přijde? Což znamená že nejsou moc častý a nebo to znamená, že je dostanou ti co půjdou později... :?
Grafovy algoritmy neodpovidaji ucelu malych pisemek, ty jsou na to, abys ukazalo, ze dokazes technicky zvladnout praci s dynamickyma strukturama. Teda nejaky prohledavani do sirky tam byt muze, ale nic moc vic bych necekal. Na algoritmy jsou tu velky pisemky, koukni na zadani na fearu.
MIKI wrote:Cafte ludia, co keby ste pustili do eteru nejake tie male
Napiste proceduru, ktora precita zo vstupneho textoveho sudoru postupnost kladnych cisiel a vytvory dokonale vyvazeny BVS. Dokonale vyvazeny stom ,je taky v ktorom sa pocet vrcholov lisi najviac o 1. Pocet cisiel na vstupe <= 100.Velky priklad vam uz nepoviem, bo som na nom uz nebol. :wink:
Ked tak ho niekto doplnte....
Si si isty, ze to mal byt BVS?
Broskyna wrote:
MIKI wrote:Cafte ludia, co keby ste pustili do eteru nejake tie male
Napiste proceduru, ktora precita zo vstupneho textoveho sudoru postupnost kladnych cisiel a vytvory dokonale vyvazeny BVS. Dokonale vyvazeny stom ,je taky v ktorom sa pocet vrcholov lisi najviac o 1. Pocet cisiel na vstupe <= 100.Velky priklad vam uz nepoviem, bo som na nom uz nebol. :wink:
Ked tak ho niekto doplnte....Si si isty, ze to mal byt BVS?
Na 100% bo je kompletne zadanie opisane z toho papiera :twisted:
MIKI wrote:
Broskyna wrote:
MIKI wrote:Cafte ludia, co keby ste pustili do eteru nejake tie male
Napiste proceduru, ktora precita zo vstupneho textoveho sudoru postupnost kladnych cisiel a vytvory dokonale vyvazeny BVS. Dokonale vyvazeny stom ,je taky v ktorom sa pocet vrcholov lisi najviac o 1. Pocet cisiel na vstupe <= 100.Velky priklad vam uz nepoviem, bo som na nom uz nebol. :wink:
Ked tak ho niekto doplnte....Si si isty, ze to mal byt BVS?
Na 100% bo je kompletne zadanie opisane z toho papiera :twisted:
Njn, je to tak, tohle zadání není ničím vyjímečné a upřímně mi ani nepřijde nezvládnutelné - načíst, setřídit a pak třeba pomocí půlení intervalů z pole udělat BVS...
LordWolverin wrote:Njn, je to tak, tohle zadání není ničím vyjímečné a upřímně mi ani nepřijde nezvládnutelné - načíst, setřídit a pak třeba pomocí půlení intervalů z pole udělat BVS...
Mne uprimne nezvladnutelne prislo spomenut si po roku na nacitanie zo suboru v pascale... to ostatne nebol problem....
Inak z tej tvojej uprimnej odpovede sudim, ze struhas machra... :-/ ....alebo mi to len tak blbo znie....
MIKI wrote:
LordWolverin wrote:Njn, je to tak, tohle zadání není ničím vyjímečné a upřímně mi ani nepřijde nezvládnutelné - načíst, setřídit a pak třeba pomocí půlení intervalů z pole udělat BVS...
Mne uprimne nezvladnutelne prislo spomenut si po roku na nacitanie zo suboru v pascale... to ostatne nebol problem....
Inak z tej tvojej uprimnej odpovede sudim, ze struhas machra... :-/ ....alebo mi to len tak blbo znie....
Aha :o). Já to nemyslel nijak špatně (ani nemůžu, se svými výsledky), ale z těch zadání na malé příklady se mi to fakt zdá z těch jednodušších, oproti nějakým součtům libovolně dlouhých čísel a podobným legráckám
Matfyz Wiki