% % % Deklaratív programozás % % 3. Prolog gyakorlat % % 2024 október 29. % % % % % Prolog programozás % % % -------------------------------------------------------------------- % % Deklaratív Programozás gyakorlat % Prolog programozás: listák, gráfok % MEGOLDÁSOK % --------------------------------------------------------------- % 1. Beszúrás rendezett listába % % insert_ord(+RL0, +Elem, ?RL): Az RL szigorúan monoton növő egészlista % % úgy áll elő, hogy az RL0 szigorúan növő egészlistába beszúrjuk az Elem % % egész számot, feltéve hogy Elem nem eleme az RL0 listának; egyébként % % RL = RL0. Megoldása legyen jobbrekurzív, használjon feltételes szerkezetet! % | ?- insert_ord([1,3,5,8], 6, L). % L = [1,3,5,6,8] ? ; % no % | ?- insert_ord([1,3,5,8], 3, L). % L = [1,3,5,8] ? ; % no % Megoldása legyen jobbrekurzív, ne hagyjon választási pontot, % használjon feltételes szerkezetet! % insert_ord(+RL0, +Elem, ?RL): Az RL szigorúan monoton növő egészlista % úgy áll elő, hogy az RL0 szigorúan növő egészlistába beszúrjuk az Elem % egész számot, feltéve hogy Elem nem eleme az RL0 listának; egyébként % RL = RL0. Megoldása legyen jobbrekurzív, használjon feltételes szerkezetet! insert_ord([], E, [E]). insert_ord(L0, E, L) :- L0 = [X|L1], ( X > E -> L = [E|L0] ; X =:= E -> L = L0 ; L = [X|L2], insert_ord(L1, E, L2) ). % -------------------------------------- % Otthoni, szorgalmi feladat: oldja meg ugyanezt a feladatot vágó % használatával (feltételes szerkezet és diszjunkció nélkül), úgy hogy % csak három klózból álljon a predikátum. % insert_ord_1(+RL0, +Elem, ?RL): ugyanaz mint % insert_ord(+RL0, +Elem, ?RL), a vágó beépített eljárás használatával. % Kicsit egyszerűbb mint az előző két változat, mert csak % háromfelé ágazik (insert_ord_1 1. és 3. klózát itt most % egyetlen klóz, a 3. helyettesíti) insert_ord_1([X|L0], E, L) :- X < E, !, L = [X|L1], insert_ord_1(L0, E, L1). insert_ord_1([E|L0], E, L) :- !, L = [E|L0]. insert_ord_1(L0, E, [E|L0]). % 2. Két rendezett egészlista összefésülése egy rendezett listává % % merge(+RL0, +RL1, ?RL): RL0 és RL1 szigorúan rendezett listák % összefésülése egy szigorúan rendezett RL listává. % | ?- merge([1,2],[2,3,4], L). % L = [1,2,3,4] ? % yes % | ?- merge([1,2,3,4],[2,3,4], L). % L = [1,2,3,4] ? ; % no % | ?- merge([1,4,16,64],[2,4,8,16,32], L). % L = [1,2,4,8,16,32,64] ? ; % no merge(L1, L2, L) :- ( L1 = [] -> L = L2 ; L2 = [] -> L = L1 ; L1 = [X|T1], L2 = [Y|T2], ( X = Y -> L = [X|T], merge(T1, T2, T) ; X < Y -> L = [X|T], merge(T1, L2, T) ; L = [Y|T], merge(L1, T2, T) ) ). % 3. Unalmas listák % A 260. előadásdián szerepel az unalmas/2 predikátum: % unalmas(Lista, X): Lista minden eleme = X unalmas([], _X). unalmas([H|T], X) :- H = X, unalmas(T, X). % Írjon egy nemrekurzív unalmas1/2 eljárást, amely ekvivalens a fentivel! % Használja az append/3 beépített eljárást! unalmas1(L,X):-append(U,_,L),L=[X|U]. unalmas9([X|U],X):-append(U,_,[X|U]). unalmas8([X|U],X):-prefix([X|U],U). % Írjon egy szintén nemrekurzív unalmas2/2 eljárást, amely a \+ /2 % (nem bizonyítható) beépített eljárásra épül! Mik azok a bemenetek, % amikre az unalmas2/2 nem úgy működik mint az unalmas/2 és az % unalmas1/2? % Az unalmas1/2 és unalmas2/2 eljárásokat "egyklózos" eljárásoknak % hívjuk. Ezektől elvárjuk, hogy egyetlen klózból álljanak és ne % legyenek rekurzívak, viszont nem várjuk el, hogy hatékonyak % legyenek. % ----------------------------- % Platónak hívunk egy olyan legalább kételemű listát, amely csupa azonos % elemből áll. Az mondjuk, hogy MP egy L listában található maximális % plató, ha % - MP az L folytonos része (azaz MP előáll úgy, hogy L elejéről és % végéről 0 vagy több elemet elhagyunk), % - MP egy plató és % - MP maximális L-ben, azaz nem lehet sem balra sem jobbra a benne % levőkkel azonos, közvetlenül szomszédos elemekkel kiterjeszteni. % Például az L = [a.b,a,c,c,c,b,b] listában két maximális plató van, a % 4. pozición kezdődő [c,c,c] és a 7. pozición kezdődő [b,b] lista (a % listaelemeket 1-től számozzuk). % ----------------------------- % 4. Platók felsorolása % Írja meg az alábbi fejkommentnek megfelelő plato0/4 egyklózos % eljárást, amellyel egy adott listában előforduló platók adatait % tudjuk felsorolni. Segítségül megadtuk az eljárás fejéhez és % törzséhez tartozó kommenteket. Használja az append/2 és last/2 % eljárásokat a lists könyvtárból! :-use_module(library(lists),[append/2,prefix/2,last/2]). plato0(L, I, Len, X) :- % Az L listában az I. pozición van egy % Len hosszúságú, X elemekből képzett % maximális plató HA L2 = [X,X|T], % L2 két X elemmel kezdődő, T-vel folytatódó lista ÉS append([L1,L2,L3], L), % L szétszedhető L1, L2, L3 részlistákra ÉS prefix(L2, T), % L2 minden Y eleme azonos X-szel ÉS \+ L3 = [X|_], % L3 nem X-szel kezdődő lista (1) ÉS \+ last(L1, X), % L1 nem X-szel végződő lista (2) ÉS length(L2, Len), % L2 hossza Len, ÉS length([a|L1], I). % I = 1+(L1 hossza). % Az alábbi eljárások segítségével a fenti plato0/4 eljárással ekvivalens, % de lényegesen hatékonyabb plato/4 predikátumot valósítunk majd meg. % 5. Kezdő plató % Írjon Prolog eljárást amely a bemenetként kezdődő listáról % eldönti, hogy egy platóval kezdődik-e, és ha igen, visszaadja a % kezdeti plató hosszát és az ezutáni (maradék) elemek % listáját. Segédeljárásokat is meg kell valósítania. % % % pl_kezdetu(L, Len, M): Az atomokból álló L lista egy Len hosszúságú % % maximális platóval kezdődik, amelyet az M maradéklista követ. % % | ?- pl_kezdetu([a,b,a,c,c,c,b,b], Len, M). % no % | ?- pl_kezdetu([c,c,c,b,b], Len, M). % Len = 3, M = [b,b] ? ; no % | ?- pl_kezdetu([b,b], Len, M). % Len = 2, M = [] ? ; no % | ?- pl_kezdetu([b], Len, M). % no % | ?- pl_kezdetu([], Len, M). % no % | ?- % maxazonos(L0, M, A, N0, N): Az L0 lista elejerol leszedheto k db A es % marad egy nem A-val kezdodo M, tovabba N=N0+k. maxazonos(L0, M, A, N0, N) :- ( L0 = [A|L1] -> N1 is N0+1, maxazonos(L1, M, A, N1, N) ; M = L0, N = N0 ). pl_kezdetu([A,A|L], Len, M) :- maxazonos(L, M, A, 2, Len). % Kevésbé hatékony, de segédeljárás nélküli. pl_kezdetu1([A,A], 2, []). pl_kezdetu1([A|L], Len, M) :- L = [A|L1], L1 = [B|_], ( B = A -> pl_kezdetu1(L, Len1, M), Len is Len1+1 ; Len = 2, M = L1 ). % 6. Hatékony platókeresés % Írjon olyan hatékony Prolog eljárást, amely felsorolja atomok egy % adott listájában található maximális platókat, megadva a plató % hosszát és az ismétlődő elemet. Használja a pl_kezdetu/3 eljárást! % % % plato(+L, ?Len, ?X): Az L listában található egy Len hosszúságú, % % X elemekből képzett maximális plató. % % | ?- plato([a,b,b,b,b,a,a,c,b,b], Len, X). % Len = 4, X = b ? ; % Len = 2, X = a ? ; % Len = 2, X = b ? ; % no plato(L, Len, X) :- L = [X0|L1], ( pl_kezdetu(L, Len0, M) -> ( X = X0, Len = Len0 ; plato(M, Len, X) ) ; plato(L1, Len, X) ). % 7. Futamok % Egy olyan listát, amelyekben sokszor ismétlődnek a szomszédos % elemek, érdemes lehet tömörítve tárolni. Ennek egy formája a % futamokkal való ábrázolás, pl.: % [a,a,b,c,c,c,c,d,e,e,e,f,f,f] ---> [a-2,b-1,c-4,d-1,e-3,f-3] % Tehát az azonos (X) elemekből álló maximális hosszúságú (N) % sorozatokat egy X-N párral ábrázolunk a futamok listájában. % Írjon egy futamok0/2 Prolog eljárást, amely egy tetszőleges tömör % Prolog listát átalakít futamok listájává! (Egy Prolog kifejezés % tömör, ha nem tartalmaz változót, vö. a ground/1 beépített % eljárással.) % | ?- futamok0([a,a,b,c,c,c,c,d,e,e,e,f,f,f], Futamok). % Futamok = [a-2,b-1,c-4,d-1,e-3,f-3] ? ; no % | ?- futamok0([a,a,a,a], Futamok). % Futamok = [a-4] ? ; no % | ?- futamok0([a,b,c,d], Futamok). % Futamok = [a-1,b-1,c-1,d-1] ? ; no % | ?- futamok0([a,b,b,c,a,a,c], Futamok). % Futamok = [a-1,b-2,c-1,a-2,c-1] ? ; no % | ?- futamok0([], Futamok). % Futamok = [] ? ; no futamok0([], []). futamok0([X|L0], [X-Xcnt|Fk]) :- append(Xs, L1, L0), L1 \= [X|_], !, length([X|Xs], Xcnt), futamok0(L1, Fk). % % Írjon egy komatuf/2 Prolog eljárást, amely egy tetszőleges tömör % % (azaz változót nem tartalmazó) futamlistát visszaalakít közönséges % % listává! % % | ?- komatuf([a-1,b-2,c-1,a-2,c-1], L). % L = [a,b,b,c,a,a,c] ? ; no % | ?- komatuf([d-1,a-2,d-1], L). % L = [d,a,a,d] ? ; no % | ?- komatuf([], L). % L = [] ? ; no komatuf([X-N|Futamok0], L) :- length(F, N), unalmas(F, X), append(F, L0, L), komatuf(Futamok0, L0). komatuf([], []). % Végül írjon egy futamok/2 Prolog eljárást, amelyik ugyanazt a % relációt valósítja meg mint a futamok0/2 eljárás, de mindkét % irányban működik: ha az első argumentuma tömör lista, akkor ennek % futamlista megfelelőjét egyesíti a második argumentummal; ha a % második argumentuma egy tömör futamlista, akkor azt közönséges % listává alakítja, és az első argumentumban adja vissza! Ha egyik % argumentum sem tömör, az eljárás hiúsuljon meg! % | ?- futamok([a,b,b,c,a,a,c], Futamok). % Futamok = [a-1,b-2,c-1,a-2,c-1] ? ; no % | ?- futamok(L, [a-1,b-2,a-1]). % L = [a,b,b,a] ? ; no % | ?- futamok([a,X,b,c], Y). % no futamok(L, F) :- ( ground(L) -> futamok0(L, F) ; ground(F) -> komatuf(F, L) ).