Deklaratív programozás nagyzárthelyi, 2004. március 24. ======================================================= 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 valtozók behelyettesítéseit! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- [_|Z]=[1,d,3]. ---> Z = [d,3] ? 1b. | ?- R is 3+1, Z = 2+2, Z is R. ---> no 1c. | ?- append([_,3|_],[a],[1,3,B]). ---> B = a ? 1d. | ?- Y is 3+4, Z =:= Y+1. ---> ! Instantiation error 1e. | ?- X = 3*5, \+ X = 15. ---> X = 3*5 ? 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. [A,b*c|D] = .(A,.(*(b,c),D)) [2*3,R,p] = .(*(2,3),.(R,.(p,[]))) Az egyesítés eredménye: A = 2*3, D = [p], R = b*c 2b. [[A+C|B],f(A,B,C)] = .(.(+(A,C),B),.(f(A,B,C),[])) [[1*2+3,p,q],Z] = .(.(+(*(1,2),3),.(p,.(q,[]))),.(Z,[])) Az egyesítés eredménye: A = 1*2, B = [p,q], C = 3, Z = f(1*2,[p,q],3) 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([K-V,_-Y|_], B, K-V) :- abs(V-Y) =< B. p([_|L], B, Z) :- p(L, B, 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([1-5], 3, X). {no} 3b. | ?- p([1-5,3-4], 1, X). 1-5 ? 3c. | ?- p([3-3,1-1,2-2], 4, X). 3-3 ? ; 1-1 ? 3d. | ?- p([5-6,1-9,6-9,e-10], 2, X). 1-9 ? ; 6-9 ? 3e. | ?- p([2-2,w-6,3-3,t-2,7-2,3-8,5-1,8-3], 2, X). 3-3 ? ; t-2 ? ; 5-1 ? Tekintse a fenti p/3 eljárásra épülő alábbi p/2 eljárást: % p(L, Z): Az X-Y alakú párokból álló 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! Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! ... amelynek 2. argumentuma aritmetikailag megegyezik az őt követő elem 2. argumentumával. 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. Összeghármasnak, ill. különbséghármasnak nevezzük egy egészlista három szomszédos elemét, ha közülük az első és a második összege, ill. különbsége a harmadikkal egyenlő. Írjon olyan Prolog eljárást osszkul néven, amely egy egészlistában lévő összeg- és különbséghármasokat sorolja fel, az előbbieket o(E1,E2,E3), míg az utóbbiakat k(E1,E2,E3) alakú struktúra formájában. Segédeljárást nem definiálhat! % osszkul(+L, -H): H egy az L egészlistában előforduló % összeg- vagy különbséghármas. L bemenő, H kimenő paraméter. | ?- osszkul([1,1], H). ----> no | ?- osszkul([1,2,1], H). ----> no | ?- osszkul([1,2,-1], H). ----> H = k(1,2,-1) ; no | ?- osszkul([1,2,3,-1], H). ----> H = o(1,2,3) ; H = k(2,3,-1) ; no | ?- osszkul([4,1,2,3,1,2], H). ----> H = o(1,2,3) ; H = k(3,1,2) ; no | ?- osszkul([1,2,-1,-1,-2,1,3], H). ----> H = k(1,2,-1) ; H = o(-1,-1,-2) ; H = k(-1,-2,1) ; no Egy megoldás: osszkul([X,Y,Z|_], o(X,Y,Z)) :- X+Y =:= Z. osszkul([X,Y,Z|_], k(X,Y,Z)) :- X-Y =:= Z. osszkul([_|L], H) :- osszkul(L, 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 valtozók behelyettesítéseit! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- U=3+3, V is U+1, W =:= 7. ---> ! Instantiation error 1b. | ?- [U|_] = [a,[b]]. ---> U = a ? 1c. | ?- I = 4+1, T is 7-2, I=T. ---> no 1d. | ?- append(A,[_,B],[k,f,t]). ---> A = [k], B = t ? 1e. | ?- A*B=a*2*b*4. ---> A = a*2*b, B = 4 ? 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. [[R,3|Z]|U] = .(.(R,.(3,Z)),U) [[a,3]|R+1] = .(.(a,.(3,[])),+(R,1)) Az egyesítés eredménye: R = a, U = a+1, Z = [] 2b. p(A,[[a,b]|C]) = p(A,.(.(a,.(b,[])),C)) p(f(1,2*4),[T|T]) = p(f(1,*(2,4)),.(T,T)) Az egyesítés eredménye: A = f(1,2*4), C = [a,b], T = [a,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. r([K-_,X-Y|_], B, X-Y) :- abs(K-X) >= B. r([_|L], B, Z) :- r(L, B, 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([1-5], 3, X). no 3b. | ?- r([1-5,3-4], 1, X). 3-4 ? ; 3c. | ?- r([3-3,1-1,2-2], 0, X). 1-1 ? ; 2-2 ? ; 3d. | ?- r([5-6,1-7,2-9,12-e], 2, X). 1-7 ? ; 12-e ? ; 3e. | ?- r([2-2,5-w,3-3,4-2,7-2,3-8,5-p,8-3], 3, X). 5-w ? ; 7-2 ? ; 3-8 ? ; 8-3 ? ; Tekintse a fenti eljárásra épülő alábbi eljárást: % r(L, Y): Az X-Y alakú párokból álló L listának Z egy olyan eleme,.... r(L, Z) :- r(L, 1, Z). 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! ... amelynek első argumentuma legalább 1-gyel eltér az őt követő elem első argumentumátó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. poz2neg1-hármasnak nevezzük egy egészlista három szomszédos elemét, ha közülük az első kettő pozitív, a harmadik pedig negatív szám. neg2poz1-hármasnak nevezzük azt a három szomszédos elemet, amelyek közül az első kettő negatív és a harmadik pozitív. Írjon olyan Prolog eljárást pozneg néven, amely egy egészlistában lévő poz2neg1-hármasokat és neg2poz1-hármasokat sorolja fel, az előbbieket ppn(E1,E2,E3) alakú, míg az utóbbiakat nnp(E1,E2,E3) struktúra formájában. Segédeljárást nem definiálhat! % pozneg(+L, -H): H egy az L egészlistában előforduló % poz2neg1- vagy neg2poz1-hármas. L bemenő, H kimenő paraméter. | ?- pozneg([1,1], H). no | ?- pozneg([1,2,0], H). no | ?- pozneg([1,2,-1], H). H = ppn(1,2,-1) ; no | ?- pozneg([-1,-2,3,4,-1], H). H = nnp(-1,-2,3) ; H = ppn(3,4,-1) ; no | ?- pozneg([4,1,2,-1,-2,1], H). H = ppn(1,2,-1) ; H = nnp(-1,-2,1) ; no | ?- pozneg([7,-1,1,2,-3,-1,4,1,5,-1,-1], H). H = ppn(1,2,-3) ; H = nnp(-3,-1,4) ; H = ppn(1,5,-1) ; no Egy megoldás: pozneg([X,Y,Z|_], ppn(X,Y,Z)) :- X > 0, Y > 0, Z < 0. pozneg([X,Y,Z|_], nnp(X,Y,Z)) :- X < 0, Y < 0, Z > 0. pozneg([_|L], H) :- pozneg(L, H). Összpontszám: 8 pont Nem követelmény a hatékony program.