# [ZK] 1.2., 8:30 <{ForumPost(poster="gASK", timestamp=2006-02-01 13:48:36)}> Proboha, proč tak brzo? :evil: Takže, protože sem nikdo ještě nedal zadání, dovoluji si tak učinit já. Takže poslouchejte, pohádka začíná: PROLOG 1. Maté orientovaný graf. Máte množinu vrcholů. Slučte tuto množinu vrcholů do jednoho. (Tzn místo této množiny bude ve výsledném grafu jen jeden nový vrchol, místo všech hran vedoucích z nějakého vrcholu do / z libovolného vrcholu této množiny jen jedna vedoucí do / z toho nového vrcholu) 2. Máte dán n-ární strom, který má v každém uzlu OKNO (dané souřadnicí levého horního a pravého dolního rohu). Napište predikát, co tento strom projde a ořeže každé okno podle jeho předka (tzn. to co přes předka "přečuhuje" uřízne a vrátí nový strom). Pokud je celé mimo předka, zahoďte uzel i jeho potomky. HASKELL 3. Máte dán n-ární strom. Napište predikát co vrátí seznam cest ze všech listů ke kořeni. 4. Máte dán seznam xs a číslo n. Napište funkci co vám vrátí takovou podmnožinu xs, že její součet je <= n a to tak, že co "nejblíže". Velká úloha je dlouhá, tak mi dovolte pauzu, napíšu ji pod to do nového příspěvku. :wink: <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-02-01 14:05:03)}> Takže tady je slibovaná velká úloha. Tentokrát byla opravdu hyper :twisted: Máte dán orientovaný hypergraf: orientovaný hypergraf je dán množinou vrcholů a množinou hyperhran - hyperhrana je hrana, co má právě jeden výstupní vrchol a alespoň jeden (ale může jich být víc) vstupní vrchol. Vrchol v je dosažitelný z množiny M právě tehdy, když existuje hrana (resp. cesta), jejíž vstupní vrcholy jsou všechny z M a jejíž výstupní vrchol je v. Máte dánu množinu M, kde každý vrchol je dostupný ze všech ostatních. Máte najít všechny vrcholy dostupné z této množiny a určit jejich vzdálenost (viz dole). Použijte k tomu modifikovaný Dijkstrův algoritmus. Vzdálenost nějakého vrcholu je rovna součtu vzdáleností všech vstupních vrcholů hyperhrany, jež do něj vede, plus jedna. Vzdálenost všech vrcholů z M je pochopitelně 0. Viz obrázek dole Tož pěkné, ne? :twisted: *Attachments:* - *[hypergraf.JPG](/Forum%20archiv/Attachments/hypergraf.jpg)* <{/ForumPost}> <{ForumPost(poster="nytram", timestamp=2006-02-01 14:20:09)}> inak, jeho pismo a vysvetlovanie stoja za h0vn0, zadanie tam naskrabal a vysvetlil to este "lepsie"... :evil: :twisted: po polhodiny vahania, ci tam ostat do konca som dospel k zaveru : radsej zdrhnut! .... snaaad nabuduce :( <{/ForumPost}> <{ForumPost(poster="Kuba", timestamp=2006-02-01 14:23:05)}> > gASK wrote: > > > > > 2. Máte dán n-ární strom, který má v každém uzlu OKNO (dané souřadnicí levého horního a pravého dolního rohu). Napište predikát, co tento strom projde a ořeže každé okno podle jeho předka (tzn. to co přes předka "přečuhuje" uřízne a vrátí nový strom). Pokud je celé mimo předka, zahoďte uzel i jeho potomky. Můžu si to představit jako okna s podokny ve Windows? <{/ForumPost}> <{ForumPost(poster="wintermute", timestamp=2006-02-01 14:27:13)}> > Kuba wrote:Můžu si to představit jako okna s podokny ve Windows? Nemůžeš!!! <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2006-02-01 14:38:43)}> > Kuba napsal: > Můžu si to představit jako okna s podokny ve Windows? > > Nemůžeš!!! Ale muzes! :) Nekdo se na to Hricaka ptal...... Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :( <{/ForumPost}> <{ForumPost(poster="Kuba", timestamp=2006-02-01 14:41:16)}> > Anonymous wrote: > > Kuba napsal: > > Můžu si to představit jako okna s podokny ve Windows? > > > > Nemůžeš!!! > > > > Ale muzes! :) Nekdo se na to Hricaka ptal...... > > > Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :( To si asi rikal "Ja blbec, jak jsem je to naucil?!" A kdy se vlastne chodi na ustni? <{/ForumPost}> <{ForumPost(poster="wintermute", timestamp=2006-02-01 14:41:37)}> > Anonymous wrote: > > Kuba napsal: > > Můžu si to představit jako okna s podokny ve Windows? > > > > Nemůžeš!!! > > > > Ale muzes! :) Nekdo se na to Hricaka ptal...... > > > Mam pocit, ze je dneska v nedobrej nalade, pri opravovani tech pisemek tam bouchal hlavou do stolu :( A jéje... no, tak já letim, v 15:30 mám ústní část zkoušky. Docela si i věřim na 1, ale jestli ho třeba bolí zub... :( <{/ForumPost}> <{ForumPost(poster="Necroman", timestamp=2006-02-01 15:26:18)}> Tak je to doma... priklady byly celkem pohodove, ten prvni vysel na 4 radky :-) hrany zadany jako h(a,b). ->hrana z A do B seznam vrcholu, ktery se mel sloucit do jednoho (napr vrcholu n): x(a). x(b). ... reseni: vyres(S):- setof(h2(X,Y),h2(X,Y),S). h2(X,Y):-h(X,Y),\+ x(X), \+ x(Y). h2(n,Y):-h(X,Y),x(X), \+ x(Y). h2(X,n):-h(X,Y),\+ x(X), x(Y). Jeste jedna rada, zkuste nepouzivat k reseni velkych prikladu "naivni" algoritmy, me dal kvuli tomu za tri :roll: . <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-02-01 15:32:28)}> Nevím v jaké je náladě, ale mně dal za jedna. A vůbec, co jsem mu koukal pod ruku, tak většina co zatím rozdal byly jedničky...jinak ústni jela od dvou, já tam měl být na půl třetí, na řadu jsem se dostal o čtvrt na čtyři, přesvědčil mne, že mý řešení druhý příkladu nefunguje, přečetl velkej, pokejval hlavou a pravil: "Index". Tak asi tak. Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted: <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2006-02-01 16:31:04)}> > gASK wrote: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted: slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.) <{/ForumPost}> <{ForumPost(poster="wintermute", timestamp=2006-02-01 16:57:01)}> Takže za 1. Ale myslim, že jsem na něj neudělal moc dobrej dojem, když zjistil, že vlastně pořádně neumim Dijkstrův algoritmus. <{/ForumPost}> <{ForumPost(poster="Kuba", timestamp=2006-02-01 21:00:53)}> > Anonymous wrote: > > gASK wrote: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted: > > > slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.) Moje reseni neni zrovna na 6 radku, ale tohle (3) jsem si psal doma: data NTree a = Tr a [NTree a] -- Prochazi strom a pamatuje si, kudy sel (cur - prvky pridava dopredu, jde o cestu z listu do korene!) -- Kdyz dojde do listu, prida cestu do seznamu cest, ktery se vsude taha (sezn) hledej :: NTree a -> [[a]] hledej (Tr x (y:ys)) = ses [x] (y:ys) [[]] ses :: [a] -> [NTree a] -> [[a]] -> [[a]] -- projde vsechny podstromy aktualniho uzlu ses _ [] [[]] = [] -- aby to nevracelo prazdny seznamy navic ses _ [] x = x -- kdyz jsem prosel vsechny podstromy ses cur (y:ys) sezn = sestup cur y sezn ++ ses cur ys sezn -- cesty z aktualniho podstromu ++ z ostatnich sestup :: [a] -> NTree a -> [[a]] -> [[a]] -- zpracuje jeden podstrom sestup cur (Tr x []) [[]] = [(x:cur)] -- aby to nevracelo prazdny seznamy navic sestup cur (Tr x []) sezn = (x:cur):sezn -- list sestup cur (Tr x (y:ys)) sezn = ses (x:cur) (y:ys) sezn -- nelist <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-02-02 16:31:34)}> > Anonymous wrote: > > gASK wrote: Jinak ono i řešení třetího a čtvrtého příkladu bylo všeho všudy po šesti řádcích. Jen ten proklatej druhej mi zabral dvě stránky :twisted: > > > slo by to sem prosim napsat? urcite by to mnoha lidem pomohlo a kdyz je to tak kratke, tak by to nemuselo zabrat moc casu ani vam. diky (mam na mysli 3. a 4.) Takže řešení trojky: data Tree a = Leaf a | Branch a [Tree a] cesta::Tree a -> [[a]] cesta Leaf x = [[x]] cesta Branch x xs = map (++[x]) (fold [cesta y | y <- xs]) fold::[[a]] -> [a] fold [] = [] fold (x:xs) = x++(fold xs) Jinak řečeno jsem si v každém vrcholu nechal do seznamu nasypat všechny cesty do všech jeho synů, ke všem připojil na konec daný uzel (nejsem si jist, jestli mám ten map správně, něco se mi tam nezdá). Fold pouze zajišťuje "správný počet závorek", páč mi po kadžý iteraci cesty jedny "přebývají". A čtyřka: soucet::[a] -> a -> [a] soucet [] _ = 0 soucet _ 0 = 0 soucet (x:xs) n = if (sum Batoh1 <= n) then if (sum Batoh2 > n) then (Batoh1) elseif (sum Batoh1 >= sumBatoh2) then (Batoh1) else (Batoh2) else (Batoh2) where Batoh1 = x:(soucet xs n-x) Batoh2 = soucet xs n Tohle není ouplně šest řádků, ale je to zase pro změnu úplně triviální program. <{/ForumPost}> <{ForumPost(poster="rastik", timestamp=2006-02-02 22:31:33)}> > gASK wrote:(nejsem si jist, jestli mám ten map správně, něco se mi tam nezdá). Fold pouze zajišťuje "správný počet závorek", páč mi po kadžý iteraci cesty jedny "přebývají". Map je spravne, ale definicia fold-u ma byt: fold :: [[a]] -> [a] Inac velmi pekne riesenie, paci sa mi. <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-02-02 22:37:17)}> > rastik wrote: > > gASK wrote:(nejsem si jist, jestli mám ten map správně, něco se mi tam nezdá). Fold pouze zajišťuje "správný počet závorek", páč mi po kadžý iteraci cesty jedny "přebývají". > > Map je spravne, ale definicia fold-u ma byt: > > > > fold :: [[a]] -> [a] Pochopitelně...zajímavý, že v písemce mi to prošlo i se dvěma závorkama...ještě se nad tím zamyslím, až nebudu mít hlavu plnou analýzy... :twisted: <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2006-02-11 23:38:33)}> ta velka uloha sa podozrivo podoba na moj zapoctak... neni to tak tazke, myslienka je vcelku jasna(prehladavanie do hlbky) implementacia je uz trocha ina. v zapoctaku veselo pridavam do databazy, potom to ide, ovsem ja som chcel aj cenu vrcholu vypisat, aj vediet cestu... <{/ForumPost}>