% =================================== % Deklaratív Programozás 5. gyakorlat % =================================== :- use_module(library(lists)). % Imperatív algoritmus átírása Prologba % ------------------------------------- % int hatv(int a, int h) { % int e = 1; % % while (h > 0) { % if (h & 1) { % e *= a; % } % h >>= 1; % a *= a; % } % % return e; % } % int main() { % printf("hatv(2, 19) = %d\n", hatv(2, 19)); % } % hatv(A, H, E): A-nak H-adik hatványa E, % ahol A, H >= 0 egészek. hatv(A, H, E) :- % int hatv(int a, int h) { hatv(A, H, 1, E). % int e = 1; % % hatv(A, H, E0, E): A-nak H-adik hatványát % % E0-lal szorozva kapjuk E-t. % hatv(A0, H0, E0, E) :- % H0 > 0, !, % while (h > 0) { ( H0 /\ 1 =:= 1 % if (h & 1) { % /\ bitenkénti "és" % -> E1 is E0*A0 % e *= a; ; E1 = E0 % E0 "nem változik" % } ), % H1 is H0 >> 1, % h >>= 1; A1 is A0*A0, % a *= a; hatv(A1, H1, E1, E). % } hatv(_, _, E, E). % return e; % } % Univ gyakorlása % --------------- % A feladat: egy tetszőleges Prolog kifejezéshez soroljuk fel a benne % bárhol előforduló atomokat, de a struktúranévként szereplő % atomokat ne soroljuk fel. % Vigyázat: a kifejezésben változók is előfordulhatnak. % Az alábbiakban a "Kif kifejezésben előfordul az A atom" feltétel így % értelmezendő: "a Kif kifejezésben előfordul az A atom, nem struktúranév % helyzetben". % kif_atom(?Kif, ?A): A Kif kifejezésben előfordul az A atom. kif_atom(X, A) :- atom(X), !, A = X. kif_atom(X, A) :- compound(X), % a változó kizárása miatt fontos! X =.. [_F|ArgList], member(X1, ArgList), % lists könyvtárból kif_atom(X1, A). % A feladat: egy tetszőleges Prolog kifejezéshez soroljuk fel a benne levő % atomokat, és minden atom esetén adjuk meg annak a kiválasztóját! % Egy részkifejezés kiválasztója egy olyan lista, amely megadja, mely % argumentumpozíciók mentén juthatunk el hozzá. % Pl. az `a*b+f(1,2,3)/c' Prolog kifejezésben % `b' kiválasztója [1,2], 3 kiválasztója [2,1,3]. % kif_atom_kiv(?Kif, ?A, ?Kiv): Kif Kiv kiválasztójú része az A atom. kif_atom_kiv(X, A, Kiv) :- atom(X), !, A = X, Kiv = []. kif_atom_kiv(X, A, [I|Kiv]) :- compound(X), % a változó kizárása miatt fontos! X =.. [_F|ArgList], nth(I, ArgList, X1), % lists könyvtárból kif_atom_kiv(X1, A, Kiv). % kif_atom1(?Kif, ?A): A Kif kifejezésben előfordul az A atom. kif_atom1(X, A) :- atom(X), !, A = X. kif_atom1(X, A) :- compound(X), % a változó kizárása miatt fontos! functor(X, _F, ArgNo), between(1, ArgNo, I), arg(I, X, X1), kif_atom1(X1, A). % between(+I, +J, ?X): I =< X, X =< J. between(I, J, I) :- I =< J. between(I, J, X) :- I < J, I1 is I+1, between(I1, J, X). % A feladat: egy tetszőleges Prolog kifejezés esetén gyűjtsük listába a % benne előforduló atomokat. % kif_atomok(?Kif, ?L): A Kif kifejezésben előforduló atomok listája L. kif_atomok(X, L) :- kif_atomok(X, [], L). % kif_atomok(?Kif, ?L0, ?L): A Kif kifejezésben előforduló atomok listáját % L0 elé fűzve kapjuk az L listát. kif_atomok(X, L0, L) :- atom(X), !, L = [X|L0]. kif_atomok(X, L0, L) :- compound(X), !, X =.. [_|ArgList], lista_atomok(ArgList, L0, L). kif_atomok(_X, L0, L0). % lista_atomok(?KifL, ?L0, ?L): A KifL lista elemeiben előforduló atomok % listáját L0 elé fűzve kapjuk az L listát. lista_atomok([], L0, L0). lista_atomok([Kif|KifL], L0, L) :- kif_atomok(Kif, L1, L), lista_atomok(KifL, L0, L1). % kif_atomok1(?Kif, ?L): A Kif kifejezésben előforduló atomok listája L. kif_atomok1(X, L) :- findall(A, kif_atom(X, A), L). % ki_0(X): egy tetszőleges X kifejezést kiír alapstruktúra alakban ki_0(Kif) :- var(Kif), !, write(Kif). ki_0(Kif) :- Kif =.. [Func|ArgL], writeq(Func), ( ArgL == [] -> true ; ArgL = [A1|ArgL2], write('('), ki_0(A1), arglista_ki0(ArgL2), write(')') ). % arglista_ki0(AL): Az AL = [A1,...,An] listát kiírja ",A1,...,An" alakban. arglista_ki0([]). arglista_ki0([A|AL]) :- write(','), ki_0(A), arglista_ki0(AL). % ki_1(X): egy tetszőleges X kifejezést kiír alapstruktúra alakban ki_1(Kif) :- compound(Kif), !, Kif =.. [Func|ArgL], writeq(Func), write('('), ( append(_, [A|Rest], ArgL), ki_1(A), Rest \= [], % az utolsó argumentum után nem írunk vesszőt write(','), fail % visszalépéses ciklus ; true ), write(')'). ki_1(Kif) :- % \+ compound(Kif), writeq(Kif). % A feladat: egy tetszőleges Prolog kifejezésben cseréljük le % az összes számot 1-gyel nagyobbra. Vigyázat: a kifejezésben % változók is előfordulhatnak. % novel(+Kif, ?NKif): NKif úgy áll elő Kif-ből, hogy az utóbbiban % előforduló összes számot 1-gyel nagyobbra cseréljük. novel(X, NX) :- number(X), !, NX is X+1. novel(X, NX) :- compound(X), !, X =.. [F|ArgList], lista_novel(ArgList, NArgList), NX =.. [F|NArgList]. novel(X, X). % lista_novel(+L, ?NL): NL úgy áll elő az L listából, hogy az % utóbbiban előforduló összes számot 1-gyel nagyobbra cseréljük. lista_novel([], []). lista_novel([X|Xs], [NX|NXs]) :- novel(X, NX), lista_novel(Xs, NXs). % novel1(+Kif, ?NKif): NKif úgy áll elő Kif-ből, hogy az utóbbiban % előforduló összes számot 1-gyel nagyobbra cseréljük. novel1(X, NX) :- number(X), !, NX is X+1. novel1(X, NX) :- compound(X), !, X =.. [F|ArgList], bagof(NA, A^( member(A, ArgList), novel1(A, NA) ), % Fontos, hogy bagof-ot és ne findall-t használunk, mert a bagof % megőrzi a változókat. % Fontos az A^ használata (vagy helyette a konjukció külön % eljárásként való elnevezése). NArgList), NX =.. [F|NArgList]. novel1(X, X). % Felsoroló eljárások írása % ------------------------- % A feladat: 2 hatványainak felsorolása. % kettohatv(+N, ?K): K =< N olyan pozitív egész, amely % 2-nek valahanyadik hatványa. kettohatv(N, K) :- 1 =< N, kettohatv(N, 1, K). % kettohatv(+N, +K0, ?K): K olyan pozitív egész, amely % 2-nek valahanyadik hatványa, és K0 =< K =< N. % Előfeltétel: K0 =< N, K0 2-nek valahanyadik hatványa. kettohatv(N, K0, K) :- ( K = K0 ; K1 is 2*K0, K1 =< N, kettohatv(N, K1, K) ). % kettohatv(+N, ?K): K =< N olyan pozitív egész, amely % 2-nek valahanyadik hatványa. kettohatv1(N, K) :- kezdo_par(N, P0), par_megoldas(P0, K). % A P0 paraméterrel jellemzett keresési térben K egy megoldás. par_megoldas(P0, K) :- par_elso_megoldas(P0, K0), ( K = K0 ; par_kovpar(P0, P1), par_megoldas(P1, K) ). % A kettohatv problématér jellemzésére használt paraméter(struktúra): % N-K0: A K0..N intervallumban szereplő 2 hatványokat soroljuk % fel, ahol K0 =< N, és K0 egy 2 hatvány. % kezdo_par(N, P0): P0 az 1..N közötti 2 hatványok felsorolásához % tartozó paraméter kezdo_par(N, N-1) :- 1 =< N. % par_elso_megoldas(P0, K0): A P0 paraméterű keresési térben levő % első megoldás K0. par_elso_megoldas(_N-K0, K0). % par_kovpar(P0, P1): A P0 paraméterű keresési térből az első megoldás % elhagyásával keletkező keresési téret írja le a P1 paraméter. par_kovpar(N-K0, N-K1) :- K1 is 2*K0, K1 =< N. % Egy listában fennsíknak nevezünk: % - egy csupa azonos elemből álló, legalább kételemű, folytonos részlistát; % - amely az ilyenek között maximális (egyik irányba sem kiterjeszthető). % A feladat: felsorolandók egy lista fennsíkjai és kezdőpozíciójuk. % fennsik(L, F, H)}: Az L listában az F (1-től számozott) pozíción egy H % hosszú fennsík van. fennsik(L, F, H) :- fennsik(L, 1, F, H). % A P0-tól számozott L0 listában az F pozíción % egy H hosszú fennsík van. fennsik(L0, P0, F, H) :- % az első fennsík jellemzői F0 és H0, % a fennsík utáni maradéklista L1: elso_fennsik(L0, P0, F0, H0, L1), ( F = F0, H = H0 ; P1 is F0+H0, % L1 kezdőpozíciója, P1, nem más mint % az előző megoldás kezdőpozíciója+hossza fennsik(L1, P1, F, H) ). % elso_fennsik(+L0, +P0, -F, -H, -L): A P0-tól számozott L0 listában az % első fennsík az F. pozíción van és hossza H, a fennsík után fennmaradó % rész pedig az L lista. elso_fennsik([E,E|L1], P0, F, H, L) :- !, F = P0, azonosak(L1, E, 2, H, L). elso_fennsik([_|L1], P0, F, H, L) :- P1 is P0+1, elso_fennsik(L1, P1, F, H, L). % azonosak(+L0, +E, +H0, -H, -L): Az L0 lista elejéről a maximális számú % E-vel azonos elemet lehagyva marad L, a lehagyott elemek száma H-H0. azonosak([X|L0], E, H0, H, L) :- E = X, !, H1 is H0+1, azonosak(L0, E, H1, H, L). azonosak(L, _, H, H, L). % Megoldásgyűjtő eljárások gyakorlása % ----------------------------------- % nszerese(L, N, NL): NL az L számlista elemeinek % N-szereseiből álló lista. nszerese(L, N, NL) :- findall(NX, elem_nszerese(L, N, NX), NL). % elem_nszerese(NL, N, NX): NX az NL lista egy elemének N-szerese. elem_nszerese(L, N, NX) :- member(X, L), NX is N*X. % nszerese1(L, N, NL): NL az L számlista elemeinek % N-szereseiből álló lista. nszerese1(L, N, NL) :- findall(NX, ( member(X, L), NX is N*X ), NL). % Kevésbe hatékony, mint nszerese/3, mert a meta-hívás % interpretáltan fut. % nszerese2(L, N, NL): NL az L nem-üres számlista elemeinek % N-szereseiből álló lista. nszerese2(L, N, NL) :- bagof(NX, elem_nszerese(L, N, NX), NL). % Kevésbe hatékony, mint nszerese/3, mert a bagof kénytelen % bejárni a meghivandó célt, hogy kigyűjtse a változókat. % Eltérés: []-ra meghiúsul. % nszerese3(L, N, NL): NL az L nem-üres számlista elemeinek % N-szereseiből álló lista. nszerese3(L, N, NL) :- bagof(NX, X^( member(X, L), NX is N*X ), NL). % Ha elhagyjuk az `X^' karaktereket, hibas mukodest kapunk: % | ?- nszerese3([1,2,2,1,5], 4, L). % L = [4,4] ? ; % L = [8,8] ? ; % L = [20] ? ; % no