Programozási paradigmák, nagyzárthelyi, 1999. december 17. 17.30--19.00 Munkaidő: 90 perc, összpontszám: 60 Prolog, ,,A'' csoport (30 pont) A Prolog eljárás megírását kérő feladatokban a jegyzetben szereplő összes Prolog eljárás (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá fejkommentet; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat (pl. az append eljárás felesleges használatát)! 1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha igen, milyen behelyettesítéssel! (3 pont) f(1*Y-U, [V], V*U) f(A-3, B, A) 2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek csúcsaiban célsorozatok vannak és két csúcs között akkor megy él, ha a kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel eljuthatunk a cél csúcs célsorozatába. Az élek a redukció során alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük. Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres célsorozatot tartalmazó leveleinél jelezze a visszalépést! (Az append és a write szavakat rövidítheti (a ill. w).) (7 pont) | ?- append([A|B], C, [1,2]), write([A|B]-C). Az append/3 eljárás definíciója: (1) append([], L, L). (2) append([X|T], L, [X|R]) :- append(T, L, R). 3. Írjon olyan Prolog eljárást, amely előfordulási sorrendben felsorolja egy nem-negatív egészekből álló lista közeli elemeit! Két elem közeli, ha egymás mellett vannak a listában és különbségük abszolút értéke kisebb, mint 2. (7 pont) % :- pred kozeli(list(int)::in, int::out, int::out). % kozeli(L, A, B): A és B az L lista közeli elemei. | ?- kozeli([1,2,3,5,8,6,7], A, B). A = 1, B = 2 ? ; A = 2, B = 3 ? ; A = 6, B = 7 ? ; no 4. Írjon olyan Prolog eljárást, amely egy csupa egynél nagyobb egészt tartalmazó lista olyan folytonos részlistáit gyűjti össze egy listába, amelyek szorzata egy megadott számmal egyenlő. (13 pont) % :- pred szorzat(list(int)::in, int::in, list(list(int))::out). % szorzat(L, Sz, Rk): Az Rk olyan listák listája, amelyek % mindegyike L folytonos része és az elemeik szorzata Sz. | ?- szorzat([3,2,3,4], 6, L). L = [[3,2],[2,3]] ? ; no Programozási paradigmák, nagyzárthelyi, 1999. december 17. 17.30--19.00 Munkaidő: 90 perc, összpontszám: 60 Standard ML, ,,A'' csoport (30 pont) Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédfüggvényt definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a függvény típusát és írja le a függvény argumentumai és az eredménye közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 5. Deklaráljon SML-jelöléssel egy olyan bináris fát, amelynek a csomópontjaiban egész értékek vannak, a levelei pedig valós értékeket tartalmaznak vagy üresek! Rajzoljon fel egy olyan bináris fát, amely az alábbi értékeket tartalmazza tetszőleges sorrendben, majd írja le a fát a most deklarált új adattípus adatkonstruktoraival! (4 pont) Az ábrázolandó értékek: 2, 3, 4, 6, 1.3, 5.0, 9.9 6. Írjon olyan SML-függvényt osszeg néven, amely egy bináris fában, ahol a levelekben és a csomópontokban egész számok vannak, kiszámítja a bal részfa bal szélső elemétől a jobb részfa bal szélső eleméig haladó élsorozat mentén kiolvasható egész számok összegét! (6 pont) A fa és a megírandó függvény típusa: datatype fa = L of int | N of fa * int * fa (* osszeg f = az f fa bal részfájának bal szélső elemétől jobb részfájának bal szélső eleméig haladó élsorozat mentén kiolvasható egész számok összege osszeg : fa -> int *) Példák: osszeg(L 1) = 1 osszeg(N(L 1, 2, L 3)) = 6 osszeg(N(N(L 1, 2, L 3), 4, N(N(L 5, 6, L 7), 8, N(L 9, 10, L 11)))) = 26 7. Mi a típusa az alábbi v1, v2, v3 SML-értékeknek? Az a)--c) deklarációk egymástól függetlenek. (7 pont) A map és a String.tokens függvények típusa: map : ('a -> 'b) -> 'a list -> 'b list String.tokens : (char -> bool) -> string -> string list a) val v1 = let val cs = explode "ejnye" in map ord cs end b) fun v2 h y = h y y c) val v3 = fn ls => map String.tokens ls 8. Írjon SML-függvényt szorlista néven, amely egy csupa egynél nagyobb egészt tartalmazó lista olyan folytonos részlistáit gyűjti össze egy listába, amelyek elemeinek szorzata a megadott számmal egyenlő! (13 pont) (* szorlista(ns, s) = a pozitív egészeket tartalmazó ns lista olyan folytonos részlistáinak listája, amelyek elemeinek szorzata s szorlista : int list * int -> int list list *) Példák: szorlista([2,3,4,5,6], 6) = [[2, 3], [6]] szorlista ([], 1) = [] Programozási paradigmák, nagyzárthelyi, 1999. december 17. 17.30--19.00 Munkaidő: 90 perc, összpontszám: 60 Prolog, ,,B'' csoport (30 pont) A Prolog eljárás megírását kérő feladatokban a jegyzetben szereplő összes Prolog eljárás (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá fejkommentet; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat (pl. az append eljárás felesleges használatát)! 1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha igen, milyen behelyettesítéssel! (3 pont) [f(B*2, C, [B|A]),_] [f(Y*Y, 3, X)|X] 2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek csúcsaiban célsorozatok vannak és két csúcs között akkor megy él, ha a kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel eljuthatunk a cél csúcs célsorozatába. Az élek a redukció során alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük. Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres célsorozatot tartalmazó leveleinél jelezze a visszalépést! (Az append és a write szavakat rövidítheti (a ill. w).) (7 pont) | ?- append(A, [B|C], [d,t]), write(A-[B|C]). Az append/3 eljárás definíciója: (1) append([], L, L). (2) append([X|T], L, [X|R]) :- append(T, L, R). 3. Írjon olyan Prolog eljárást, amely előfordulási sorrendben felsorolja egy nem-negatív egészekből álló lista hasonló elemeit! Két elem hasonló, ha egymás mellett vannak a listában és azonos a paritásuk (egyenlőek modulo 2). (7 pont) % :- pred hasonlo(list(int)::in, int::out, int::out). % hasonlo(L, A, B): A és B az L lista hasonló elemei. | ?- hasonlo([1,2,3,5,8,6,7], A, B). A = 3, B = 5 ? ; A = 8, B = 6 ? ; no 4. Írjon olyan Prolog eljárást, amely egy csupa pozitív egészt tartalmazó lista olyan folytonos részlistáit gyűjti össze egy listába, amelyekre igaz, hogy első elemük megegyezik a többi elemeik összegével. (13 pont) % :- pred osszeg(list(int)::in, list(list(int))::out). % osszeg(L, Rk): Az Rk olyan listák listája, amelyek % mindegyike L folytons része és az első elemük egyenlő a többi % elemeik összegével. | ?- osszeg([2,1,1,4,3,1,7], L). L = [[2,1,1],[1,1],[4,3,1]] ? ; no Programozási paradigmák, nagyzárthelyi, 1999. december 17. 17.30--19.00 Munkaidő: 90 perc, összpontszám: 60 Standard ML, ,,B'' csoport (30 pont) Az SML-függvény megírását kérő feladatokban a jegyzetben szereplő összes SML-függvény (akár beépített, akár a jegyzetben definiált) szabadon használható. Ha segédfüggvényt definiál, feltétlenül adjon meg hozzá (deklaratív) fejkommentet, azaz specifikálja a függvény típusát és írja le a függvény argumentumai és az eredménye közötti kapcsolatot; enélkül a megoldás nem értékelhető, vagy csak csökkentett pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra; használjon jobbrekurziót, kerülje a felesleges hívásokat. 5. Deklaráljon SML-jelöléssel egy olyan bináris fát, amelynek a csomópontjai valós értéket tartalmaznak vagy üresek, a leveleiben pedig egész értékek vannak! Rajzoljon fel egy olyan bináris fát, amely az alábbi értékeket tartalmazza tetszőleges sorrendben, majd írja le a fát a most deklarált új adattípus adatkonstruktoraival! (4 pont) Az ábrázolandó értékek: 2, 3, 4, 6, 7, 1.3, 5.0, 9.9 6. Írjon olyan SML-függvényt szorzat néven, amely egy bináris fában, ahol a levelekben és a csomópontokban egész számok vannak, kiszámítja a bal részfa jobb szélső elemétől a jobb részfa jobb szélső eleméig haladó élsorozat mentén kiolvasható egész számok szorzatát! (6 pont) A fa és a megírandó függvény típusa: datatype fa = L of int | N of int * fa * fa (* szorzat f = az f fa bal részfájának jobb szélső elemétől jobb részfájának jobb szélső eleméig haladó élsorozat mentén kiolvasható egész számok szorzata szorzat : fa -> int *) Példák: szorzat(L 1) = 1 szorzat(N(2, L 1, L 3)) = 6 szorzat(N(1, N(2, L 3, L 4), N(5, N(6, L 7, L 8), N(9, L 10, L 11)))) = 3960 7. Mi a típusa az alábbi v1, v2, v3 SML-értékeknek? Az a)--c) deklarációk egymástól függetlenek. (7 pont) A map és a o függvények típusa: map : ('a -> 'b) -> 'a list -> 'b list o : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b a) val v1 = (real(ord #"A"), chr(floor 65.0)) b) val v2 = fn (g, x) => g x x c) val v3 = fn ls => map (op o) ls 8. Írjon SML-függvényt osszlista néven, amely egy csupa pozitív egészeket tartalmazó lista olyan folytonos részlistáit gyűjti össze egy listába, amelyeknek első eleme megegyezik a többi elemük összegével! (13 pont) (* osszlista ns = a pozitív egészeket tartalmazó ns lista olyan folytonos részlistáinak listája, amelyeknek első eleme egyenlő a többi elemük összegével osszlista : int list -> int list list *) Példák: osszlista([9,6,3,2,1,1]) = [[9, 6, 3], [6, 3, 2, 1], [3, 2, 1], [2, 1, 1], [1, 1]] osszlista [1,1,1] = [[1, 1], [1, 1]] osszlista [] = []