Deklaratív programozás - Prolog gyakorlati 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

Feladat

append(X, _, [a,b,c,d]), X = [_|_], !.

Megoldás

X = [a] ? ; no

Komment

append (A, B, AB).

Ez alapból azt csinálja, hogy A mögé fűzi B-t, és ezt AB-ben adja vissza. Ennek inverz művelete az, ha a kimenetre egy véges listát adsz meg, és a bemenetekhez meg tetszőleges változókat írsz. Ekkor a Prolog az összes lehetséges módon szétbontja az AB listát 2 részre. Ez azt jelenti, hogy

A=[], B=[a,b,c,d];
A=[a], B=[b,c,d];
...
A=[a,b,c,d], B=[];

listákat csinál belőle.
Mivel a klóz nem csak ennyiből áll, hanem van mögötte egy X = [_ | _] is, csak olyan szétbontás fog megfelelni, ami nem eredményez az első listában üres listát (tehát A nem []). Ebből az első jó megoldás az A=[a]. Így kerül X-be X=[a|[]], vagy rövidebben írva X=[a]. Mivel a klóz 3. céljában egy vágó szerepel (egy ! jel), ezért az összes további megoldás le sem fog generálódni, hiszen egy helyes megoldás utan leáll a kereséssel.

Feladat

select(1, [2,X,3], L).

Megoldás

X = 1, L=[2,3] ? ; no

Komment

A fenti hívás azt mondja, hogy a [2,X,3] listából szeretnénk elhagyni az 1-es elemet. A select viszont meghiúsul, ha a listának nincs olyan eleme, ami megegyezik az elhagyandóval. Tehát ha azt szeretnénk, hogy a fenti hívás sikerrel fusson le, az X-nek 1-nek kell lennie.

Feladat

number_codes(123, [_|L]), number_codes(X, L).

Megoldás

L = [50,51], X = 23 ? ; no

Komment

number_codes(Szam, Kodok).

A number_codes eljárás a Szam-ot - decimális alakban - stringként értelmezi és a Kodok listában visszaadja az ASCII kódjait. A feladatban L ennek a listának a farkát képviseli, tehát a 2 és 3 számok kódjai vannak benne. A második number_codes hívás épp az előző ellentettjé csinálja, azaz a listában kapott kódokból készült számot adja vissza X-ben. (Érdemes megfigyelni, hogy a number_codes kétirányban is használható. ;) )

Feladat

\+ \+ X = 1, X = 2.

Megoldás

X = 2 ? ; no

Komment

Először elemezzük ki a \+ \+ X = 1 részt.

\+ X = 1 akkor lesz igaz, ha X nem egyesíthető 1-el. Mivel X egy változó, így egyesíthető, tehát \+ X = 1 meghiúsul, \+ \+ X = 1 viszont már igaz lesz (kétszeres tagadás). Fontos tudni a \+ szerkezet viselkedéséről, hogy a \+ X = 1 nem helyettesíti be X értékét, az - jelen esetben - továbbra is egy változó marad. Ezért a következő X = 2 hívás egyesíteni tudja X értékét 2-vel.

Feladat

[A,B] = [x,y,z].

Megoldás

no

Komment

Nagyon egyszerű: az [A,B] egy kételemű lista, [x,y,z] pedig három elemű, ezért nem egyesíthetőek.

Feladat

X	= : =	3*4.

Megoldás

! Instantiation error

Komment

Na itt a jó öreg Instantiation Error. :) Az = : = operátorról tudni kell, hogy mindkét oldalán tömör aritmetikai kifejezéseket vár, tehát nem lehet bennük változó. Márpedig X egy változó, ezért Futási hibát (Inst. Error) kapunk.

Feladat

X = 2*4, \+ X = 8.

Megoldás

X = 2*4 ? ; no

Komment

Az X = 2*4 hívás hatására X 2*4-gyel egyesül. (A Prolog egyesítésnél nem számolja ki az aritmetikai kifejezések értékét!) A \+ X = 8 hívás akkor sikerül, ha X nem egyesíthető 8-cal. Mivel X-ben 2*4 van, ami NEM egyesíthető 8-cal, így a hívás sikerrel fut le.

Feladat

X+Y = 2+3*4.

Megoldás

X = 2, Y = 3*4 ? ; no

Komment

Itt az operátorok eltérő prioritására láthatunk példát.

A szemléltetés érdekében alapstruktúra alakra hozva a két oldalt: +(X, Y) = +(2, *(3,4))

Innen már azonnal látszik, hogy X = 2 és Y = 3*4 lesz az egyesítési algoritmus eredménye.

Feladat

% parospoz(+L, ?A): A egy pozitív szám, amely páros indexű
%	eleme az Lszámlistának. A listaelemeket 1-től
%	számozzuk. 

Megoldás

parospoz([_,A|_], A) :- A > 0.
parospoz([_,_|T], A) :- parospoz(T, A).

Feladat

% szomsz(+L, ?Ossz, ?A, ?B): Az L számlistában A és B
%	szomszédos elemek, és összegük Ossz.

Megoldás

szomsz([A,B|_],O,A,B):-
	O is A+B.
szomsz([_|Xs],O,A,B):-
	szomsz(Xs,O,A,B).

Feladat

% kozep(+L, ?A): A egy olyan eleme az L listának, amely a
%	bal és jobb szomszédjának számtani közepe. 

Megoldás

kozep([X,Y,Z|_],K):-
	 Y=:=(X+Z)/2,
	 K=Y.
kozep([_|Zs],K) :- 
	 kozep(Zs,K).

Feladat

% nullpar(+L, ?NL): NL egy olyan kételemű (folytonos)
%	részlistája L-nek, amelynek összege 0.

Megoldás

nullpar([A,B|Xs],[A,B]):-
	 0=:=A+B.
nullpar([_|Xs],NP):-
	 nullpar(Xs,NP).

Feladat

%  hosszabb(R,H): igaz, ha R hosszabb mint H

Megoldás

hosszabb([_|_],[]).
hosszabb([_|T1],[_|T2]) :- hosszabb(T1,T2).

Komment

ETS elfogadta.

Feladat

% rakov(+L0, ?L): L ugyanolyan hosszú, mint az L0
%	számlista, és minden eleme 1-gyel nagyobb mint L0 azonos
%	sorszámú eleme.

Megoldás

rakov([], []).
rakov([A|T1],[B|T2]) :- 
		  B is A+1,
		  rakov(T1, T2).

Komment

ETS elfogadta.

Feladat

% parospoz(+L, ?A): A egy pozitív szám, amely páros indexű
%	eleme az L számlistának. A listaelemeket 1-től
%	számozzuk. 

Megoldás

parospoz([_, A | T], P) :-
  A  > 0,
  P is A.
parospoz([_,_|T],A) :- parospoz(T,A).

Komment

ETS elfogadta.

Feladat

% parosneg(+L, -A): A egy negatív szám,  amely páros indexű
%	eleme az L számlistának. A listaelemeket 1-től
%	számozzuk. 

Megoldás

parosneg([_, A | T], P) :-
  A  < 0,
  P is A.
parosneg([_,_|T],A) :- parosneg(T,A).

Komment

ETS elfogadta.

Feladat

% count(+X, +L, ?N): Az L lista elemeként az X kifejezés
%	pontosan N-szerfordul elő 

Megoldás

count(X, [], 0).
count(X, [E|L], N) :-
	  (
		 X = E -> count(X, L, S), N is S + 1
		 ; count(X, L, N)
	  ).

Komment

ETS elfogadta.