Dnešní kombo Hric + Dvořák nám zadali následující příklady (některý recyklovaný, některý poupravený, některý zcela fresh):
Prolog
1)Prořezávání BVStromu
Binární vyhledávací strom (=BVS) reprezentovaný pomocí predikátů void/0 a t/3 (rekursivní struktura, navíc přirozená čísla ve vrcholech), dále přirozená čísla D a H zadány na vstupu. Prořezat tak, aby zůstal BVS právě jen s vrcholy s hodnotami ležícími mezi, tedy vrchol s hodnotou X zůstane iff D =< X =< H.
Příklad:
Kód: Vybrat vše
?- orez(t(
t(
void, 5, void
),
10,
t(
t(
void, 15, void
),
20,
t(
void, 30, void
),
),
), 10, 20, T).
T = t(void, 10, t(t(void, 15, void), 20, void)).
Obdélník (jakožto množina bodů včetně vnitřku a hranice) v rovině se stranami rovnoběžnými s osami je zadán pomocí predikátu o(X, Y, VX, VY), kde X, Y jsou souřadnice dolního levého rohu a VX, VY jeho rozměry. Dva obdélníky se protínají iff nejsou disjunktní jakožto množiny bodů (tj. jakékoli dotýkání se na hraně či v bodě se nepovažuje za nevhodné).
Na vstupu dostaneme seznam takovýchto a takto zadaných obdélníků, úkolem je backtrackingem postupně vydat všechny protínající se dvojice. Při dotazu se ukázalo, že je lepší vypsat bez opakování a v pořadí, v jakém jsou ve vstupním seznamu, tedy když se v seznamu [..., X, ... , Y] protínali, vypsat jen X-Y a ne ještě Y-X. Ale v zadání to explicitně nebylo, tak to v nejhorším šlo vynechat...
Příklad:
Kód: Vybrat vše
?- protinajiSe([o(0, 0, 1, 1), o(1, 1, 2, 3), o(2, 2, 3, 4)], V).
V = o(0, 0, 1, 1)-o(1, 1, 2, 3) ;
V = o(1, 1, 2, 3)-o(2, 2, 3, 4) ;
false.
3)Dělení na přihrádky
umisťování holubů do holubníků, zde prvků do intervalů
Zadány seřazené prvky (pravé okraje přihrádek) a prvky (samotní holubi). Rozdělte prvky (holubi) do přihrádek pomocí funkce
Kód: Vybrat vše
prihradky :: Ord a => [a] -> [a] -> [(a, [a])]
a) patří do přihrádky označené iff
b) patří do přihrádky označené iff
To vše ve tvaru (oznaceni_prihradky, [seznam_prvku_v_teto_prihradce]).
Pokud jsou nějaké prvky (nějací holubi) menší než , přidejte přihrádku , kde C je seznam těchto menších prvků.
Příklad:
Kód: Vybrat vše
> prihradky [2, 5, 11, 25] [10, 2, 1, 0, 3, 6, 30]
[(0, [1, 0], (2, [2, 3]), (5, [10, 6]), (11, []), (25, [30])]
Zadán hypergraf (viz http://cs.wikipedia.org/wiki/Hypergraf )
a) Navrhněte datovou reprezentaci hypergrafu v Haskellu, stylem HGraf a, kde a jsou datové typy vrcholů.
b) Navrhněte funkci
Kód: Vybrat vše
doplneni :: Eq a => HGraf a -> HGraf a
Příklad:
Do hypergrafu s vrcholy {1, 2, 3, 4, 5} a hyperhranami {{1, 4}, {4, 5, 2}, {3, 1, 2}} se doplní hrany {1, 5}, {4, 3} a {3, 5}.