Deklaratív programozás nagyzárthelyi Budapest, 2004. október 28. =========================== Prolog-megoldások, V1.2, dp04a-zh1-plmegol.txt ------------------- 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- [a,2,c]=[_|A]. A = [2,c] ? 1b. | ?- X = 1+1, \+X = 1+1. no 1c. | ?- append([_,A],[d],[c,d,A]). A = d ? 1d. | ?- A is 3+4, A =:= 7. A = 7 ? 1e. | ?- Y is A+4, A = 2. Instantiation error Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. Ö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, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. [B,f(b+C,E)] = .(B,.(f(+(b,C),E),[])) [C-3|[f(b+2,4)]] = .(-(C,3),.(f(+(b,2),4),[])) Az egyesítés eredménye: B = 2-3, C = 2, E = 4 2b. f(A,[p([1|B])|C]) = f(A,.(p(.(1,B)),C)) f(B+c,.(p([1,2]),[])) = f(+(B,c),.(p(.(1,.(2,[]))),[])) Az egyesítés eredménye: A = [2]+c, B = [2], C = [] 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 Ö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([a-7], 3, X). no 3b. | ?- p([r-7,3-9], 2, X). r-7 3c. | ?- p([4-4,1-1,2-2], 4, X). 4-4 ; 1-1 3d. | ?- p([5-6,1-7,t-7,e-10], 2, X). 5-6 ; 1-7 3e. | ?- p([1-2,w-6,3-6,t-2,7-2,r-8,5-8,8-3], 3, X). w-6 ; t-2 ; r-8 Tekintse a fenti eljárásra épülő alábbi eljárást: % p(L, Z): Az L listának a Z egy olyan eleme, ... p(L, Z) :- p(L, 0, Z). 3f. Írja le a q/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! Egy X-Y struktúra esetén X-re és Y-ra mint az X-Y pár első és második tagjára hivatkozhat. ... amely egy olyan párt alkot, amelynek a második tagja megegyezik a Z-t követő pár második tagjá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 Összesen max. 8 pont 4. Egy egészeket tartalmazó számlistában összegelemnek hívunk egy elemet, ha az egyenlő az előtte előforduló elemek összegével. Írjon olyan Prolog-eljárást osszegelem néven, amely bemenetként kap egy listát, és kimenetként felsorolja a benne szereplő összegelemeket! Segédeljárást definiálhat, ha ad hozzá fejkommentet. % osszegelem(+L, -O): az L listában az O egy összegelem | ?- osszegelem([0,1,6], O). => O = 0 ? ; no | ?- osszegelem([3,3,1,7], O). => O = 3 ? ; O = 7 ? ; no | ?- osszegelem([-1,2,1,-4,-2,2], O). => O = 1 ? ; O = -2 ? ; no Egy megoldás: osszegelem(Ls, Ossz) :- osszegelem(Ls, 0, Ossz). osszegelem([L|Ls], Gy, Ossz) :- ( L = Gy, Ossz = L ; NGy is Gy+L, osszegelem(Ls, NGy, Ossz) ). Nem követelmény a hatékony program. Pontozás: Fejkomment hiánya: -2 pont Felesleges klóz: -1, súlyosabb esetben -2 pont Kisebb hibák: hibánként -1 pont Végtelen rekurzió: -3 pont Összesen: max. 8 pont ------------------- 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ő változó-behelyettesítéseket! A kérdéseket egyenként és önmagukban adjuk át az értelmezőnek. 1a. | ?- [A|_]=[a,b,c]. A = a ? 1b. | ?- A*B=a+2*b*4. no 1c. | ?- A = 3+4, Z is A+2. A = 3+4, Z = 9 ? 1d. | ?- append([_,e|_],[4],[1,e,B]). B = 4 ? 1e. | ?- Z = 3+4, A is B+4, B = Z. Instantiation error Pontozás: 1.a-1.e Helyes válasz 1 pont, helytelen 0 pont. Ö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, milyen változó-behelyettesítéseket eredményeznek ezek az egyesítések! 2a. [A,3+a|B] = .(A,.(+(3,a),B)) .(a,[3+A]) = .(a,.(+(3,A),[])) Az egyesítés eredménye: A = a, B = [] 2b. z(A,.([a,c],C)) = z(A,.(.(a,.(c,[])),C)) z(f(1,a),[T]) = z(f(1,a),.(T,[])) Az egyesítés eredménye: A = f(1,a), C = [], T = [a,c] 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 Összesen max. 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog-rendszerbe. q([K-_,X-Y|_], B, X-Y) :- abs(K-X) >= B. q([_|L], B, Z) :- q(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. | ?- q([a-7], 3, X). no 3b. | ?- q([7-r,3-9], 2, X). 3-9 3c. | ?- q([4-4,1-1,2-2], 4, X). no 3d. | ?- q([5-6,1-7,7-t,8-e], 2, X). 1-7 ; 7-t 3e. | ?- q([1-2,6-w,3-6,2-t,7-2,8-r,13-8,10-3], 4, X). 6-w ; 7-2 ; 13-8 Tekintse a fenti eljárásra épülő alábbi eljárást: % q(L, Z): Az L listának a Z egy olyan eleme, ... q(L, Z) :- q(L, 0, Z). 3f. Írja le a q/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 egy olyan párt alkot, amelynek az első tagja esetleg különbözik a Z-t megelőző pár első tagjá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 Összesen max. 8 pont 4. Egy egészeket tartalmazó számlistában csúcselemnek hívunk egy elemet, ha az nagyobb, mint az előtte előforduló elemek összege. Írjon olyan Prolog-eljárást csucselem néven, amely bemenetként kap egy listát, és kimenetként felsorolja a benne szereplő csúcselemeket! Segédeljárást definiálhat, ha ad hozzá fejkommentet % csucselem(+L, -Cs): az L listában a Cs egy csucselem | ?- csucselem([1,-2], Cs). => Cs = 1 ? ; no | ?- csucselem([3,3,1,8], Cs). => Cs = 3 ? ; Cs = 8 ? ; no | ?- csucselem([-1,2,3,-4,-2,2], Cs). => Cs = 2 ? ; Cs = 3 ? ; Cs = 2 ? ; no Egy megoldás: csucselem(Ls, Ossz) :- csucselem(Ls, 0, Ossz). csucselem([L|Ls], Gy, Ossz) :- ( L > Gy, Ossz = L ; NGy is Gy+L, csucselem(Ls, NGy, Ossz) ). Nem követelmény a hatékony program. Pontozás: Fejkomment hiánya: -2 pont Felesleges klóz: -1, súlyosabb esetben -2 pont Kisebb hibák: hibánként -1 pont Végtelen rekurzió: -3 pont Összesen max. 8 pont