Deklaratív programozás nagyzárthelyi, 2002. március 25. ==================================================== Javítási kulcsok ================ ------------------- 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. | ?- I is 3*4, J =:= I+1. hiba (Instantiation error) 1b. | ?- U/V = a+b/2. meghiúsulás 1c. | ?- A = B+2, B is 3*2. A = 6+2, B = 6 1d. | ?- X is 2+2, X =:= 2*2. X = 4 1e. | ?- [G|H] = [a,b]. G = a, H = [b] 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. [X, X|Y] = .(X,.(X,Y)) [1+B, A+2*3, A] = .(+(1,B),.(+(A,*(2,3)),.(A,[]))) egyesítés eredménye: A = 1, B = 2*3, X = 1+2*3, Y = [1] 2b. .(f(K,a+b),[N|M]) = .(f(K,+(a,b)),.(N,M)) [N,f(1/2,L),K] = .(N,.(f(/(1,2),L),.(K,[]))) egyesítés eredménye: K = 1/2, L = a+b, M = [1/2], N = f(1/2,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. p([], X, X). p([X|L], X, X). p([X|L], _Y, 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([], a, X). ---> a 3b. p([a], a, X). ---> a;a 3c. p([a], b, X). ---> a 3d. p([a,b,b,c,d,e], a, X). ---> a;b;e 3e. p([a,b,b,b,c], b, X). ---> b;b;c 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|T], Y) :- p(T, X, Y). 3f. Egészítse ki teljes kijelentő mondattá a fenti fejkommentet! ... amely megegyezik a közvetlenül megelőző elemmel, vagy az utolsó helyen szerepel a listában. Egy szellemesen tömör hallgatói megoldás: ... amely elemet nem követ egy tőle különböző elem. Pontozás: 3a.-e. minden helyes válaszért 1 pont 3f. 2 pont 4. Egy nem negatív egész számokból álló listát (n,m) emelkedőnek hívunk, ha a 0 elemektől eltekintve kizárólag az n+1, n+2, ... , m (esetleg üres) számsorozatot tartalmazza, ebben a sorrendben. (Speciálisan: egy üres, vagy csak 0 számokat tartalmazó listát (n,n) emelkedőnek tekintünk, tetszőleges n esetén.) Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! Segédeljárást nem használhat! % emelkedo(+L, +N, ?M): L egy (N,M) emelkedő. Egy megoldás: % emelkedo(+L, +N, ?M): L egy (N,M) emelkedő. emelkedo([0|L], N, M) :- emelkedo(L, N, M). emelkedo([X|L], N, M) :- X =:= N+1, emelkedo(L, X, M). emelkedo([], N, N). Összpontszám: 9 pont Nem követelmény a hatékony program. 5. Mi az f típusa az alábbi (egymástól független) deklarációkban? 5.a fun f x y = (x, y) f : 'a -> 'b -> 'a * 'b 5.b fun f (x, y) = x y f : ('a -> 'b) * 'a -> 'b 5.c fun f x y = y x f : 'a -> ('a -> 'b) -> 'b Pontozás: Részfeladatonként 3-3 pont, összesen 9 pont. 6. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 6.a val x = "csi" ^ implode [#"p",#"a"] x = "csipa" : string 6.b val x = List.filter (fn x => x > 0.0) [1.3, ~2.2, 3.0, 0.0] x = [1.3, 3.0] : real list 6.c val x = map op- [(5,2), (6,~3), (~4,~7), (1,1)] x = [3, 9, 3, 0] : int list Pontozás: Részfeladatonként 2-2 pont, összesen 6 pont. 7. Mit kap eredményül, ha az alábbi f függvényt a hat számjegyből álló, ÉÉHHNN alakban füzérként megadott SAJÁT születési dátumára alkalmazza (pl. f "820431")? Válaszát indokolja! fun f t = let fun g (x::y::zs) = if x < y then y::g(x::zs) else x::g(y::zs) | g zs = zs : char list in implode(g(explode t)) end Pl. f "820431" = "824310" Általánosan: Az explode a t füzért (string) karakterek listájává alakítja. A g függvény a buborékrendezés egy lépését hajtja végre, azaz a lista első elemét addig viszi hátrafele, amíg egy nála kisebbet nem talál, vagy a lista végére nem ér; az első esetben a kisebb elemmel folytatja. Az implode a g függvény eredményét ismét füzérré alakítja; a füzérben a legkisebb (kódú) karakter az eredeti füzérhez képest a jobb szélen van. Összpontszám: 6 pont. 8. Adott egy valós számokat tartalmazó lista. Írjon függvényt intRat néven egy olyan lista előállítására, amelyben az argumentumlista egész értékű elemei az eredménylista elején, nem egész értékű elemei pedig az eredménylista végén vannak, tetszőleges sorrendben. Javaslat: az egész értékű valós számokat felismerő kifejezésben használja a round és real függvényeket. Egy megoldás: (* intRat : real list -> real list intRat xs = olyan lista, amelynek az elején az xs egész értékű, a végén pedig a nem egész értékű elemei vannak, tetszőleges sorrendben *) local fun iR (_, [], zs) = zs | iR (p, y::ys, zs) = if p y then iR(p, ys, y::zs) else iR(p, ys, zs) in fun intRat xs = iR(fn x => real(round x) = x, xs, iR(fn x => real(round x) <> x, xs, [])) end Példák (az eredménylistákban az elemek sorrendje tetszőleges lehet!): intRat [] = []; intRat [2.0, 3.0, 1.0] = [1.0, 3.0, 2.0]; intRat [2.2, 3.1, 1.44] = [1.44, 3.1, 2.2]; intRat [2.0, 2.2, 1.44, 3.1, 1.0] = [1.0, 2.0, 3.1, 1.44, 2.2]; Egy másik megoldás: fun intRat xs = List.filter (fn x => real(round x) = x) xs @ List.filter (fn x => real(round x) <> x) xs Példák (az eredménylistákban az elemek sorrendje tetszőleges lehet!): intRat [] = []; intRat [2.0, 3.0, 1.0] = [2.0, 3.0, 1.0]; intRat [2.2, 3.1, 1.44] = [2.2, 3.1, 1.44]; intRat [2.0, 2.2, 1.44, 3.1, 1.0] = [2.0, 1.0, 2.2, 1.44, 3.1]; Összpontszám: 9 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. | ?- a*b+2 = C+D. C = a*b, D = 2 1b. | ?- [X,Y|Z] = [a,b,c]. X = a, Y = b, Z = [c] 1c. | ?- P is [1,2], P = [1,2]. hiba (Domain error) 1d. | ?- U = 1, U is U+1. meghiúsulás 1e. | ?- S is 2*4, T = S+2. S = 8, T = 8+2 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. .(X, [4/2+Y, Y]) = .(X,.(+(/(4,2),Y),.(Y,[]))) [U+1,X|V] = .(+(U,1),.(X,V)) egyesítés eredménye: U = 4/2, V = [1], X = 4/2+1, Y = 1 2b. f(.(a/b,U), [1,V,V*c]) = f(.(/(a,b),U),.(1,.(V,.(*(V,c),[])))) f(W, [S|W]) = f(W,.(S,W)) egyesítés eredménye: S = 1, U = [a/b*c], V = a/b, W = [a/b,a/b*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([X|_], [X|_], X). p([_|L1], [_|L2], X) :- p(L1, L2, X). Á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], X). ---> {no} 3b. p([a], [a], X). ---> a 3c. p([b,d], [c,d], X). ---> d 3d. p([a,b,d], [a,c,d], X). ---> a;d 3e. p([a,b,b,b,c,d], [b,c,b,a,c,d], X). ---> b;c;d 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(L, Y) :- p(L, [_|L], Y). 3f. Egészítse ki teljes kijelentő mondattá a fenti fejkommentet! ... amely megegyezik a közvetlenül megelőző elemmel, vagy az első helyen szerepel a listában. Pontozás: 3a.-e. minden helyes válaszért 1 pont 3f. 2 pont 4. Egy nem negatív egész számokból álló listát (n,m) lejtőnek hívunk, ha a 0 elemektől eltekintve kizárólag az n, n-1, ..., m (esetleg üres) számsorozatot tartalmazza, ebben a sorrendben. (Speciálisan: egy üres, vagy csak 0 számokat tartalmazó listát (n,m) lejtőnek tekintünk, ahol m=n+1, tetszőleges n esetén.) Írjon olyan Prolog eljárást, amely megfelel az alábbi fejkommentnek! Segédeljárást nem használhat! % lejto(+L, +N, ?M): L egy (N,M) lejtő. Egy megoldás: % lejto(+L, +N, ?M): L egy (N,M) lejtő. lejto([0|L], N, M) :- lejto(L, N, M). lejto([N|L], N, M) :- N > 0, N1 is N-1, lejto(L, N1, M). lejto([], N, M) :- M is N+1. Összpontszám: 9 pont Nem követelmény a hatékony program. Nem jár levonás azért, ha a második klózban az N > 0 vizsgálat elmarad. 5. Mi az f típusa az alábbi (egymástól független) deklarációkban? 5.a fun f (y, x) = (x, y) f : 'a * 'b -> 'b * 'a 5.b fun f (x, y) = y x f : 'a * ('a -> 'b) -> 'b 5.c fun f x y = x y f : ('a -> 'b) -> 'a -> 'b Pontozás: Részfeladatonként 3-3 pont, összesen 9 pont. 6. Mi az x értéke és típusa az alábbi (egymástól független) deklarációkban? 6.a val x = implode(#"p" :: #"a" :: explode "csi") x = "pacsi" : string 6.b val x = map op^ [("al","ma"), ("kar","fa"), ("al","fa")] x = ["alma", "karfa", "alfa"] : string list 6.c val x = List.filter (fn x => x) [3.0>4.0, 4.7>2.4, ~3.0<=0.4, 0.7>=6.0] x = [true, true] : bool list Pontozás: Részfeladatonként 2-2 pont, összesen 6 pont. 7. Mit kap eredményül, ha az alábbi f függvényt a hat számjegyből álló, ÉÉHHNN alakban füzérként megadott SAJÁT születési dátumára alkalmazza (pl. f "820431")? Válaszát indokolja! fun f t = let fun h (u::v::ws) = if v >= u then u::h(v::ws) else v::h(u::ws) | h ws = ws : char list in implode(h(explode t)) end Pl. f "820431" = "204318" Általánosan: Az explode a t füzért (string) karakterek listájává alakítja. A h függvény a buborékrendezés egy lépését hajtja végre, azaz a lista első elemét addig viszi hátrafele, amíg egy nála nagyobbat nem talál, vagy a lista végére nem ér; az első esetben a nagyobb elemmel folytatja. Az implode a h függvény eredményét ismét füzérré alakítja; a füzérben a legnagyobb (kódú) karakter az eredeti füzérhez képest a jobb szélen van. Összpontszám: 6 pont. 8. Adott egy előjeles egész számokat tartalmazó lista. Írjon függvényt posNeg néven egy olyan lista előállítására, amelyben az argumentumlista nemnegatív elemei az eredménylista elején, negatív elemei pedig az eredménylista végén vannak, tetszőleges sorrendben. Egy megoldás: (* posNeg : int list -> int list posNeg xs = olyan lista, amelynek az elején az xs nemnegatív, a végén pedig az xs negatív elemei vannak, tetszőleges sorrendben *) local fun pN (_, [], zs) = zs | pN (p, y::ys, zs) = if p y then pN(p, ys, y::zs) else pN(p, ys, zs) in fun posNeg xs = pN(fn x => x >= 0, xs, pN(fn x => x < 0, xs, [])) end Példák (az eredménylistákban az elemek sorrendje tetszőleges lehet!): posNeg [] = []; posNeg [~2, ~3, ~1] = [~1, ~3, ~2]; posNeg [2, 0, 1] = [1, 0, 2]; posNeg [~2, 2, ~1, ~3, 1] = [1, 2, ~3, ~1, ~2]; Egy másik megoldás: fun posNeg xs = List.filter (fn x => x >=0) xs @ List.filter (fn x => x < 0) xs Példák (az eredménylistákban az elemek sorrendje tetszőleges lehet!): posNeg [] = []; posNeg [~2, ~3, ~1] = [~2, ~3, ~1]; posNeg [2, 0, 1] = [2, 0, 1]; posNeg [~2, 2, ~1, ~3, 1] = [2, 1, ~2, ~1, ~3]; Összpontszám: 9 pont. Nem követelmény a hatékony program.