Deklaratív programozás - Prolog programozási feladatok

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Prolog programozási feladatok

A mintavizsga Prolog programozás feladatainak megoldásai.

A print_all/1 és megold/1 eljárásoktól meg az alattuk lévő ?- kezdetű soroktól ne ijedjen meg senki, azok csak azért vannak, hogy Consult után rögtön megjelenjenek a példákra adott megoldások, ne kelljen begépelni őket ;)

A mintavizsga 1. feladatának megoldása

<hr><BEGIN FILE>

% PROLOG MINTAFELADATSOR 1. PROGRAMOZÁSI FELADAT
%
% Segédeljárás:
%
%	Egy számlistában vízesésnek hívunk egy olyan legalább kételemű,
%	folyamatos részlistát, amely szigorúan monoton csökkenő, a
%	szomszédos elemek különbsége legalább 3, és egyik irányba sem
%	terjeszthető ki ezen tulajdonságok megtartásával.
%
%	Írjon egy olyan Prolog eljárást, amely eldönti, hogy egy egészekből
%	álló lista elején egy vízesés áll-e, és visszadja a vízesés első és
%	utolsó elemét, valamint a bemeneti listának a megtalált vízesés
%	utáni részét! Ha a bemeneti lista nem vízeséssel kezdődik, az
%	eljárás hiúsuljon meg!
%
% Teljes feladat:
%
%	A kezdo_vizeses/3 predikátum segítségével írjon egy olyan Prolog
%	eljárást, amely felsorolja egészek egy adott listájában az összes
%	benne megtalálható vízesés első és utolső elemét! A vízeséseket
%	előfordulási sorrendjükben vegye sorra!

% kezdo_vizeses(L, K, V, M): az L egészlista elején egy vízesés áll,
% amelynek első eleme K, utolsó eleme V, az utána következő elemek
% listája M.
% :- pred kezdo_vizeses(list(int)::in, int::out, int::out,
%	 list(int)::out).
kezdo_vizeses([X,Y|Xs], K, X, [Y|Xs]) :-
		X - Y < 3, !, nonvar(K), !.
kezdo_vizeses([X,Y|Xs], K, V, M) :-
		!,
		(var(K) -> K = X ; true),
		kezdo_vizeses([Y|Xs], K, V, M).
kezdo_vizeses([X], K, X, []) :-
		nonvar(K).

% vizeses(L, K, V): K és V egy az L egészlistában előforduló vízesés
% első illetve utolsó eleme.
% :- pred vizeses(list(int)::in, int::out, int::out).
vizeses(L, K, V) :-
		kezdo_vizeses(L, A, B, M), !,
		(  K = A, V = B
		;
			vizeses(M, K, V)
		).
vizeses([_|Xs], K, V) :-
		vizeses(Xs, K, V).


% megold(X): Az X paraméterrel meghívja a főfüggvényt és az eredményt
% kiírja a képernyőre.
megold(X) :-
		print('  '), print(X), print(' --> '),
		(  bagof(K-V, vizeses(X, K, V), E),
			print_all(E)
		;
			print('no')
		),
		nl.

% print_all(X): Az X paraméterben kapott megoldáslistát kiírja a
% képernyőre.
print_all([]) :-
		print('no').
print_all([K-V|Xs]) :-
		print('K = '), print(K), print(', '),
		print('V = '), print(V),
		print(' ; '),
		print_all(Xs).

?- nl, print('Példafutások:'), nl.
?- megold([0,2,5,5]).
?- megold([1,2,-5,20,15,12,7,3,0,-2]).
?- nl.

<EOF><hr>

A mintavizsga 2. feladatának megoldása

<hr><BEGIN FILE>

% PROLOG MINTAFELADATSOR 2. PROGRAMOZÁSI FELADAT
%
% Segédeljárás:
%
%	Egy Prolog kifejezés szimmetrikus, ha a szimmetrikus pozíciójú
%	argumentumai azonosak (azaz egy n-argumentumú kifejezés
%	szimmetrikus, ha 1. és n., 2. és (n-1).,..., i. és (n+1-i).
%	argumentuma azonos). Az argumentum nélküli kifejezéseket
%	szimmetrikusaknak tekintjük.
%
%	Írjon Prologban egy olyan eljárást, amely egy tetszőleges Prolog
%	kifejezésről megállapítja, hogy az szimmetrikus-e!  Az azonosság
%	eldöntésére az ==/2 beépített eljárást használhatja.  Vigyázat, a
%	kifejezés lehet változó!
%
% Teljes feladat:
%
%	A szimmetrikus/1 predikátum segítségével írjon egy olyan Prolog
%	eljárást, amely egy tetszőleges Prolog kifejezés összes
%	szimmetrikus részstruktúráját felsorolja. A részkifejezések
%	előfordulási sorrendjét őrizze meg! Vigyázat, a kifejezés lehet
%	változó és benne is előfordulhatnak változók!

:- use_module(library(lists)).

% szimmetrikus(Kif): igaz, ha Kif szimmetrikus.
% :- pred szimmetrikus(univ::in).
szimmetrikus(Kif) :-
		var(Kif), !.
szimmetrikus(Kif) :-
		Kif =.. Reszek,
		length(Reszek, L),
		(  L =< 2, !
		;
		  [F,Arg1|Args] = Reszek,
		  reverse(Args, [LastArg|MidArgs]),
		  Arg1 == LastArg,
		  Kif1 =.. [F|MidArgs],
		  szimmetrikus(Kif1)
		).

% szimmetrikus_resze(Kif, Resz): Resz a Kif-nek szimmetrikus
% részstruktúrája
% :- pred szimmetrikus_resze(univ::in, univ::out).
szimmetrikus_resze(Kif, Kif) :-
		szimmetrikus(Kif).
szimmetrikus_resze(Kif, Resz) :-
		nonvar(Kif),
		Kif =.. [_|Args],
		member(Arg, Args),
		szimmetrikus_resze(Arg, Resz).


% megold(X): Az X paraméterrel meghívja a főfüggvényt és az eredményt
% kiírja a képernyőre.
megold(X) :-
		print('  '), print(X), print(' --> '),
		(  bagof(R, szimmetrikus_resze(X, R), E),
			print_all(E)
		;
			print('no')
		),
		nl.

% print_all(X): Az X paraméterben kapott megoldáslistát kiírja a
% képernyőre.
print_all([]) :-
		print('no').
print_all([R|Rs]) :-
		print('R = '), print(R), print(' ; '),
		print_all(Rs).

?- nl, print('Példafutások:'), nl.
?- megold(f(1,a,1)).
?- megold(f(2+1+1,3+3+3)).
?- megold(g(X,Y)).
?- nl.

<EOF><hr>

A mintavizsga 3. feladatának megoldása

<hr><BEGIN FILE>

% PROLOG MINTAFELADATSOR 3. PROGRAMOZÁSI FELADAT
%
% Egy A atom egy N nemnegatív egésszel vett szorzatán az A atom
% N-szeri egymás után fuzésével kapott atomot értjük.
%
% Segédeljárás:
%
%	Írjon Prolog nyelven egy eljárást amelynek bemenete egy N
%	nemnegatív egész és egy A atom, kimenete pedig N és A szorzata!
%
% Teljes feladat:
%
% A szorzata/3 eljárás segítségével, könyvtári eljárások használata
% nélkül készítsen el egy Prolog eljárást, amely egy számokból és
% atomokból a + és * operátorokkal felépített a-kifejezés értékét
% kiszámítja! Ha A atomot, N nemnegatív egészet jelöl, akkor az
% AKif-fel jelölt a-kifejezéseket a következő nyelvtani szabállyal
% jellemezhetjük:
%
%				AKif --->  A | N*AKif | AKif*N | AKif+AKif.
%
% A + operátor a konkatenálást jelöli, a * operátor pedig a
% segédfeladatban definiált szorzást. 

:- use_module(library(lists)).

% szorzata(N, A, NA): NA az N nemnegatív egész és az A atom szorzata.
% :- pred szorzata(int::in, atom::in, atom::out).
szorzata(0, _, '') :- !.
szorzata(N, A, NA) :-
		N1 is N - 1,
		szorzata(N1, A, R),
		atom_codes(A, B),
		atom_codes(R, R1),
		append(B, R1, R2),
		atom_codes(NA, R2).

% erteke(OpKif, Ertek): Az OpKif operátoros ábrázolású fent definiált
% alakú kifejezés értéke Ertek.
% :- pred erteke(univ::in, atom::out).
erteke(OpKif, OpKif) :- integer(OpKif) ; atom(OpKif).
erteke(OpKif, Ertek) :-
		OpKif =.. [Op, Arg1, Arg2],
		erteke(Arg1, Val1), erteke(Arg2, Val2),
		(  Op = '*' ->
			  (  integer(Val1) ->
					 szorzata(Val1, Val2, Ertek)
			  ;
					 szorzata(Val2, Val1, Ertek)
			  )
		;
			Op = '+' ->
			  atom_codes(Val1, Val1Codes),
			  atom_codes(Val2, Val2Codes),
			  append(Val1Codes, Val2Codes, ValCodes),
			  atom_codes(Ertek, ValCodes)
		).


% megold(X): Az X paraméterrel meghívja a főfüggvényt és az eredményt
% kiírja a képernyőre.
megold(X) :-
		erteke(X, E),
		print('  '), print(X), print(' --> '), print(E), nl.

?- nl, print('Példafutások:'), nl.
?- megold(alma).
?- megold(ba*2).
?- megold(2*ba).
?- megold(alma+'_korte'+2*'_barack').
?- nl.

<EOF><hr>

-- kronik - 2005.05.27.