Programozási paradigmák, nagyzárthelyi, 1998. november 27. 15.00--16.30 (c) Szeredi Peter, 1994-1998 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. Prolog feladatok A csoport. 1. Írja fel az alábbi két Prolog kifejezés 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! f(2+2*X, .(U,V), U) f(A+B, [B,B], A*3) (3 pont) Megoldás: f(+(2, *(2, X)), .(U, V), U) f(+(A, B), .(B, .(B, [])), *(A, 3)) A = 2, B = U = 2*3, V = [2*3], X = 3 2. Írjon olyan Prolog eljárást, amely felépíti adott Min és Max egészek közé eső egész számok növekedő listáját (a határokat is beleértve)! Segédeljárást ne definiáljon! % novolista(Min, Max, L): L azon X egészek növekedő listája, % amelyekre Min =< X =< Max. % :- pred novolista(int::in, int::in, list(int)::out). (3 pont) Példa: | ?- novolista(5, 10, L). L = [5,6,7,8,9,10] ? Megoldás: novolista(Min, Max, []) :- Max < Min. novolista(Min, Max, [Min|L]) :- Max >= Min, Min1 is Min + 1, novolista(Min1, Max, L). 3. Írjon olyan Prolog eljárást, amely egy adott atomnak felsorolja az összes olyan rész-atomját, amelyben saját kezdőbetűje legalább még egyszer előfordul! Segédeljárást ne definiáljon! % duplazo(Atom, Resz): Az Atom atomnak Resz olyan rész-atomja, amelynek % első karaktere legalább még egyszer előfordul Resz-ben. % :- pred duplazo(atom::in, atom::out). (4 pont) Példa: | ?- duplazo(opapa, D). D = pap ? ; D = papa ? ; D = apa ? ; no Megoldás: duplazo(Atom, Resz) :- name(Atom, Lista), append(_, Farok, Lista), append([K|Kozep], _, Farok), % prefix([K|Kozep], Farok), memberchk(K, Kozep), name(Resz, [K|Kozep]). 4. Írjon olyan Prolog eljárást, amely egy adott szám-listából kigyüjt minden olyan elemet, amely az őt megelőző elemek összegével megegyezik. % elossz(L, T): A T lista az L szám-lista azon elemeiből áll, amelyek % megegyeznek az őket L-ben megelőző elemek összegével. % :- pred elossz(list(int)::in, list(in)::out). (5 pont) Példa: | ?- elossz([1,2,3,2,8,4,20], L). L = [3,8,20] ? Megoldás: elossz(L, T) :- elossz(L, 0, T). % elossz(L, S, T): T az L lista azon elemeinek listaja amelyek egyenloek % az oket megelozo elemek es S osszegevel. Az elemek sorrendje a ket % listaban megegyezik. elossz([], _, []). elossz([H|T], S, L) :- ( S =:= H -> L = [H|L1] ; L = L1 ), S1 is S + H, elossz(T, S1, L1). Prolog feladatok B csoport. 1. Írja fel az alábbi két Prolog kifejezés 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! .(X, [U-V*2, f(X)]) [A, 5-A, f(1*B)]. (3 pont) Megoldás: .(X, .(-(U, *(V, 2)), .(f( X), []))) .(A, .(-(5, A), .(f(*(1, B)), []))) A = X = 1*2, B = 2, U = 5, V = 1 2. Írjon olyan Prolog eljárást, amely felépíti adott Min és Max egészek közé eső egész számok fogyó listáját (a határokat is beleértve)! Segédeljárást ne definiáljon! % fogyolista(Min, Max, L): L azon X egészek fogyó listája, % amelyekre Min =< X =< Max. % :- pred fogyolista(int::in, int::in, list(int)::out). (3 pont) Példa: | ?- fogyolista(5, 10, L). L = [10,9,8,7,6,5] ? Megoldás: fogyolista(Min, Max, []) :- Max < Min. fogyolista(Min, Max, [Max|L]) :- Max >= Min, Max1 is Max - 1, fogyolista(Min, Max1, L). 3. Egy atomot "kezdőhosszú"-nak nevezünk, ha ASCII kisbetűvel kezdődik és hossza megegyezik a kezdőbetű ábécében elfoglalt sorszámával (a - 1, b - 2, stb.). Írjon olyan Prolog eljárást, amely egy adott atomnak felsorolja az összes "kezdőhosszú" rész-atomját! Segédeljárást ne definiáljon! % kezdohosszu(Atom, Resz): Az Atom atomnak Resz "kezdőhosszú" % rész-atomja. % :- pred kezdohosszu(atom::in, atom::out). (4 pont) Példa: | ?- kezdohosszu(dobban, R). R = dobb ; R = bb ; R = ba ; R = a ; no Megoldás: kezdohosszu(Atom, Resz) :- name(Atom, Lista), append(_, [K|Farok], Lista), K >= 0'a, K =< 0'z, N is K - 0'a, length(Kozep, N), append(Kozep, _, Farok), % prefix(Kozep, Farok), name(Resz, [K|Kozep]). 4. Írjon olyan Prolog eljárást, amely egy adott szám-listából kigyüjt minden olyan elemet, amely a teljes számlista átlagától egy adott számnál kevesebbel tér el. % atlkozeli(L, Eps, K): A K lista az L szám-lista azon elemeiből áll, % amelyek eltérese az L lista átlagától kisebb mint Eps. % :- pred atlkozeli(list(number)::in, number::in, list(number)::out). (5 pont) Példa: | ?- atlkozeli([5,1,3,2,4,7,6], 2, K). K = [5,3,4] ? Megoldás: atlkozeli([], _, L) :- !, L = []. atlkozeli(L, E, K) :- sum_list(L, S), length(L, N), A is S/N, atlkozeli(L, E, A, K). % atlkozeli(L, E, A, K): K az L lista azon elemeinek listaja, amelyek A-tol % kevesebb mint E-vel ternek el. Az elemek sorrendje a ket listaban % megegyezik. atlkozeli([], _, _, []). atlkozeli([H|T], E, A, K) :- ( abs(H - A) < E -> K = [H|K1] ; K = K1 ), atlkozeli(T, E, A, K1).