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) Megoldás: f(-(*(1,Y),U),.(V,[]),*(V,U)) f(-(A,3),B,A) egyesíthetők, a következő behelyettesítéssel: A = 1*3, B = [1], U = 3, V = 1, Y = 3 Egy Prolog párbeszéd, amelyből a fentiek kiolvashatók: | ?- current_prolog_flag(toplevel_print_options, Opts). Opts = [quoted(true),numbervars(true),portrayed(true), max_depth(10)] ? yes | ?- set_prolog_flag(toplevel_print_options, [numbervars(true),ignore_ops(true)]). yes | ?- Term1 = f(1*Y-U, [V], V*U). Term1 = f(-(*(1,Y),U),.(V,[]),*(V,U)) ? yes | ?- Term2 = f(A-3, B, A). Term2 = f(-(A,3),B,A) ? yes | ?- f(1*Y-U, [V], V*U) = f(A-3, B, A). A = *(1,3), B = .(1,[]), U = 3, V = 1, Y = 3 ? yes | ?- set_prolog_flag(toplevel_print_options, [quoted(true),numbervars(true),portrayed(true),max_depth(10)]). yes | ?- f(1*Y-U, [V], V*U) = f(A-3, B, A). A = 1*3, B = [1], U = 3, V = 1, Y = 3 ? yes | ?- 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). Megoldás: . a([A|B], C, [1,2]), w([A|B]-C). | | (2) | . a(B, C, [2]), w([1|B]-C). / \ / \ (1) / \ (2) / \ / \ / \ / \ / \ . w([1]-[2]). . a(T, C, []), w([1,2|T]-C). | | | | (1) [] | . w([1,2]-[]). | | [] 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 Megoldások: :- use_module(library(lists)). kozeli(L, A, B) :- append(_, [A,B|_], L), abs(A-B) =< 1. kozeli2([A,B|_L], A, B) :- abs(A-B) =< 1. kozeli2([_|L], A, B) :- kozeli2(L, A, B). kozeli3([X,Y|L], A, B) :- ( abs(X-Y) =< 1, A = X, B = Y ; kozeli3([Y|L], A, B) ). 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 (egynél nagyobb) 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 szorzat([], _, []). szorzat([X|Xs], Sz, Ls) :- prefix_szorzata([X|Xs], Sz, L), Ls = [L|Ls0], szorzat(Xs, Sz, Ls0). szorzat([X|Xs], Sz, Ls) :- \+ prefix_szorzata([X|Xs], Sz, _L), szorzat(Xs, Sz, Ls). % prefix_szorzata(L, Sz, P): P az L egy olyan prefixe, % amelynek szorzata Sz. % :- pred prefix_szorzata(list(int)::in, int::in, list(int)::out). prefix_szorzata([X|_Xs], Sz, [X]) :- X = Sz. prefix_szorzata([X|Xs], Sz, [X|Prefix]) :- Sz > X, Sz mod X =:= 0, Sz1 is Sz//X, prefix_szorzata(Xs, Sz1, Prefix). szorzat1([], _, []). szorzat1([X|Xs], Sz, Ls) :- prefix_szorzata([X|Xs], Sz, L), !, Ls = [L|Ls0], szorzat1(Xs, Sz, Ls0). szorzat1([_X|Xs], Sz, Ls) :- szorzat1(Xs, Sz, Ls).