Deklaratív programozás pótzárthelyi, 2004. november 25. ======================================================== Prolog megoldások ================= ------------------- A csoport ------------------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkezo valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezonek. 1a. | ?- append([_,a],[1,b,3],[3,A|_]). A = a ? 1b. | ?- [1,b] = [_|B]. B = [b] ? 1c. | ?- A = 11+1, A is 13-1. no 1d. | ?- X = 3, Y = 4, \+ X = Y. X = 3, Y = 4 ? 1e. | ?- Z=:=11+1, Z=12. Instantiation error Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi egyenlőségek bal- és jobboldalának alapstruktúra alakját, vagy rajzolja fel a fastruktúrájukat! Adja meg, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. f1(A,[b+3|D]) = f1(A,.(+(b,3),D)) f1(C,[b+C]) = f1(C,.(+(b,C),[])) Az egyesítés eredménye: A = 3, C = 3, D = [] 2b. [.(A,[])|[p(b+C),13+A]] = .(.(A,[]),.(p(+(b,C)),.(+(13,A),[]))) .([e],.(p(b+D),[D])). = .(.(e,[]),.(p(+(b,D)),.(D,[]))) Az egyesítés eredménye: A = e, C = 13+e, D = 13+e Pontozás: Minden helyes alapstruktúra-alak 1 pont, helytelen 0 pont (összesen max 4 pont). 2a. helyes egyesítés 2 pont 2b. helyes egyesítés 3 pont Mindösszesen max 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog rendszerbe. pf([_,_|L], L). p(L, B, A) :- pf(L, A), length(A, H), H > B. p([_|Xs], B, A) :- p(Xs, B, A). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az A változónak! Sorolja fel az összes megoldást, a rendszer által előállított sorrendben és írja le ezeket pontosvesszővel elválasztva! Ha nincs megoldás, írjon {no}-t! 3a. | ?- p([], 5, A). {no} 3b. | ?- p([1,3,2,3], 1, A). [2,3] 3c. | ?- p([0,4,0], 0, A). [0] 3d. | ?- p([1,1,2,4,5], 1, A). [2,4,5], [4,5] 3e. | ?- p([1,1,2,3,2,4,2], 2, A). [2,3,2,4,2], [3,2,4,2], [2,4,2] Tekintse a fenti eljárásra épülő alábbi eljárást: % p(L, A): Az L listának A ... p(L, A) :- length(L, H), H1 is H-3, p(L, H1, A). 3f. Írja le a p/2 eljárás jelentését deklaratív módon, azaz egészítse ki teljes kijelentő mondattá a fenti fejkommentet! ...az első két elem elhagyásával keletkező részlistája/farka. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont 4. Írjon olyan Prolog-eljárást pithagoraszi néven, amely bemenetként kap egy egészeket tartalmazó listát és kimenetként felsorolja azokat a szomszédos elemeket, amelyek rendezett pithagoraszi számhármast alkotnak! A kimenetet egy p/3 struktúrába csomagolva állítsa elő! Segédeljárást definiálhat, ha ad hozzá fejkommentet. | ?- pithagoraszi([1,3,4,5,6,7], P). P = p(3,4,5) | ?- pithagoraszi([1,4,3,5,3,7,24,25], P). P = p(7,24,25) | ?- pithagoraszi([7,24,25,5,16,63,65], P). P = p(7,24,25) ? ; P = p(16,63,65) | ?- pithagoraszi([3,4,5,12,13], P). P = p(3,4,5) ? ; P = p(5,12,13) | ?- pithagoraszi([-5,-4,-3], P). no Egy megoldás: pithagorasz([X,Y,Z|_], P) :- X > 0, Y > 0, Z > 0, Y > X, Z > Y, Z * Z =:= X*X + Y*Y, P = p(X,Y,Z). pithagorasz([_|Xs], P) :- pithagorasz(Xs, P). Összpontszám: 8 pont Nem követelmény a hatékony program. ------------------- B csoport ------------------- 1. Döntse el, mi lesz az alábbi Prolog kérdések eredménye (hiba, meghiúsulás, siker)! Siker esetén adja meg a keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- append([e,_],[1,b,3],[A,e|_]). A = e ? 1b. | ?- [1,c,2] = [_|E]. E = [c,2] ? 1c. | ?- A = 2+2, A is 4. no 1d. | ?- T =:= 19*3-2, A is 49+6, T=A. Instantiation error 1e. | ?- X = 1, \+ X = 2. X = 1 ? Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. 2. Írja fel az alábbi egyenlőségek bal- és jobboldalának alapstruktúra alakját, vagy rajzolja fel a fastruktúrájukat! Adja meg, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. t(A,[a+a|D]) = t(A,.(+(a,a),D)) t(C,[a+C,2]) = t(C,.(+(a,C),.(2,[]))) Az egyesítés eredménye: A = a, C = a, D = [2] 2b. [[A|[]]|[p(b*C),c+A]] = .(.(A,[]),.(p(*(b,C)),.(+(c,A),[]))) .([b],.(p(A*D),[D])) = .(.(b,[]),.(p(*(A,D)),.(D,[]))) Az egyesítés eredménye: A = b, C = c+b, D = c+b Pontozás: Minden helyes alapstruktúra-alak 1 pont, helytelen 0 pont (összesen max 4 pont). 2a. helyes egyesítés 2 pont 2b. helyes egyesítés 3 pont Mindösszesen max 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog rendszerbe. qf([_|L], L). q(L, B, A) :- qf(L, A), length(A, H), H >= B. q([_|Xs], B, A) :- q(Xs, B, A). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az A változónak! Sorolja fel az összes megoldást, a rendszer által előállított sorrendben és írja le ezeket pontosvesszővel elválasztva! Ha nincs megoldás, írjon {no}-t! 3a. | ?- q([], 1, A). no 3b. | ?- q([1,2,3], 2, A). [2,3] 3c. | ?- q([1,2,2,4], 3, A). [2,2,4] 3d. | ?- q([0,3,2], 1, A). [3,2], [2] 3e. | ?- q([1,3,2,5,3], 1, A). [3,2,5,3], [2,5,3], [5,3], [3] Tekintse a fenti eljárásra épülő alábbi eljárást: % q(L, A): Az L listának A ... q(L, A) :- length(L, H), H1 is H-1, q(L, H1, A). 3f. Írja le az q/2 eljárás jelentését deklaratív módon, azaz egészítse ki teljes kijelentő mondattá a fenti fejkommentet! ... a farka. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont 4. Írjon olyan Prolog-eljárást mertani néven, amely bemenetként kap egy egészeket tartalmazó listát és kimenetként felsorolja azokat a szomszédos elemeket, amelyek mértani számhármast alkotnak! A kimenetet egy m/3 struktúrába csomagolva állítsa elő! Segédeljárást definiálhat, ha ad hozzá fejkommentet. % mertani(+L, -M): Az L listában M egy mértani számhármas | ?- mertani([2,4,8], M). M = m(2,4,8) ? ; no | ?- mertani([2,4,8,8,8], M). M = m(2,4,8) ? ; M = m(8,8,8) ? ; no | ?- mertani([2,4,8,16], M). M = m(2,4,8) ? ; M = m(4,8,16) ? ; no | ?- mertani([1,3,12,48,16], M). M = m(3,12,48) ? ; no | ?- mertani([-2,-4,-8], M). no Egy megoldás: mertani([X,Y,Z|_], M) :- X > 0, Y > 0, Z > 0, Z mod Y =:= 0, Y mod X =:= 0, Z/Y =:= Y/X, M = m(X,Y,Z). mertani([_|Xs], M) :- mertani(Xs, M).