od mathemage » 18. 9. 2012 21:22
Hola!
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)).
2)
Protínající se obdélníky
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.
Haskell
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])]
takto:
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])]
4)
Doplnění hran hypergrafu
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
která k zadanému hypergrafu přidá hrany (jako v normálním grafu, tedy dvojice vrcholů), jež spolu nejsou v 1 hyperhraně.
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}.
Hola!
Dnešní kombo Hric + Dvořák nám zadali následující příklady (některý recyklovaný, některý poupravený, některý zcela fresh):
[u]Prolog[/u]
1)[b]Prořezávání BVStromu[/b]
Binární vyhledávací strom (=BVS) reprezentovaný pomocí predikátů [i]void/0[/i] a [i]t/3[/i] (rekursivní struktura, navíc přirozená čísla ve vrcholech), dále přirozená čísla [i]D[/i] a [i]H[/i] 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 [i]D =< X =< H[/i].
Příklad:
[code]
?- 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)).
[/code]
2)[b]Protínající se obdélníky[/b]
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 [i]o(X, Y, VX, VY)[/i], kde [i]X, Y[/i] jsou souřadnice dolního levého rohu a [i]VX, VY[/i] 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. [size=50]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...[/size]
Příklad:
[code]
?- 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.
[/code]
[u]Haskell[/u]
3)[b]Dělení na přihrádky[/b]
[i]umisťování holubů do holubníků, zde prvků do intervalů[/i]
Zadány seřazené prvky [latex]b_1 < \dots < b_n[/latex] (pravé okraje přihrádek) a prvky [latex]c_1, \dots c_m[/latex] (samotní holubi). Rozdělte prvky (holubi) do přihrádek pomocí funkce
[code]prihradky :: Ord a => [a] -> [a] -> [(a, [a])][/code]
takto:
a) [latex]c_k[/latex] patří do přihrádky označené [latex]b_i[/latex] iff [latex]b_i \leq c_k < b_{i+1}[/latex]
b) [latex]c_k[/latex] patří do přihrádky označené [latex]b_n[/latex] iff [latex]b_n \leq c_k[/latex]
To vše ve tvaru [i](oznaceni_prihradky, [seznam_prvku_v_teto_prihradce])[/i].
Pokud jsou nějaké prvky (nějací holubi) menší než [latex]b_1[/latex], přidejte přihrádku [latex](c_{min}, C)[/latex], kde C je seznam těchto menších prvků.
Příklad:
[code]
> prihradky [2, 5, 11, 25] [10, 2, 1, 0, 3, 6, 30]
[(0, [1, 0], (2, [2, 3]), (5, [10, 6]), (11, []), (25, [30])]
[/code]
4)[b]Doplnění hran hypergrafu[/b]
Zadán hypergraf (viz [url]http://cs.wikipedia.org/wiki/Hypergraf[/url] )
a) Navrhněte datovou reprezentaci hypergrafu v Haskellu, stylem [i]HGraf a[/i], kde [i]a[/i] jsou datové typy vrcholů.
b) Navrhněte funkci
[code]doplneni :: Eq a => HGraf a -> HGraf a[/code]
která k zadanému hypergrafu přidá hrany (jako v normálním grafu, tedy dvojice vrcholů), jež spolu nejsou v 1 hyperhraně.
Příklad:
[i]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}.[/i]