Deklaratív programozás nagyzárthelyi, 2005. április 22. ======================================================= 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. | ?- Z = 1+2, A is Z+1, A = 6-2. no 1b. | ?- append([_,A],[_|_],[a,2,3]). A = 2 ? 1c. | ?- Z =:= 3+1, A is Z*2. ! Instantiation error 1d. | ?- D is 6-1, \+ D > 0. no 1e. | ?- A+B=3*4/2+1. A = 3*4/2, B = 1 ? 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. [A,2+4|D] = .(A,.(+(2,4),D)) .(4,[B+A,e]) = .(4,.(+(B,A),.(e,[]))) Az egyesítés eredménye: A = 4, B = 2, D = [e] 2b. r(A+4*5,[3,B|C], s) = r(+(A,*(4,5)),.(3,.(B,C)),s) r(B,[_,_],A) = r(B,.(_,.(_,[])),A) Az egyesítés eredménye: A = s, B = s+4*5, 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 Mindösszesen max 9 pont 3. Tegyük fel, hogy az alábbi programot betöltöttük a Prolog rendszerbe. p([A,B,C|_], R, E) :- R < A+B, E is R*10+C. p([_|Xs], R, E) :- p(Xs, R, E). Á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,2,4], 2, X). 24 3b. | ?- p([1,5], 5, X). {no} 3c. | ?- p([3,2,4,2], 0, X). 4 ; 2 3d. | ?- p([1,5,3,4,4,5], 6, X). 64 ; 64 ; 65 3e. | ?- p([1,1,4,5,3,2,1,6], 4, X). 45 ; 43 ; 42 ; 41 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! ... amelyet megelőző két elem összege pozitív. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont Mindösszesen max 8 pont 4.Egy K-V alakú struktúrát párnak hívunk. Két pár első tagjainak összegét kulcsösszegnek hívjuk. Két pár távolságán a második tagjaik különbségének abszolútértékét értjük. Írjon olyan Prolog-eljárást "kozelebb" néven, amely egy K-V alakú párokból álló listát kap bemenetként és kimenetként felsorolja azon szomszédos párok kulcsösszegét, amely párok távolsága kisebb, mint egy előre megadott érték (az eljárás második argumentuma)! Segédeljárást definiálhat, ha ad hozzá fejkommentet. | ?- kozelebb([1-4], 2, E). no | ?- kozelebb([1-4,3-5], 2, E). E = 4 ; no | ?- kozelebb([1-4,2-7,3-5], 2, E). no | ?- kozelebb([3-4,1-6,10-6], 1, E). E = 11; no | ?- kozelebb([1-4,2-5,5-11,6-7,2-8], 5, E). E = 3 ; E = 11 ; E = 8 ; no Egy megoldás: kozelebb([A-B,C-D|_], T, K) :- Tav is abs(D-B), % vagy simán: abs(D-B) < T Tav < T, K is A+C. kozelebb([_|As], T, K) :- kozelebb(As, T, K). Ö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([A|_],[d,_,r],[1,d,A,r]). A = 1 ? 1b. | ?- E is 3+1, Z is 5-1, E = Z. E = 4, Z = 4 ? 1c. | ?- Z is B+1, B = 2. ! Instantiation error 1d. | ?- A = 2, \+ A = 1. A = 2 ? 1e. | ?- K = 2, U = K+3, U = 5 no 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. f([1,A],3,_) = f(.(1,.(A,[])),3,_) f([A|B],3,1) = f(.(A,B),3,1) Az egyesítés eredménye: A = 1, B = [1] 2b. [f(B,3+b+B)|[A,C]] = .(f(B,+(+(3,b),B)),.(A,.(C,[]))) .(f(c,C+A),D) = .(f(c,+(C,A)),D) Az egyesítés eredménye: A = c, B = c, C = 3+b, D = [c,3+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([A,B,C|_], R, E) :- R > A+B, E is 100*R+C. r([_|Xs], R, E) :- r(Xs, R, E). Á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,3], 5, X). {no} 3b. | ?- r([1,3,1], 7, X). 701 3c. | ?- r([1,-3,-2,-5], 0, X). -2 ; -5 3d. | ?- r([4,5,1,2,3,6], 4, X). 403 3e. | ?- r([1,4,6,2,5,1,1,7,1], 8, X). 806 ; 801 ; 801 ; 807 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! Írja le azt is, hogy az eljárás milyen sorrendben állítja elő a megoldásokat! ... ... amelyet megelőző két elem összege negatív. Pontozás: 3a.-d. minden helyes válaszért 1 pont 3e. 2 pont 3f. 2 pont Mindösszesen max 8 pont 4. Egy K-V alakú struktúrát párnak hívunk. Két pár első tagjainak szorzatát kulcsszorzatnak hívjuk. Két pár távolságán a második tagjaik különbségének abszolútértékét értjük. Írjon olyan Prolog-eljárást "tavolabb" néven, amely egy K-V alakú párokból álló listát kap bemenetként és kimenetként felsorolja azon szomszédos párok kulcsszorzatát, amely párok távolsága nagyobb, mint egy előre megadott érték (az eljárás második argumentuma)! Segédeljárást definiálhat, ha ad hozzá fejkommentet. | ?- tavolabb([1-2,3-6], 1, E). E = 3; no | ?- tavolabb([1-2,3-4,4-8], 1, E). E = 3 ; E = 12 ; no | ?- tavolabb([1-2,4-4], 3, E). no | ?- tavolabb([3-2,1-2, 4-8], 3, E). E = 4; no | ?- tavolabb([4-2,6-5,4-8,6-7,2-10], 2, E). E = 24 ; E = 24 ; E = 12 ; no Egy megoldás: tavolabb([A-B,C-D|_], T, K) :- Tav is abs(D-B), % vagy simán: abs(D-B) > T Tav > T, K is A*C. tavolabb([_|As], T, K) :- tavolabb(As, T, K). Összpontszám: 8 pont Nem követelmény a hatékony program.