Prolog: Máme daný orientovaný graf reprezentovaný jako [vrchol-[seznam sousedů]|...], zjistěte, zda v něm je orientovaná kružnice, a pokud ano, vraťte vrcholy nějaké takové kružnice v tom pořadí, jak jsou na kružnici. Chce se polynomiální řešení.
Prolog: Máme daný BVS klastickým způsobem, tj např. t(t(nil,0,nil)1,nil) a číslo, máme vrátit strom stromovými rotacemi upravený tak, aby dané číslo, nachází-li se ve stromě, nebo nejblíže vyšší nebo nižší bylo v kořeni
Haskell: Tetris: Máme obdélníkovou tabulku uloženou po řádcích jako seznam seznamů Intů. Vymažte z ní všechny sloupce, které neobsahují žádnou nulu.
Haskell: Očíslování stromu jako čtvrtý příklad tady akorátže preorder, pozor na to, že strom je obecný (=ne binární).
Velký příklad: Odtamtéž, co 4., až na to, že komodity nemají určený cílový objem a cílem je maximalizovat součet toků. Řekli nám, že se jedná nejen o NP-úplnou úlohu, ale že i její bruteforce řešení je obtížné, proto není potřeba najít optimum, ale stačí nějaký tok, který nepůjde triviálně zlepšit. Tzn. například najít optimum pro jednu komoditu, zafixovat ji tak a hledat optimum pro druhou a tak dále je přijatelné řešení. Nevadilo jim exponenciální hledání zlepšujících cest, ikdyž to jde dělat lineárně.
Řešení
1)
removeVertex(_,[],[]). removeVertex(X,[X-_|T],T1):-removeVertex(X,T,T1). removeVertex(X,[X1-S|T],[X1-S1|T1]):-delete(X,S,S1),removeVertex(X,T,T1). cutTo(A,[A|_],[A]). %Vezme část seznamu až do prvního výskytu prvku A. cutTo(A,[B|Z],[B|Z1]:-A/=B,cutTo(A,Z,Z1). circle(G,C):-member(X-[],G),removeVertex(X,G,G1),!,circle(G1,C). %Odstraním z grafu všechny vrcholy s outdegree 0 circle([V-E|G],C):-circle_([V-E|G],[V],C). %V grafu bez vrcholů s outdegree 0 najdu kružnici na první pokus DFSkem circle_(G,[V|A],C):-member(V-E,G),member(V1,E),member(V1,[V|A]),!,cutTo(V1,[V|A],B),reverse(B,C). circle_(G,[V|A],C):-member(V-E,G),member(V1,E), circle_(G,[V1,V,|A],C).
splay(P,t(L,P,R),t(L,P,R)). splay(P,t(L,P1,nil),t(L,P1,nil)):-P>P1,!. splay(P,t(nil,P1,R),t(nil,P1,R)):-P<P1,!. splay(P,t(L,P1,R),T):-P<P1,splay(P,L,L1),rotRight(t(L1,P1,R),T). splay(P,t(L,P1,R),T):-P>P1,splay(P,R,R1),rotLeft(t(L,P1,R1),T). rotRight(t(t(A,B,C),D,E),t(A,B,t(C,D,E))). rotLeft(A,B):-rotRight(B,A).
filtrovatPodle::[a]->[Bool]->[a]
filtrovatPodle _ [] = []
filtrovatPodle [] _ = []
filtrovatPodle (a:as) (b:bs) |b = (a:(filtrovatPodle as bs))
|otherwise = filtrovatPodle as bs
vymazat::[[Int]]->[[Int]]
vymazat (a:as) = map (\x -> filtrovatPodle x mask) (a:as)
where mask = foldl (zipWith (||)) (map (=0) a) (map (map (=0)) as)
ocisluj::NT a->NT (a,Int)
ocisluj x = y
where (y,_)=ocislujSeZacatkem 1 x
ocislujSeZacatkem :: Int -> NT a -> (NT (a,Int),Int)
ocislujSeZacatkem x (N a p) = ((N (a,x) p1),n)
where (p1,n) = ocislujPole (x+1) p
ocislujpole :: Int -> [NT a] -> ([NT (a,Int)],Int)
ocislujpole x [] = ([],x)
ocislujpole x (a:as) =((b:bs),z)
where (b,x1) = ocislujSeZacatkem x a
(bs,z) = ocislujpole x1 as