Tak, jak si to ještě pamatuju:
Celkem 4 úlohy. První dvě za 10 bodů, další dvě za 15 bodů.
Zadání:
==========================================================================
10 bodů:
1) Rotace seznamů. Predikát Rotace(+Seznam,-RotovanySeznam) vydá na výstup
rotovaný seznam; rotaci provede v konstantním čase. Predikát přijímá i neúplně
definované struktury.
a) Vyjádřete seznam [1,2,3] jako neúplnou datovou strukturu.
b) Definujte predikát Rotace(+Seznam, -RotovanySeznam), který bude používat
neúplně definované struktury k rotaci daného seznamu.
2) Akumulátor. Predikát obsah(+SeznamVrcholu, -Obsah) spočítá obsah
mnohoúhelníka a je definován takto:
obsah([X],0).
obsah([v(X1,Y1),v(X2,Y2) | T ], Obsah):-
obsah([v(X2,Y2) | T], Temp),
Obsah is Temp + (X1 * Y2 + X2 * Y1)/2.
a)Definujte vlastní predikát, který bude používat akumulátor (a rekurzi použije
na konci těla predikátu).
b)Vysvětlete, proč je vaše řešení v a) efektivnější.
15 bodů:
3)Je zadán orientovaný ohodnocený graf pomocí seznamu vrcholů se seznami
následníků, tj např. [a-[b-1,c-2],b-[a-2]]. Definujte predikát
obratGraf(+OhodnocGraf,-ObracGraf), který otočí orientaci jednotlivých hran v
grafu, ale zachová jejich ohodnocení.
4)Je zadán seznam kladně a záporně ohodnocených výroků, tedy např. [a-true,
b-false, c-false]. Úkolem je definovat predikát
ohod2(+SeznamVyroku,-SeznamySDvemaZmenenymiVyroky), který vrátí seznam všech
seznamů, kde byly změněny ohodnocení právě dvou výroků.
==========================================================================
Na vypracování písemky jsme měli 65 minut. Řešení měla být čitelná a
strukturovaná.
U první úlohy mě kdyžtak někdo opravte, jestli mám
zadání správně... teď jsem si zpětně uvědomil, že jsem řešil úlohu jen pro
rozdílové seznamy, a normální jsem zapomněl na rozdílové převést.
U druhé úlohy si nejsem jistý ohledně seznamu.
A u čtvrté úlohy si já (a pár dalších lidí) není jistý, jak znělo zadání. Jde o
to, vrátit seznam všech možných seznamů, nebo stačí jen seznam s dvema
zmenenymi ohodnocenimi?
(Mám pocit ale, že opravdu seznam všech seznamů, protože na příkladu myslím
bylo jako možný výsledek V =
[[a-true,b-true,c-true],[a-false,b-true,c-false],[a-false,b-false,c-true]].)
Neprocedurální programování - písemka z Prologu 15.4.2010
- mifeet
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 27. 1. 2010 14:37
- Typ studia: Informatika Ph.D.
Re: Neprocedurální programování - písemka z Prologu 15.4.2010
Zadání si pamatuji stejně.
1) U prvního úkolu jsem taky použil jenom rozdílové seznamy, větu "Predikát přijímá i neúplně definované struktury" jsem pochopil tak, že převod na normální seznam není nutný.
2) U dvojky bylo v predikátu X1*Y2-X2*Y1 (místo X1*Y2+X2*Y1).
3) Myslím, že ukázkový vstup byl [a-[b/1,c/3],b-[a/2],c-[]]
4) Tady chtěli vrátit seznam všech ohodnocení, která se od původního liší v právě dvou hodnotách, tj. seznam seznamů. A ještě u toho byla poznámka, že na plný počet bodů je to třeba napsat bez bagof & spol.
Moje řešení:
1) U prvního úkolu jsem taky použil jenom rozdílové seznamy, větu "Predikát přijímá i neúplně definované struktury" jsem pochopil tak, že převod na normální seznam není nutný.
2) U dvojky bylo v predikátu X1*Y2-X2*Y1 (místo X1*Y2+X2*Y1).
3) Myslím, že ukázkový vstup byl [a-[b/1,c/3],b-[a/2],c-[]]
4) Tady chtěli vrátit seznam všech ohodnocení, která se od původního liší v právě dvou hodnotách, tj. seznam seznamů. A ještě u toho byla poznámka, že na plný počet bodů je to třeba napsat bez bagof & spol.
Moje řešení:
Kód: Vybrat vše
rotace(X-X,X-X) :- var(X). rotace([X|Xs]-Y,Xs-Z) :- var(Y),Y=[X|Z].
Kód: Vybrat vše
obsah(X,Y) :- obsah(X,0,Y). obsah([_],A,A). obsah([v(X1,Y1),v(X2,Y2)|Vs], A, Vysl):- A1 is A + (X1*Y2-X2*Y1)/2, obsah([v(X2,Y2)|Vs], A1, Vysl).
Kód: Vybrat vše
otoc(G,TG):- bezHran(G,BG), otocHrany(G,BG,TG). bezHran([],[]). bezHran([V-_|Xs], [V-[]|Ys]):-bezHran(Xs,Ys). otocHrany([], A, A):-!. otocHrany([V-Hrany|Vs], A, Vysl) :- pridejHrany(V,Hrany,A,A1), otocHrany(Vs, A1, Vysl). pridejHrany(_,[],G,G). pridejHrany(Kam,[V/Vaha|Vs],A,Vysl):- select(V-Hrany,A,A1), A2 = [V-[Kam/Vaha|Hrany]|A1], pridejHrany(Kam,Vs,A2,Vysl).
Kód: Vybrat vše
negace(true,false). negace(false,true). insert(X,Is,[X|Is]). ohod2([V1-H1,V2-H2],[[V1-NH1,V2-NH2]]):-negace(H1,NH1),negace(H2,NH2),!. ohod2([V1-H1|Vs],Vysl) :- negace(H1,NH1), ohod1(Vs,Ts1), maplist(insert(V1-NH1),Ts1,Vysl1), ohod2(Vs,Ts2), maplist(insert(V1-H1),Ts2,Vysl2), append(Vysl1,Vysl2,Vysl). ohod1([V1-H1],[[V1-NH1]]):-negace(H1,NH1),!. ohod1([V1-H1|Vs],Vysl):- negace(H1,NH1), Vysl1=[[V1-NH1|Vs]], ohod1(Vs,Ts), maplist(insert(V1-H1),Ts,Vysl2), append(Vysl1,Vysl2,Vysl).