Lp trình lôgic trong Prolog 110
Prolog tr li :
N = 1 + (1 + (1 + (1 + 0)))
Yes
Phép cng do không c khi ng mt cách tng minh nên s- không bao
gi c th,c hin. Tuy nhiên, ta có th hoán (i hai ích ca mnh  th hai
trong length1 :
length1( [ ], 0 ).
length1( [ _ | Queue ], N ) :-
N = 1 + N1,
length1( Queue, N1 ).
K!t qu chy chng trình sau khi hoán (i v0n y ht nh c#. Bây gi, ta li
có th rút gn mnh  v ch" còn mt ích :
length1( [ ], 0 ).
length2( [ _ | Queue ], 1 + N ) :-
length2( Queue, N ).
K!t qu chy chng trình ln này v0n y ht nh c#. Prolog không a ra tr
li nh mong mun, mà là :
?- length1([ a, b, c, d], N).
N = 1+ (1+ (1+ (1+0)))
Yes
77 J,!+&
Chng trình sau ây to sinh và lit kê các s t, nhiên :
% Natural Numbers
nat(0).
nat(N) :- nat(M), N is M + 1.
Khi th,c hin các ích con trong câu h+i :
?- nat(N), write(N), nl, fail.
các s t, nhiên c to sinh liên ti!p nh k1 thut quay lui. Sau khi s t, nhiên
u tiên nat(N) c in ra nh write(N), h$ng fail bt buc th,c hin quay
lui. Khi ó, lut th hai c vn dng  to sinh s t, nhiên ti!p theo và c th!
ti!p tc cho !n khi NSD quy!t nh d'ng chng trình (^C).
Cu trúc danh sách 111
Tóm tt chng 4
• Danh sách là mt cu trúc hoc rng, hoc gm hai phn : phn u là mt
phn t và phn còn li là mt danh sách.
• Prolog qun lý các danh sách theo cu trúc cây nh phân. Prolog cho phép
s dng nhiu cách khác nhau  biu din danh sách.
[ Object1, Object2, ... ]
hoc [ Head | Tail ]
hoc [ Object1, Object2, ... | Others ]
Vi Tail và Others là các danh sách.
• Các thao tác c( in trên danh sách có th lp trình c là : kim tra mt
phn t có thuc v mt danh sách cho trc không, phép ghép hai danh
sách, b( sung hoc loi b+ mt phn t u hoc cui danh sách, trích ra
mt danh sách con...
Bài tp chng 4
1. Vi!t mt th tc s dng append  xóa ba phn t cui cùng ca danh sách
L, to ra danh sách L1. Hng d0n : L là phép ghép ca L1 vi mt danh sách
ca ba phn t (ã b xóa kh+i L).
2. Vi!t mt dãy các ích  xóa ba phn t u tiên và ba phn t cui cùng ca
mt danh sách L,  tr v danh sách L2.
3. )nh ngha quan h :
last_element( Object, List )
sao cho Object phi là phn t cui cùng ca danh sách List. Hãy vi!t
thành hai mnh , trong ó có mt mnh  s dng append, mnh  kia
không s dng append.
4. )nh ngha hai v t' :
even_length( List ) và odd_length( List )
c thõa mãn khi s các phân t ca danh sách List là ch*n hay l. tng
ng. Ví d danh sách :
[ a, b, c, d ] có  dài ch*n,
[ a, b, c ] có  dài l-.
5. Cho bi!t k!t qu Prolog tr li các câu h+i sau :
?- [1,2,3] = [1|X].
?- [1,2,3] = [1,2|X].
Lp trình lôgic trong Prolog 112
?- [1 | [2,3]] = [1,2,X].
?- [1 | [2,3,4]] = [1,2,X].
?- [1 | [2,3,4]] = [1,2|X].
?- b(o,n,j,o,u,r) =.. L.
?- bon(Y) =.. [X,jour].
?- X(Y) =.. [bon,jour].
6. Vi!t chng trình Prolog kim tra mt danh sách có phi là mt tp hp con
ca mt danh sách khác không ? Chng trình hot ng nh sau :
?- subset2([4,3],[2,3,5,4]).
Yes
7. Vi!t chng trình Prolog  ly ra các phn t t' mt danh sách. Chng
trình c#ng có th chèn các phn t vào mt danh sách hot ng nh sau :
?- takeout(3,[1,2,3],[1,2]).
Yes
?- takeout(X,[1,2,3],L).
X = 1
L = [2, 3] ;
X = 2
L = [1, 3] ;
X = 3
L = [1, 2] ;
No
?- takeout(4,L,[1,2,3]).
4
L = [4, 1, 2, 3] ;
L = [1, 4, 2, 3] ;
L = [1, 2, 4, 3] ;
L = [1, 2, 3, 4] ;
No
8. Vi!t v t' Prolog getEltFromList(L,N,E) cho phép ly ra phn t th N
trong mt danh sách. Tht bi n!u danh sách không có  N phn t. Chng
trình hot ng nh sau :
?- getEltFromList([a,b,c],0,X).
No
?- getEltFromList([a,b,c],2,X).
X = b
?- getEltFromList([a,b,c],4,X).
No
Cu trúc danh sách 113
9. Vi!t chng trình Prolog tìm phn t ln nht và phn t nh+ nht trong mt
danh sách các s. Chng trình hot ng nh sau :
?- maxmin([3,1,5,2,7,3],Max,Min).
Max = 7
Min = 1
Yes
?- maxmin([2],Max,Min).
Max = 2
Min = 2
Yes
10. Vi!t chng trình Prolog chuyn mt danh sách phc hp, là danh sách mà
mi phn t có th là mt danh sách con cha các danh sách con phc hp
khác, thành mt danh sách ph ng là danh sách ch" cha các phn t trong tt
c các danh sách con có th, gi nguyên th t, lúc u. Chng trình hot
ng nh sau :
flatten([[1,2,3],[4,5,6]], Flatlist).
Flatlist = [1,2,3,4,5,6]
Yes
flatten([[1,[hallo,[[aloha]]],2,[],3],[4,[],5,6]],
Flatlist)
Flatlist = [1, hallo, aloha, 2, 3, 4, 5, 6]
Yes
11. Vi!t các chng trình Prolog th,c hin các v t' x lý tp hp cho phn lý
thuy!t (mc II).
12. S dng v t' forall  vi!t chng trình Prolog kim tra hai danh sách có
ri nhau (disjoint) không ? Chng trình hot ng nh sau :
?- disjoint([a,b,c],[d,g,f,h]).
Yes
?- disjoint([a,b,c],[f,a]).
No
13. V t' forall(Cond, Action) th,c hin kim tra s, so khp tng ng
gia Cond, thng k!t hp vi v t' member, và Action. Ví d di ây
kim tra vic th,c hin các phép toán s hc trong danh sách L là úng n.
?- forall(member(Result = Formula, [2 = 1 + 1, 4 = 2 *
2]), Result =:= Formula).
Result = _G615
Formula = _G616
Yes
Lp trình lôgic trong Prolog 114
14. S dng v t' forall  vi!t chng trình Prolog kim tra mt danh sách
có là mt tp hp con ca mt danh sách khác hay không ? Chng trình
hot ng nh sau :
?- subset3([a,b,c],[c,d,a,b,f]).
Yes
?- subset3([a,b,q,c],[d,a,c,b,f])
No
15. S dng v t' append ghép hai danh sách  vi!t các chng trình Prolog
th,c hin các vic sau :
prefixe(L1, L2) danh sách L1 ng trc (prefixe list) danh sách L2.
suffixe(L1, L2) danh sách L1 ng sau (suffixe list) danh sách L2.
isin(L1, L2) các phn t ca danh sách L1 có mt trong danh sách L2.
16. S dng phng pháp Quicksort vi!t chng trình Prolog sp x!p nhanh mt
danh sách các s ã cho theo th t, t&ng dn.
17. )c hiu chng trình sau ây ri d,ng li thut toán :
/* Missionarys & Cannibals */
/* Tránh vòng lp */
lNotExist(_,[]).
lNotExist(X,[T|Q]) :-
X\==T, lNotExist(X,Q).
/* Kim tra tính hp lý ca trng thái */
valid(MG,CG,MD,CD) :-
MG>=0, CG>=0, MD>=0, CD>=0, MG=0, MD>=CD.
valid(MG,CG,MD,CD) :-
MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD=0.
valid(MG,CG,MD,CD) :-
MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD>=CD.
/* Xây d,ng cung và kim tra */
sail(1,0). sail(0,1). sail(1,1). sail(2,0). sail(0,2).
arc([left,MGi,CGi,MDi,CDi],[droite,MGf,CGf,MDf,CDf]) :-
sail(Mis,Can),
MGf is MGi-Mis, MDf is MDi+Mis,
CGf is CGi-Can, CDf is CDi+Can,
valid(MGf,CGf,MDf,CDf).
arc([right,MGi,CGi,MDi,CDi],[left,MGf,CGf,MDf,CDf]) :-
sail(Mis,Can),
MGf is MGi+Mis, MDf is MDi-Mis,
CGf is CGi+Can, CDf is CDi-Can,
valid(MGf,CGf,MDf,CDf).
/* Phép  quy */