Deklaratív programozás nagyzárthelyi Budapest, 2004. március 22. ==================================== SML megoldások, V1.3, dp04s-zh1-mlmegol.txt =========================================== ------------------- A csoport ------------------- 5. Az alábbi, egymástól független, szintaktikailag helyes SML-kifejezésekben kifejezésenként két-két hiba van. Mik ezek? (a) [1*2, round 7.3, 3*7<>7*3.0] - különböző típusú elemek (int, bool) vannak a listában - a 7*3.0 kifejezésben int helyett real típusú szám kell (b) (#"a", 3=2, 12) = (ord 97, true, 5+7) - az ord függvény argumentuma rossz típusú - az ord függvény egész értéket adna eredményül, és emiatt a két hármas első tagjának eltérő a típusa (c) map (fn (x,y) => x+y) [3.0, 4.0, real 5.0] - a listaelemek típusa nem jó, mert a névtelen függvény párokat vár - a real függvény argumentumának nem jó a típusa Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Az 5.b esetben két pontot ér az is, ha egynek tekinti a kettős hibát. Az 5.c esetben a névtelen függvény mint hibaok megtalálása 1 pontot, a hiba pontosabb megfogalmazása 2 pontot ér. 6. Mi a k értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::_::k::_) = tl(tl(explode "vAlToGaTvA")) k = #"o" : char (b) val k = map (fn x => x mod 3) [1,7,3,5] k = [1, 1, 0, 2] : int list (c) val (_::_::k) = List.filter Char.isUpper (explode "vAlToGaTvA") k = [#"G", #"T", #"A"] : char list Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7. Nézzük a következő függvények definícióját! fun comb (x::xs, y::ys) = (x, y) :: comb(ys, xs) | comb _ = [] fun f zs = map (fn (a,b) => a+b) (comb(zs, tl zs)) (a) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése után? (a1) val x = f [1,2,3,4,5] x = [3, 5, 7, 9] : int list (a2) val x = f [~1] x = [] : int list (a3) val x = f [~1,1] x = [0] : int list (a4) val x = f [] az mosml hibát jelez (b) Mutassa be a comb([1,2,3,4], [2,3,4]) függvényalkalmazás egyszerűsítési lépéseit, mohó kiértékelést feltételezve! comb([1,2,3,4], [2,3,4]) --> (1,2) :: comb([2,3,4], [3,4]) --> (1,2) :: (2,3) :: comb([3,4], [4]) --> (1,2) :: (2,3) :: (3,4) :: comb([4], []) --> (1,2) :: (2,3) :: (3,4) :: [] --> ... --> [(1,2),(2,3),(3,4)] Pontozás (összesen max. 7 pont): 7.a Minden helyes válaszért 1-1 pont. 7.b Helyes válaszért 3 pont. A 7.b esetén nem elvárás az ennyire részletes kifejtés. 8. Ö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 SML-függvényt osszkul néven, amelynek eredménye egy egészlistában lévő összeg- és különbséghármasok száma. Segédfüggvényt definiálhat (fejkommenttel!). (* osszkul : int list -> int osszkul zs = a zs-beli összeg- és különbséghármasok száma *) Példák: osszkul [1,2,3] = 1; osszkul [1,2,~1] = 1; osszkul [1,2,3,~1] = 2; osszkul [1,2,3,~1,2] = 3; osszkul [1,2,3,~1,4] = 3; osszkul [1,1] = 0; osszkul [] = 0; osszkul [0,1,1,2,3,5,8] = 5; Egy megvalósítása: fun osszkul (x::y::z::xs) = (if x+y=z orelse x-y=z then 1 else 0) + osszkul (y::z::xs) | osszkul xs = 0 Megjegyzés: Három olyan szomszédos elemet, amely egyszerre összeg- és különbséghármas is (pl. [1,0,1]), csak egyszer kell számításba venni. Ha valaki kétszer számolja, nem hiba (inkább dicséretet érdemel)! fun osszkul (x::y::z::xs) = (if x+y=z andalso x-y=z then 2 else if x+y=z orelse x-y=z then 1 else 0) + osszkul (y::z::xs) | osszkul xs = 0 Pontozás (összesen max. 9 pont): Minden kisebb hibáért 1-1 pont, minden súlyos hibáért 2 vagy 3 pont levonás. Súlyos hibának számít pl. az else ág elhagyása (-2 pont) vagy a végtelen rekurzió (-3 pont). Nem követelmény a hatékony program. ------------------- B csoport ------------------- 5. Az alábbi, egymástól független, szintaktikailag helyes SML-kifejezésekben kifejezésenként két-két hiba van. Mik ezek? (a) [1*2, real 7, 3*7<>7*3] - különböző típusú (int, real, bool) elemek vannak a listában (b) (65, 3<>2, round 5.0) = (chr #"A", false, 5) - a chr függvény argumentuma rossz típusú - a chr függvény karaktert adna eredményül, és emiatt a két hármas első tagjának eltérő a típusa (c) List.filter (fn x => x) [real 3.0, 4.0, 5.0] - az (fn x => x) függvény a lista elemeire alkalmazva nem bool típusú értéket ad eredményül - a real függvény argumentuma nem jó típusú Pontozás (összesen max. 7 pont): 5.a - 5.c Helyes válasz 2-2-3 pont. Az 5.a esetben az ér két pontot, ha a hallgató észrevette, hogy három különböző típusú kifejezés van a listában Az 5.b esetben két pontot ér az is, ha egynek tekinti a kettős hibát. Az 5.c esetben a névtelen függvény mint hibaok megtalálása 1 pontot, a hiba pontosabb megfogalmazása 2 pontot ér. 6. Mi a k értéke az alábbi, egymástól független deklarációk kiértékelése után? (a) val (_::k::_::_) = tl(explode "vAlToGaTvA") k = #"l" : char (b) val k = map (fn x => x div 3) [7,9,3,5] k = [2, 3, 1, 1] : int list (c) val (_::_::k) = List.filter Char.isLower (explode "vAlToGaTvA") k = [#"o", #"a", #"v"] : char list Pontozás (összesen max. 7 pont): 6.a - 6.c Helyes válasz 2-2-3 pont. A feladatokban csak a kifejezések értékét kérdezzük, a típusukat nem! 7. Nézzük a következő függvények definícióját! fun bine (r::rs, s::ss) = (s, r) :: bine(rs, ss) | bine _ = [] fun f zs = map (fn (a,b) => a-b) (bine(zs, tl zs)) (a) Mi az x értéke az alábbi, egymástól független deklarációk kiértékelése után? (a1) val x = f [1,2,3,4,5] x = [1, 1, 1, 1] : int list (a2) val x = f [~1] x = [] : int list (a3) val x = f [~1,1] x = [2] : int list (a4) val x = f [] az mosml hibát jelez (b) Mutassa be a bine([1,2,3,4], [2,3,4]) függvényalkalmazás egyszerűsítési lépéseit mohó kiértékelést feltételezve! bine([1,2,3,4], [2,3,4]) --> (2,1) :: bine([2,3,4], [3,4]) --> (2,1) :: (3,2) :: bine([3,4], [4]) --> (2,1) :: (3,2) :: (4,3) :: bine([4], []) --> (2,1) :: (3,2) :: (4,3) :: [] --> ... --> [(2,1),(3,2),(4,3)] Pontozás (összesen max. 7 pont): 7.a Minden helyes válaszért 1-1 pont. 7.b Helyes válaszért 3 pont. A 7.b esetén nem elvárás az ennyire részletes kifejtés. 8. 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 SML-függvényt pozneg néven, amelynek eredménye egy egészlistában lévő poz2neg1- és neg2poz1-hármasok száma. Segédfüggvényt definiálhat (fejkommenttel!). (* pozneg : int list -> int pozneg zs = a zs-beli poz2neg1- és neg2poz1-hármasok száma *) Példák: pozneg [0,1,~1] = 1; pozneg [~1,~2,1] = 1; pozneg [0,1,~1,~2,3] = 2; pozneg [0,1,~1,2,3,~4] = 2; pozneg [1,1] = 0; pozneg [~1,2,~3,4,~5,6] = 0; pozneg [] = 0; Egy megvalósítása: fun pozneg (x::y::z::xs) = (if x>=0 andalso y>=0 andalso z<0 orelse x<0 andalso y<0 andalso z>=0 then 1 else 0) + pozneg (y::z::xs) | pozneg xs = 0 Megjegyzések: 1) Egy poz2neg1 vagy neg2poz1 hármas megtalálásakor kettőt is lehet lépni a listában: fun pozneg (x::y::z::xs) = if x>=0 andalso y>=0 andalso z<0 orelse x<0 andalso y<0 andalso z>=0 then 1 + pozneg (z::xs) else 0 + pozneg (y::z::xs) | pozneg xs = 0 2) Bár a példák szerint a feladatban a 0-t pozitív számnak tekintjük, elfogadható, ha valaki matematika tanulmányaira hivatkozva sem pozitívnak, sem negatívnak nem veszi. Ilyenkor a megoldás egyszerűbb: fun pozneg (x::y::z::xs) = if x*y>0 andalso x*z<0 then 1 + pozneg (z::xs) else 0 + pozneg (y::z::xs) | pozneg xs = 0 vagy akár fun pozneg (x::y::z::xs) = (if x*y>0 andalso x*z<0 then 1 else 0) + pozneg (y::z::xs) | pozneg xs = 0 3) Érdemes a pozneg [~1,~2,~1] = 0 tesztesetre is megvizsgálni a megoldásokat. Pontozás (összesen max. 9 pont): Minden kisebb hibáért 1-1 pont, minden súlyos hibáért 2 vagy 3 pont levonás. Súlyos hibának számít pl. az else ág elhagyása (-2 pont) vagy a végtelen rekurzió (-3 pont). Nem követelmény a hatékony program.