Zkouška 26.5.2014 (Dvořák + Hric)

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
Sharduk
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 24. 1. 2012 12:12
Typ studia: Informatika Mgr.

Zkouška 26.5.2014 (Dvořák + Hric)

Příspěvek od Sharduk »

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)]
Haskell:

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.

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.
Odpovědět

Zpět na „PRG005 Neprocedurální programování“