Fórum studentů MFF UK

od **Návštěvník** » 11. 2. 2006 23:38

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...

od **gASK** » 2. 2. 2006 22:37

rastik píše:
gASK píše:(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:
Kód: Vybrat vše
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...

od **rastik** » 2. 2. 2006 22:31

gASK píše:(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:

Kód: Vybrat vše

fold :: [[a]] -> [a]

Inac velmi pekne riesenie, paci sa mi.

od **gASK** » 2. 2. 2006 16:31

Anonymous píše:
gASK píše: 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
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:

Kód: Vybrat vše

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:

Kód: Vybrat vše

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.

od **Kuba** » 1. 2. 2006 21:00

Anonymous píše:
gASK píše: 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
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:

Kód: Vybrat vše

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

od **wintermute** » 1. 2. 2006 16:57

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.

od **Návštěvník** » 1. 2. 2006 16:31

gASK píše: 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

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.)

od **gASK** » 1. 2. 2006 15:32

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

od **Necroman** » 1. 2. 2006 15:26

Tak je to doma... priklady byly celkem pohodove, ten prvni vysel na 4 radky

Kód: Vybrat vše

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

.

od **wintermute** » 1. 2. 2006 14:41

Anonymous píše:
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...

od **Kuba** » 1. 2. 2006 14:41

Anonymous píše:
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?

od **Návštěvník** » 1. 2. 2006 14:38

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

od **wintermute** » 1. 2. 2006 14:27

Kuba píše:Můžu si to představit jako okna s podokny ve Windows?

Nemůžeš!!!

od **Kuba** » 1. 2. 2006 14:23

gASK píše:

Kód: Vybrat vše

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?

od **nytram** » 1. 2. 2006 14:20

inak, jeho pismo a vysvetlovanie stoja za h0vn0, zadanie tam naskrabal a vysvetlil to este "lepsie"...

po polhodiny vahania, ci tam ostat do konca som dospel k zaveru : radsej zdrhnut! .... snaaad nabuduce

Fórum studentů MFF UK

[ZK] 1.2., 8:30

Odeslat odpověď

Rozšířit náhled Přehled tématu: [ZK] 1.2., 8:30

Re:

Re: [ZK] 1.2., 8:30

Re: [ZK] 1.2., 8:30