zk 11.2.08

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ů.
zav1nac
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 11. 2. 2008 19:03
Typ studia: Informatika Bc.

zk 11.2.08

Příspěvek od zav1nac »

Prolog:
1.) Zisti ci ide efektivne graf ofarvit 2 farbami a vydajte toto ofarbenie

2.) J dany n-arny strom pri priechode preorder jako zoznam dvojic hodnota a pocet synu, listy maju pocet synov 0.Zrekonstruuj strom.

Haskell
3.) Mame zoznam hodnot. Vyrob efektivne zoznam trojic, tak ze ke kazde hodnote pridate najmensie cisla pred nim a najvecsie za nim

4.) Mame zoznam kladnych cisel xs delky n. Zistite zda ide rozdelit xs na n/3 trojic tak, aby kazda z trojic mala stejny sucet. Vydajte 1 ries, ak existuje

Teoria: Negacia v prologu a ake su s nou problemy cico

5.)Su dane dvojice ( v 2 jazykoch) veta a preklad jako dvojice zoznamov slov (slova su dalej nedelitelne). Najdite heuristiky co najlepsieho priradenia medzi jednotlivymi stavmi z oboch jazykov tak, aby suhlasily s prekladmi. Priradenie je obecne M : N, jedno slovo sa preklada viacerymi sposobmi oboma smermi. Pri idealnom priradeny ma kazde slovo vo vete prave 1 preklad. Tj chcete penalizovat tie priradenia, kedy slovo nema vo vete preklad alebo ich ma viacero. Veta a jej preklad su obecne rozne dlhe.


Nacrtnute riesenia:
1.) funguje len pre komponentu grafu ak vobec
% graf je zoznam vrcholov, a zoznam dvojic vrcholov co su hrany G = ([V],[(x,y)])

obarv(([X,Y|V],E),O) :- obar (E,[Y] , [X], [(X-1)], O).

obar(_,[],_,X,X).

obar(E, [X|Z], UzV, Uz , Ob) :-
okolie(X,E,O), %najde vsetkych susedov X
rozdiel(O,UzV,O1), %od O odobere UzV
pridaj(O1,Z,Z1),
pridaj(X,UzV,UzV1),
ofarbi(O1,Uz,F),
pridaj(Uz,(X-F),Uz1),
obar(E,Z1,UzV1,Uz1,Ob).

ofarbi( ([Y|O], Uz, 1):- ofar1([Y|O], Uz), !.
ofarbi( ( [Y|O], Uz, 0):- ofar0([Y|O], Uz).

ofar1([],_). %ofar0 podobne
ofar1([Y|O],Uz) :- notmember((Y-1),Uz), ofar1(O,Uz).


2.) % ten vstupny zoznam je asi [a-3,b-2,c-0,d-0,e-1,f-0,g-0,h-0]

makeTree ( [ Val-0|T], T, t(Val,[]) ).
makeTree ( [Val-N|T], Z, t(Val, Childs) ) :-
makeChild ( T, N, Z, Childs ).
makeChild ( T, 0, T, [] ).
makeChild ( T, N, Z, [C|Childs] ) :-
makeTree ( T, Zb, C ),
N1 = N – 1,
makeChild ( Zb, N1, Z, Childs).

3.)
vyrob3 (x:xs) mini = (x,mini,mx) : vyrob3 xs mn
where mn = min x mini
mx = maxS xs

maxS [] = 0
maxS [x] = x
maxS (x:xs) = max x maxS xs

run (x:xs) = vyrob3 (x:xs) x

4.) toto mam trosku inak spravene ale v pohode to zobral
perm xs = [ x:ps | (x:ys) <- xs, ps <- perm ys ]
check x:y:z:xs
| x + y + z == check xs
| otherwise = False

Run xs = [ p | p <- perm xs, check p]
Naposledy upravil(a) zav1nac dne 18. 2. 2008 22:24, celkem upraveno 1 x.
Uživatelský avatar
Santhos
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 8. 1. 2007 11:34

Re: zk 11.2.08

Příspěvek od Santhos »

hej kopirka, to jsou moje reseni! :D

jen bych dodal u tech haskellu bacha na odsazeni
Odpovědět

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