od Sharduk » 26. 5. 2014 18:18
Dnešní zadání bylo následující:
Prolog:
1) Definujte predikát orez(+Strom,+D,+H,-VStrom), který ve Stromu ponechá pouze uzly V, že D <= V <= H. Už bylo min 2x.
2) Máme neorientovaný graf bez smyček, reprezentovaný pomocí seznamu sousedů. Napište predikát trojuhelniky(G,V), který ve V vrátí seznam všech trojúhelníků (třech vrcholů, které mezi sebou všechny mají hrany). Trojúhelníky by se v seznamu neměly opakovat.
Př:
Kód: Vybrat vše
troj([a->[b,c,d],b->[c,a],c->[b,d,a],d->[a,c],e->[]],V).
V = [troj(a,b,c),troj(a,c,d)]
1) Násobení řídkých polynomů -> mějme řídké polynomy reprezentované pomocí [(nenulový koeficient,exponent)]. Definujte pro ně datový typ (nezapomeňte na nulový polynom) a napište funkci mult (i její datovou signaturu), která bude řídké polynomy násobit.
Kdo neví (jako já jsem nevěděl
) co je řídký polynom -> u spousty exponentů je nulový koeficient (exponenty prostě nejdou po 1, ale skáčou), ty samozřejmě nejsou v dané reprezentaci.
Kód: Vybrat vše
data Ridky a = Ridky [(Int,Int)] | Void
Postup: vynásobit všechno se všim, posčítat závorky se stejným exponentem.
2) Definujte funkci fold a listy, bla bla, to byl hnus! Viz zde příklad 3:
http://forum.matfyz.info/viewtopic.php? ... tem#p33954
Big One:
Mějme x1..xn, y1..yn posloupnosti, P cenu vyškrtnutí, I a J maximální počet po sobě jdoucích vyškrtnutí (pro posloupnost x resp y). Představte si, že jsou posloupnosti pod sebou a nyní máte prvky z x spárovat s y přímkami tak, že se nikde nic nekříží. V posloupnostech můžete vyškrtávat prvky, abyste je nemuseli párovat. Pro spárované xi s yi je cena abs(xi - yi). Pro celé možné spárování je tedy cena součet cen párů + (počet vyškrtnutých znaků * P). Najděte spárování s nejmenší cenou.
Můj postup: vygeneruju si všechny možnosti vyškrtnutí pro x a y -> zazipuju [zip a b | a <- moznosti x [argumenty], y <- moznosti y [argumenty] ]. Doporučuju si v generovaných možnostech v posledním prvku držet penalizaci za vyškrtávání. Pak zjistím nejnižší cenu takových spárování a vyhodím všechny (oni chtěli jen jedno), které tuto cenu má.
Snad je to srozumitelný, kdybyste měli nějakej dotaz, tak napište.
Celkově slušný, až na ten fold příklad. Dvořák byl v pohodě, Hric prý taky, a celkově to šlo
O dvou vím, že neprošli malou písemku, ale jinak snad všichni v cajku.
Dnešní zadání bylo následující:
[b]Prolog:[/b]
1) Definujte predikát orez(+Strom,+D,+H,-VStrom), který ve Stromu ponechá pouze uzly V, že D <= V <= H. Už bylo min 2x.
2) Máme neorientovaný graf bez smyček, reprezentovaný pomocí seznamu sousedů. Napište predikát trojuhelniky(G,V), který ve V vrátí seznam všech trojúhelníků (třech vrcholů, které mezi sebou všechny mají hrany). Trojúhelníky by se v seznamu neměly opakovat.
Př:
[code]troj([a->[b,c,d],b->[c,a],c->[b,d,a],d->[a,c],e->[]],V).
V = [troj(a,b,c),troj(a,c,d)]
[/code]
[b]Haskell:[/b]
1) Násobení řídkých polynomů -> mějme řídké polynomy reprezentované pomocí [(nenulový koeficient,exponent)]. Definujte pro ně datový typ (nezapomeňte na nulový polynom) a napište funkci mult (i její datovou signaturu), která bude řídké polynomy násobit.
Kdo neví (jako já jsem nevěděl :D ) co je řídký polynom -> u spousty exponentů je nulový koeficient (exponenty prostě nejdou po 1, ale skáčou), ty samozřejmě nejsou v dané reprezentaci.
[code]data Ridky a = Ridky [(Int,Int)] | Void
Postup: vynásobit všechno se všim, posčítat závorky se stejným exponentem.
[/code]
2) Definujte funkci fold a listy, bla bla, to byl hnus! Viz zde příklad 3: http://forum.matfyz.info/viewtopic.php?f=169&t=8281&p=33954&hilit=item#p33954
[b]Big One:[/b]
Mějme x1..xn, y1..yn posloupnosti, P cenu vyškrtnutí, I a J maximální počet po sobě jdoucích vyškrtnutí (pro posloupnost x resp y). Představte si, že jsou posloupnosti pod sebou a nyní máte prvky z x spárovat s y přímkami tak, že se nikde nic nekříží. V posloupnostech můžete vyškrtávat prvky, abyste je nemuseli párovat. Pro spárované xi s yi je cena abs(xi - yi). Pro celé možné spárování je tedy cena součet cen párů + (počet vyškrtnutých znaků * P). Najděte spárování s nejmenší cenou.
[u]Můj postup[/u]: vygeneruju si všechny možnosti vyškrtnutí pro x a y -> zazipuju [zip a b | a <- moznosti x [argumenty], y <- moznosti y [argumenty] ]. Doporučuju si v generovaných možnostech v posledním prvku držet penalizaci za vyškrtávání. Pak zjistím nejnižší cenu takových spárování a vyhodím všechny (oni chtěli jen jedno), které tuto cenu má.
Snad je to srozumitelný, kdybyste měli nějakej dotaz, tak napište.
Celkově slušný, až na ten fold příklad. Dvořák byl v pohodě, Hric prý taky, a celkově to šlo :) O dvou vím, že neprošli malou písemku, ale jinak snad všichni v cajku.