Deklaratív programozás nagyzárthelyi, 2005. május 35. ===================================================== 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 keletkező valtozó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- Y is 2*3, Z = Y+1. Y = 6, Z = 6+1 ? 1b. | ?- [A,B] = [x,y,z]. no 1c. | ?- X+Y = 2+3*4. X = 2, Y = 3*4 ? 1d. | ?- X = 2*4, \+ X = 8. X = 2*4 ? 1e. | ?- X =:= 3*4. ! 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. f([U|V],1+2+3) = f(.(U,V),+(+(1,2),3)) f([a,b],X+Y) = f(.(a,.(b,[])),+(X,Y)) Az egyesítés eredménye: U = a, V = [b], X = 1+2, Y = 3 2b. [f(A+C,B),A|B] = .(f(+(A,C),B),.(A,B)) [f(2*3+4,[p,q])|Z] = .(f(+(*(2,3),4),.(p,.(q,[]))),Z) Az egyesítés eredménye: A = 2*3, B = [p,q], C = 4, Z = [2*3,p,q] 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|_], Y, X) :- X > Y. p([_,X|L], _, Z) :- p(L, X, Z). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az X 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([], 3, X). {no} 3b. | ?- p([3], 1, X). 3 3c. | ?- p([1,2,4], 5, X). 4 3d. | ?- p([3,1,2,7], 1, X). 3 ; 2 3e. | ?- p([2,5,3,4,7,3,5,8], 0, X). 2 ; 7 ; 5 Tekintse a fenti p/3 eljárásra épülő alábbi p/2 eljárást: % p(L, Y): Az L listának Y egy olyan eleme,.... p([X|L], Y) :- p(L, X, Y). 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! Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! ... amely páros indexű helyen áll (az indexeket 1-től számozva) és nagyobb az előző helyen álló elemnél. Az eljárás az elemeket balról jobbra sorolja fel. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont 4. Egy számlistában csúcsnak hívunk három szomszédos elemet, ha az első és a harmadik kisebb a másodiknál. Írjon olyan Prolog eljárást csucsa néven, amely balról jobbra haladva felsorolja egy számlistában levő csúcsokat! A három szomszédos elemet egy cs/3 funktorú struktúraként adja vissza! Segédeljárást nem definiálhat. % csucsa(+L, -Cs): Cs egy cs/3 funktorú struktúra, amely az L számlistában % levő csúcsot ír le. L bemenő, Cs kimenő paraméter. | ?- csucsa([1,2,3], Cs). => no | ?- csucsa([1,2,3,1,4,2], Cs). => Cs = cs(2,3,1) ? ; Cs = cs(1,4,2) ? ; no | ?- csucsa([1,2,3,-3,2,1,0,2,7,5,8,9,1], Cs). => Cs = cs(2,3,-3) ? ; Cs = cs(-3,2,1) ? ; Cs = cs(2,7,5) ? ; Cs = cs(8,9,1) ? ; no Egy megoldás: csucsa([X,Y,Z|_L], cs(X,Y,Z)) :- Y > X, Y > Z. csucsa([_|L], Cs) :- csucsa(L, Cs). Összpontszám: 8 pont Nem követelmény a hatékony program. Pluszfeladat: Írjon az alábbi fejkommentnek megfelelő Prolog eljárást! Segédeljárást definiálhat, de fejkommentet feltétlenül adjon meg hozzá. % csucsa(+L, -I, -Cs): Cs az L számlista I.-edik csúcsa. L bemenő, I és Cs kimenő. | ?- csucsa([1,2,3,-3,2,1,0,2,7,5,8,9,1], I, Cs). => I = 1, Cs = cs(2,3,-3) ? ; I = 2, Cs = cs(-3,2,1) ? ; ... Egy megoldás: csucsa(L, I, Cs) :- csucsa(L, 1, I, Cs). % csucsa(+L, +I0, -I, -Cs): Cs az L számlista (I-I0+1)-edik csúcsa. csucsa([X,Y,Z|L], I0, I, Cs) :- ( Y > X, Y > Z -> ( I = I0, Cs = cs(X,Y,Z) ; I1 is I0+1, csucsa([Z|L], I1, I, Cs) ) ; csucsa([Y,Z|L], I0, I, Cs) ). ------------------- 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. | ?- Z is Y+1, Y is 2*3. ! Instantiation error 1b. | ?- [U|V] = [a,b]. U = a, V = [b] ? 1c. | ?- X*Y = 2+3*4. no 1d. | ?- X is 1+2, X+9 =:= 3*4. X = 3 ? 1e. | ?- F*G = a*b*c. F = a*b, G = c ? 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. [U,1*2*3|V] = .(U,.(*(*(1,2),3),V)) [a,X*Y,c] = .(a,.(*(X,Y),.(c,[]))) Az egyesítés eredménye: U = a, V = [c], X = 1*2, Y = 3 2b. f(W+a*b,[2|Z]) = f(+(W,*(a,b)),.(2,Z)) f(P+Q,[P,Q,s]) = f(+(P,Q),.(P,.(Q,.(s,[])))) Az egyesítés eredménye: P = 2, Q = a*b, W = 2, Z = [a*b,s] 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|_], Y, X) :- X =< Y. r([X,_|L], _, Z) :- r(L, X, Z). Állapítsa meg, hogy a feltett kérdésekre válaszul a rendszer milyen behelyettesítést ad az X 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([], 3, X). {no} 3b. | ?- r([3], 4, X). 3 3c. | ?- r([2,3,4], 5, X). 2 3d. | ?- r([3,1,2,7], 7, X). 3 ; 2 3e. | ?- r([5,2,8,4,7,3,4,2], 9, X). 5 ; 7 ; 4 Tekintse a fenti eljárásra épülő alábbi eljárást: % r(L, Y): Az L listának Y egy olyan eleme,.... r([X|L], Y) :- r(L, X, Y). 3f. Írja le az r/2 eljárás jelentését deklaratív módon, azaz egészítse ki teljes kijelentő mondattá a fenti fejkommentet! Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! ... amely páros indexű helyen áll (az indexeket 1-től számozva) és kisebb-egyenlő a kettővel előző helyen álló elemnél (kivétel a 2. helyen álló elem, amelynek az 1. elemnél kell kisebb-egyenlőnek lennie). Az eljárás az elemeket balról jobbra sorolja fel. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont (a kivétel megadása nélkül is jár a teljes pontszám) 2+1 pont (a kivételes eset megadása esetén) 4. Egy számlistában kútnak hívunk három szomszédos elemet, ha az első és a harmadik ugyanannyival nagyobb a második elemnél. Írjon olyan Prolog eljárást kutja néven, amely balról jobbra haladva felsorolja egy számlistában levő kutakat! A három szomszédos elemet egy k/3 funktorú struktúraként adja vissza! Segédeljárást nem definiálhat. % kutja(+L, -K): K egy k/3 funktorú struktúra, amely az L számlistában % levő kutat ír le. L bemenő, K kimenő paraméter. | ?- kutja([1,2,3], K). => no | ?- kutja([3,1,3,2], K). => K = k(3,1,3) ? ; no | ?- kutja([1,2,3,-3,3,1,0,1,-5,1,9], K). => K = k(3,-3,3) ? ; K = k(1,0,1) ? ; K = k(1,-5,1) ? ; no Egy megoldás: kutja([X,Y,Z|_L], k(X,Y,Z)) :- Y < X, X-Y =:= Z-Y. kutja([_|L], K) :- kutja(L, K). Összpontszám: 8 pont Nem követelmény a hatékony program. Pontszámcsökkenés nélkül elfogadható, ha az Y < X feltétel nem szerepel. Pluszfeladat: Írjon az alábbi fejkommentnek megfelelő Prolog eljárást! Segédeljárást definiálhat, de fejkommentet feltétlenül adjon meg hozzá. % kutja(+L, -I, -K): K az L számlista I.-edik kútja. L bemenő, I és K kimenő. | ?- kutja([1,2,3,-3,3,1,0,1,-5,1,9], I, K). => I = 1, K = k(3,-3,3) ? ; I = 2, K = k(1,0,1) ? ; ... A pluszfeladatra egy megoldás: kutja(L, I, K) :- kutja(L, 1, I, K). % kutja(+L, +I0, -I, -K): K az L számlista (I-I0+1)-edik kútja kutja([X,Y,Z|L], I0, I, K) :- ( Y < X, X-Y =:= Z-Y -> ( I = I0, K = k(X,Y,Z) ; I1 is I0+1, kutja([Z|L], I1, I, K) ) ; kutja([Y,Z|L], I0, I, K) ).