[Zk] 16.5.2008
[Zk] 16.5.2008
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
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
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: [Zk] 16.5.2008
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)
A od kolegy reseni 4:
a Hric je pomerne hodnej pan...nevim proc me vzdycky tak desil
pro zajimavost moje reseni 2:
(zachovava poradi)
Kód: Vybrat vše
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).
Kód: Vybrat vše
type Rozmer = (Int, Int)
type Obd = (Int, Int, Rozmer)
prekryti :: [Obd] -> Maybe (Obd,Obd)
prekryti sObd
| (seznamKolizi == []) = Nothing
| otherwise = Just (head seznamKolizi)
where
seznamKolizi = [(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 False
else False
where
kx1 = zx1 + xz1
ky1 = zy1 + yz2
kx2 = zx2 + xz2
ky2 = 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))]
Naposledy upravil(a) peterblack dne 17. 5. 2008 16:22, celkem upraveno 1 x.
Re: [Zk] 16.5.2008
PROLOG: Hladovym algoritmem pomoci heuristiky najit minimalne obarbeni grafu.
Pozn.: Neni to uplne hladovy algoritmus, najdem vsechny barvy kteryma muzeme barvit a vyberem tu nejmensi, ale hricovi to nevadilo
Druhe reseni vic hladovejsi
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]
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]]
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
Kód: Vybrat vše
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]
Druhe reseni vic hladovejsi
Kód: Vybrat vše
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).
Kód: Vybrat vše
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).
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]]
Kód: Vybrat vše
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
Kód: Vybrat vše
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
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: [Zk] 16.5.2008
hezky reseni...
jenom otazka na 4 "|| () || () || ()" to jsou nejaky specialni haskellovsky kouzla nebo se ti nechtelo psat s podminkama?
jenom otazka na 4 "|| () || () || ()" to jsou nejaky specialni haskellovsky kouzla nebo se ti nechtelo psat s podminkama?
Re: [Zk] 16.5.2008
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
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: [Zk] 16.5.2008
jo no ale to nepokreje pripad pro tyhle dva obdelniky:
reseni co jsem posilal ja by to snad melo zvladat...
Kód: Vybrat vše
+-+
+--|-|--+
| | | |
+--|-|--+
+-+
Re: [Zk] 16.5.2008
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)
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)