# [Zk] 16.5.2008 <{ForumPost(poster="bartolomej", timestamp=2008-05-16 21:17:29)}> 1.) PROLOG: Hladovym algoritmom pomocou heuristiky najst minimalne ofarbenie grafu. 2.) PROLOG: Z postfixneho zapisu n-arneho stromu vytvorit n-arny strom. napr: (hodnota,pocet synov) IN: postfix = \[('b',0),('e',0),('f',0),('c',2),('d',0),('a',3)] OUT: NodeN 'a' \[NodeN 'b' \[],NodeN 'c' \[NodeN 'e' \[],NodeN 'f' \[]],NodeN 'd' \[]] 3.) HASKELL: Mame zadany orientovany graf. Treba vyhodit vs.hrany (u,v), pre ktore existuje cesta dlzky 2 z u do v. 4.) HASKELL: Na vstupe mame obdlzniky(okna), mame zistit ci sa nejake prekryvaju. type Rozmer = (Int,Int) type Obd = (Int,Int,Rozmer) // (sur_x,sur_y,(sirka,vyska)) data Maybe a = Nothing | Just a Ulohou bolo napisat funkciu: prusek :: \[Obd] ->Maybe (Obd,Obd) //dostane okna a vrati Kolidujucu dvojicu 5.)Vs o negacii v Prologu <{/ForumPost}> <{ForumPost(poster="peterblack", timestamp=2008-05-16 23:10:38)}> mno zkouska je zamnou...ale stejne mi prijde Prolog jako takovy zly Voodoo :) Haskell mi sednul mnohem vic a Hric je pomerne hodnej pan...nevim proc me vzdycky tak desil pro zajimavost moje reseni 2: (zachovava poradi) rs([],S,S). rs([(X,Y)|Z],S,Vysl):- rozdel(S,Y,SY,S2), rs(Z,[nt(X,SY)|S2],Vysl). rozdel(S,0,[],S). rozdel([S|SS],Y,SY,S2):- Y1 is Y-1, append(S1,[S],SY), rozdel(SS,Y1,S1,S2). spustrs:-rs([(b,0),(d,0),(e,0),(c,2),(a,2)],[],X), write(X). A od kolegy reseni 4: type Rozmer = (Int, Int) type Obd = (Int, Int, Rozmer) prekryti :: [Obd] -> Maybe (Obd,Obd) prekryti sObd| (seznamKolizi == []) = Nothing| otherwise = Just (head seznamKolizi)whereseznamKolizi = [(a,b) | a <- sObd, b <- (filter (/=a) sObd), prekryvajiSe a b] prekryvajiSe :: Obd -> Obd -> Bool prekryvajiSe (zx1,zy1,(xz1,yz1)) (zx2,zy2,(xz2,yz2)) =if ((zx1 < zx2) && (kx1 > zx2)) then if ((zy1 < zy2) && (ky1 > zy2)) then True else if ((zy2 < zy1) && (ky2 > zy1)) then True else Falseelse Falsewherekx1 = zx1 + xz1ky1 = zy1 + yz2kx2 = zx2 + xz2ky2 = zy2 + yz2 -- dotaz1: prekryti [(0,0,(6,4)),(6,5,(2,2)),(7,6,(9,8))] -- dotaz2: prekryti [(2,0,(2,5)),(0,2,(5,1))] <{/ForumPost}> <{ForumPost(poster="lickra", timestamp=2008-05-17 16:00:22)}> PROLOG: Hladovym algoritmem pomoci heuristiky najit minimalne obarbeni grafu. obarvi([],_,[],_). obarvi([(I-J)|T],Uz,[(J-N)|Z],Max):-otoc([(I-J)|T],J,OTOC),seznamMax(Max,Z),zjistiMinBarvu(J,OTOC,Uz,Z,N),dejdoUZ((J-N),Uz),maximum(Max,N,Max1),obarvi(T,Uz,Z,Max1). zjistiMinBarvu(_,[],Z,N):-minimum(Z,N). zjistiMinBarvu(J,[(I-J)|T],Uz,Z,N):-member(I,UZ),barva(I,Uz,F),delete(Z,F,Z1),zjistiMinBarvu(J,T,Uz,Z1,N). % otoc-otoci hrany tak aby koncili J % minimum najde min ze seznamu nebo M % seznamMax vrati seznam [1..Max] Pozn.: Neni to uplne hladovy algoritmus, najdem vsechny barvy kteryma muzeme barvit a vyberem tu nejmensi, ale hricovi to nevadilo Druhe reseni vic hladovejsi zjistiBarvu(S,T,X,X):-jde(S,T,X). zjistiBarvu(S,T,X,N):- X1 is X+1, zjistiBarvu(S,T,X1,N). jde([],_,_). jde([S|Z],T,X):-notmenber((S-X),T), jde(Z,T,X). barvy([],X,X). barvy([[V|ZS]|Z],T,X):-zjistiBarvu(ZS,T,1,N),barvy(Z,[(V-N)|T],X). Prolog 2: Z postfixneho zapisu n-arniho stromu rekonstruovat n-arny strom. Vstup \[B-0,E-0,F-0,C-2,D-0,A-3] rekonstrukce(Vstup,Strom):-reverse(Vstup,Vystup), makeTree(Vystup,_,Strom). makeTree ( [ Val-0|T], T, t(Val,[]) ). makeTree ( [Val-N|T], Z, t(Val, Childs) ) :- makeChild ( T, N, Z, Childs ). makeChild ( T, 0, T, [] ). makeChild ( T, N, Z, [C|Childs] ) :- makeTree ( T, Zb, C ),N1 = N – 1, makeChild ( Zb, N1, Z, Childs). Pozn.: Celkem ok ale drobnost nezachovava poradi synu!! Haskell 3: V orientovanem acyklickem grafu vyskrtat hrany\[u,v] pokud mezi vrcholy u a v existuje cesta delky 2. vstup je seznam hran. Hrana je dvojprvkovy seznam napr \[\[1,4],\[2,3],\[3,4],\[4,5]] proskrtej hrany = gen hrany hrany gen [] _ = [] gen (x:xs) hrany| projdi x vrcholy hrany = gen xs hrany| otherwise = x: g xs hrany projdi _ [] _ = False projdi [x,y] [a:as] hrany| (member [x,a] hrany) && (member [a,y] hrany) = True| otherwise = projdi [x,y] as hrany Pozn.: neefektivni protoze se porad prochazeji hrany - lepsi reseni nagenerovat seznam naseledniku a predchudcu pro vsechny vrcholy Haskell 4: Na vstupu mame obdelniky(okna), mame zistit jestli nejake prekryvaji. type Rozmer = (Int,Int) type Obd = (Int,Int,Rozmer) data Maybe a = Nothing | Just a Ulohou bylo napsat funkci: prekryvaji :: \[Obd] ->Maybe (Obd,Obd) //dostane okna a vrati kolidujici dvojci Nevedel sem co je Maybe tak sem generoval seznam -> 4body prekryvaji [] = [] prekryvaji [x] = [] prekryvaji (x:xs) = (p x xs) ++ prekryvaji xs --vrati seznam oken ktere se prekryvaji p _ [] = [] p (a,b,(ar,br)) ((x,y(xr,yr)):zbytek)| ((x>a)&&(x<(a+ax))&&(y>b)&&(y<(b+bx))) || () || () || () = ( (a,b,(ar,br)), ((x,y(xr,yr)))) :p (a,b,(ar,br)) zbytek| otherwise = p (a,b,(ar,br)) zbytek <{/ForumPost}> <{ForumPost(poster="peterblack", timestamp=2008-05-17 16:21:51)}> hezky reseni... jenom otazka na 4 "|| () || () || ()" to jsou nejaky specialni haskellovsky kouzla nebo se ti nechtelo psat s podminkama? :) <{/ForumPost}> <{ForumPost(poster="lickra", timestamp=2008-05-17 16:43:07)}> za || () || () .... se doplni podminky pro ostatni rohy, to je test jestli nejaky roh je v tom druhem a obdelnik ma 4 rohy -> dalsi 3 testy <{/ForumPost}> <{ForumPost(poster="peterblack", timestamp=2008-05-17 16:47:37)}> jo no ale to nepokreje pripad pro tyhle dva obdelniky: +-+ +--|-|--+ | | | | +--|-|--+ +-+ reseni co jsem posilal ja by to snad melo zvladat... <{/ForumPost}> <{ForumPost(poster="bartolomej", timestamp=2008-05-18 22:53:09)}> My way: 3.) zmaz g = setDiff g \[(u,v) | (u,v)<-g,(a,x)<-g,(y,b)<-g,u==a,x==y,b==v] 4.) na styri porovnania: (kx1 < zx2) || (ky1 < zy2) || (kx2 < zx1) || (ky2 < zy1) <{/ForumPost}>