Deklaratív programozás pótzárthelyi, 2005. május 3. =================================================== 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 megnevezett változók behelyettesítéseit! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- X = 4+5, Z is X+1. X = 4+5, Z = 10 1b. | ?- append([m,R|_],[],[A,p,q]). A = m, R = p 1c. | ?- Z = 1+3, Z = X, \+ X = 4. X = 1+3, Z = 1+3 1d. | ?- X = a+b, Z is X - c. hiba 1e. | ?- A = 2, 1+5 = 4+A. meghiúsulás Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. Mindösszesen max 5 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, hogy a megnevezett változókra milyen behelyettesítéseket eredményeznek ezek az egyesítések! 2a. w(2+M,[K],c) = w(+(2,M),.(K,[]),c) w(K,[N],M) = w(K,.(N,[]),M) Az egyesítés eredménye: K = 2+c, M = c, N = 2+c 2b. [f(A,B),B*A+4,c-C|W] = .(f(A,B),.(+(*(B,A),4),.(-(c,C),W))) .(f(3,6),[C,_-_]) = .(f(3,6),.(C,.(-(_,_),[]))) Az egyesítés eredménye: A = 3, B = 6, C = 6*3+4, W = [] 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. p([X|_], B, Y) :- \+ X = B, Y = X. p([X|Xs], B, Y) :- abs(X) < B, C is -abs(X), p(Xs, C, Y). p([X|Xs], B, Y) :- abs(X) >= B, p(Xs, B, Y). Á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([2,3], 2, A). 3 3b. | ?- p([1,2], -3, A). 1 ; 2 3c. | ?- p([2,2,2], 2, A). {no} 3d. | ?- p([3,4,2,-6,-2], 3, A). 4 ; 2 ; -6 3e. | ?- p([5,3,-2,3,2,5,-2], 3, A). 5 ; -2 ; 3 ; 2 ; 5 Tekintse a fenti eljárásra épülő alábbi eljárást: % p(L, Z): Az L listának Z egy olyan eleme,.... p(L, Z) :- p(L, 0, Z). 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! ... amely nem 0. Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! balról jobbra. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont Mindösszesen max 8 pont 4. Egy egészeket tartalmazó listában három szomszédos elemet \emph{nagyhármasnak} hívunk, ha összegük nagyobb egy előre megadott értéknél. Írjon olyan \textbf{Prolog-eljárást} \texttt{nagyharmas} néven, amely egy egészekből álló listát és egy egész számot kap bemenetként és kimenetként egy \texttt{nh/3}-as struktúrába csomagolva felsorolja a nagyhármasokat! Egy megoldás: nagyharmas([F1,F2,F3|_], B, nh(F1,F2,F3)) :- F1 + F2 + F3 > B. nagyharmas([_|F], B, H) :- nagyharmas(F,B,H). Ö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 megnevezett változók behelyettesítéseit! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- append([1,6],[A|_],[_,6,7]). A = 7 1b. | ?- X is 4*2, Y is 1+1, X+Y=10. meghiúsulás 1c. | ?- X = 2, U is 4-X, \+ U = 3. U = 2, X = 2 1d. | ?- T = 1+1, G is T+1, G = 3. G = 3, T = 1+1 1e. | ?- S is S1+S1, S1 = S2, S2 = 6. ! Instantiation error Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. Mindösszesen max 5 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, hogy a megnevezett változókra milyen behelyettesítéseket eredményeznek ezek az egyesítések! 2a. d([U*V],1+U,W) = d(.(*(U,V),[]),+(1,U),W) d([2*3|[]], W+2, 1) = d(.(*(2,3),[]),+(W,2),1) Az egyesítés eredménye: U = 2, V = 3, W = 1 2b. [[A|B],B*A+4,_|T] = .(.(A,B),.(+(*(B,A),4),.(_,T))) .([a],[C,A,A]) = .(.(a,[]),.(C,.(A,.(A,[])))) Az egyesítés eredménye: A = a, B = [], C = []*a+4, T = [a] 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. r([X|_], B, Y) :- X < B, Y = X. r([X|Xs], B, Y) :- abs(X) >= B, r(Xs, B, Y). r([X|Xs], B, Y) :- abs(X) < B, C is -abs(X), r(Xs, C, Y). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad a B 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. | ?- r([5,4], 5, B). 4 3b. | ?- r([4,4], 4, B). {no} 3c. | ?- r([5,-4,3], 4, B). -4 ; 3 3d. | ?- r([1,-3,7,-4,5,-9], -2, B). -3 ; -4 ; -9 3e. | ?- r([-9,6,-8,3,11,2,-7], 8, B). -9 ; 6 ; -8 ; -7 Tekintse a fenti eljárásra épülő alábbi eljárást: % r(L, Z): Az L listának Z egy olyan eleme,.... r(L, Z) :- r(L, 0, Z). 3f. Írja le a r/2 eljárás jelentését deklaratív módon, azaz egészítse ki teljes kijelentő mondattá a fenti fejkommentet! ... ... amelyek negatívak. Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! ... balról jobbra. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont Mindösszesen max 8 pont 4. Egy egészeket tartalmazó listában három szomszédos elemet \emph{kishármasnak} hívunk, ha szorzatuk kisebb egy előre megadott értéknél. Írjon olyan \textbf{Prolog-eljárást} \texttt{kisharmas} néven, amely egy egészekből álló listát és egy egész számot kap bemenetként és kimenetként egy \texttt{kh/3}-as struktúrába csomagolva felsorolja a kishármasokat! Segédeljárást definiálhat, ha ad hozzá fejkommentet.\pont8 Egy megoldás: kisharmas([F1,F2,F3|_], B, kh(F1,F2,F3)) :- F1*F2*F3 < B. kisharmas([_|F], B, H) :- kisharmas(F,B,H). Összpontszám: 8 pont Nem követelmény a hatékony program.