Deklaratív programozás pótzárthelyi, 2003. május 6. =================================================== 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. | ?- [X,Y|Z] = [a,b,c]. X = a, Y = b, Z = [c] ? 1b. | ?- X = 2*3, \+ X = 6. X = 2*3 ? 1c. | ?- X =:= 3*2, X = 6. ! Instantiation error 1d. | ?- X*Y = a*b+c. no 1e. | ?- a-b-c = X-Y. X = a-b, Y = 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. [4/2+X,1] = .(+(/(4,2),X),.(1,[])) [Y+3|Z] = .(+(Y,3),Z) Az egyesítés eredménye: X = 3, Y = 4/2, Z = [1] 2b. f([a*b+c|U],V*W) = f(.(+(*(a,b),c),U),*(V,W)) f([K+L,L],K) = f(.(+(K,L),.(L,[])),K) Az egyesítés eredménye: K = a*b, L = c, U = [c], V = a, W = 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. p([X|_], X, X). p([X|L], Y, Z) :- Y1 is Y+X, p(L, Y1, 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([5], 3, X). {no} 3b. | ?- p([3,3], 0, X). 3 3c. | ?- p([1,2], 1, X). 1 ; 2 3d. | ?- p([1,3,4,10], 2, X). 3 ; 10 3e. | ?- p([0,2,4,6,1,13,26], 0, X). 0 ; 6 ; 13 ; 26 Tekintse a fenti p/3 eljárásra épülő alábbi p/2 eljárást: % p(L, X): Az L listának X egy olyan eleme,.... p(L, X) :- p(L, 0, X). 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 megegyezik az előtte álló elemek összegével. 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. Adott két, nem feltétlenül azonos hosszú lista. Írjon olyan Prolog eljárást fesult néven, amely balról jobbra haladva összefésüli a két listát! Az eredmény-lista elemei: az első lista 1. eleme, a második lista 1. eleme, az első lista 2. eleme, a második lista 2. eleme stb. Amikor az egyik bemenő lista elemei elfogynak, a másik lista fennmaradó elemeivel zárul az eredmény. Vigyázzon arra, hogy az eljárás ne adjon hamis illetve többszörös eredményt! Segédeljárást nem definiálhat. % fesult(+L1, +L2, -F): Az F lista az L1 és L2 listák összefésültje. | ?- fesult([], [], L). ----> L = [] ? ; no | ?- fesult([1,2], [3,4,5,6,7], L). ----> L = [1,3,2,4,5,6,7] ? ; no | ?- fesult([a,b,c,d], [e,f,g], L). ----> L = [a,e,b,f,c,g,d] ? ; no Egy megoldás: fesult([], L, L). fesult([X|L1], [Y|L2], [X,Y|L]) :- fesult(L1, L2, L). fesult(L, [], L) :- L = [_|_]. Ö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. | ?- X = 2+3, 5 = X. no 1b. | ?- Y is X+1, X is 3*4. ! Instantiation error 1c. | ?- [X|[Y]] = [a,b]. X = a, Y = b ? 1d. | ?- U is 2+4, V = U+2. U = 6, V = 6+2 ? 1e. | ?- P+Q = 48/12+3. P = 48/12, Q = 3 ? 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. h(X,[X,1]) = h(X,.(X,.(1,[]))) h(B+A,[8*2+1|C]) = h(+(B,A),.(+(*(8,2),1),C)) Az egyesítés eredménye: A = 1, B = 8*2, C = [1], X = 8*2+1 2b. [f(P,a*b),Q|R] = .(f(P,*(a,b)),.(Q,R)) [Q,f(6,S),S] = .(Q,.(f(6,S),.(S,[]))) Az egyesítés eredménye: P = 6, Q = f(6,a*b), R = [a*b], S = 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([X|L], _, Z) :- r(L, X, Z). r([X,Y|_], Z, X) :- 2*X =:= Y+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([2], 2, X). {no} 3b. | ?- r([2,3], 1, X). 2 3c. | ?- r([2,2,2], 2, X). 2 ; 2 3d. | ?- r([3,5,4,3], 1, X). 4 ; 3 3e. | ?- r([3,4,2,0,5,10,15,2], 2, X). 10 ; 5 ; 2 ; 3 Tekintse a fenti r/3 eljárásra épülő alábbi r/2 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 a 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 megegyezik az előtte és mögötte álló számok átlagával. Az eljárás az elemeket jobbról balra sorolja fel. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont 4. Adott két, nem feltétlenül azonos hosszú számlista. Írjon olyan Prolog eljárást osszeg néven, amely egy olyan listát állít elő, amely a két adott listának, mint vektornak az összege! Ha az adott listák nem azonos hosszúságuak, akkor a rövidebbik listát megfelelő számú 0-val kell a végén kiegészíteni. Tehát az eredmény-lista hossza a két adott lista hosszának maximuma. Vigyázzon arra, hogy az eljárás ne adjon hamis illetve többszörös eredményt! Segédeljárást nem definiálhat. % osszeg(+L1, +L2, -S): Az S lista az L1 és L2 listák összege. | ?- osszeg([], [], L). ---> L = [] ? ; no | ?- osszeg([1,2], [3,4,5,6,7], L). ---> L = [4,6,5,6,7] ? ; no | ?- osszeg([1,2,3,4], [5,6,7], L). ---> L = [6,8,10,4] ? ; no Egy megoldás: osszeg([], L, L). osszeg([X|L1], [Y|L2], [Z|L]) :- Z is X+Y, osszeg(L1, L2, L). osszeg(L, [], L) :- L = [_|_]. Összpontszám: 8 pont Nem követelmény a hatékony program.