Bài giảng Chương 2: Kỹ thuật lập trình prolog (Prolog Programming Techniques) bao gồm những nội dung về cách biểu diễn list, số học, cách biểu diễn cấu trúc, điều khiển backtracking, xuất/nhập, một số vị từ thư viện quan trọng.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Chương 2: Kỹ thuật lập trình prolog (Prolog Programming Techniques)
- Chapter 2
KỸ THUẬT LẬP TRÌNH PROLOG
(Prolog Programming Techniques)
1
- Nội dung
Caùch bieåu dieãn list
Soá hoïc
Caùch bieåu dieãn caáu truùc
Ñieàu khieån backtracking
Xuaát/nhaäp
Moät soá vò töø thö vieän quan troïng
2
- CÁCH BIỂU DIỄN LIST
List là một cấu trúc dữ liệu đơn giản được dùng trong lập trình phi số
học. Một list là một chuỗi với số lượng bất kỳ của các phân tử .
Thí dụ: [ann, tennis, tom, skiing] là một list ở PROLOG
Tuy nhiên đấy chỉ là hình thức bên ngoài của list. Lưu ý rằng, mọi đối
tượng có cấu trúc ở PROLOG được diễn tả bằng cấu trúc cây. list cũng
vậy.
Một list rỗng được diễn tả bởi [ ]
Một list khác rỗng được coi như gồm hai thành phần:
Phần tử đầu tiên của list được gọi là đầu (head) của list
Phần con lại của list được gọi là đuôi (tail) của list
Trong thí dụ trên, ann là đầu của list và [ tenmis, tom, skiing] là đuôi
của list.
3
- Một cách tổng quát , head và tail của một list được phối
hợp lại thành ra một cấu trúc nhờ một hàm tử đặc biệt.
Việc chọn hàm tử này tuỳ thuộc vào Prolog cụ thể. Ở đây
giả định rằng đó là dấu chấm .
.( Head, Tail)
Thí dụ: .( ann, .( tennis,. ( tom, .(skiing, []))))
.
.
ann
.
tennis
.
tom
skiing
[ ]
4
- Một list mà chỉ gồm một phần tử tương đương với :
[skiing] = .(skiing, [ ])
Lối ký hiệu dấu chấm không dễ dùng bằng lối ký hiệu [ , ].
Lập trình viên có thể dùng cả hai lối ký hiệu, nhưng lối ký
hiệu dấu ngoặc vuông thông dụng hơn. Nhưng hãy nhớ rằng
các list được diễn tả bên trong bằng các cây nhị phân.
Các phần tử của một list cũng có thể là bất kỳ loại đối
tượng nào, kể cả các list. Đuôi của một list có thể được coi
như là một đối tượng.
Thí dụ: L = [ a,b,c ]
Tail = [b, c] và L = .(a, Tail )
5
- Trong lối ký hiệu dấu ngoặc vuông, Prolog đưa vào
dấu để tách biệt đầu và đuôi của list
L = [ a Tail ]
[ a,b,c ] = [ a [b,c] ] = [ a,b [c] ] = [ a,b,c [ ] ]
Tóm lại: Prolog cung cấp 3 cách viết :
[Item1, Item2, … ]
[Head Tail ]
[Item1, Item2, …… Others ]
6
- CÁC THAO TÁC TRÊN LIST
2.1 Quan heä thaønh vieân:
Vò töø member( X , L ) xeùt xem X coù phaûi laø moät phaàn töû cuûa
list L.
Thí duï: member( b, [ a,b,c ]) true
member( b, [ a| [b, c] ]) false
member( X, [ X _ ]).
member( X, [ Head Tail ]):- member( X, Tail).
7
- Ghép kề ( Concatenrtion)
Vị từ: conc(L1, L2 , L3 ): L3 là sự ghép kề L1 và L2.
Thí dụ : conc( [a,b ], [c,d ], [a,b,c,d] ) true
conc([], L , L ).
conc([ X L1], L2, [ X, L3 ]) :- conc( L1 , L2, L3).
Ta có thể dùng conc để phân rã một list thành rã hai list :
?- conc( L1, L2, [ a,b,c] ).
L1 = [ ]
L2 = [ a,b,c ]
L1 = [ a ]
L2 = [ b,c ]
L1 = [a,b ]
L2 = [ c ]
L1 = [ a,b,c ]
L2 = [ ]
8
- Thêm một phần tử vào list
Thêm một phần tử vào đầu của list, ta cần một procedure như
sau :
add( X, L , [ X L ] ). ( Sự kiện)
2.4 Xoá một phần tử ra khỏi list :
Xoá một phần tử X ra khỏi list L, có thể được lập trình như một
vị từ :
del(X , L , L1 )
del( X, [ X Tail ], Tail ).
del( X, [ Y Tail ] , [ Y Tail1] ) :- del( X , Tail , Tail1 ).
? - del( a, [ a,b,a,a ] , L ).
L = [ b,a,a ];
L = [ a,b,a ];
L = [ a,b,a ]
Ta có thể dùng vị từ del để định nghĩa thao tác thêm một phần tử
vào bất kỳ chỗ nào trong một list .
insert( X, List , BiggerList ) :- del( X, BiggerList, List ).
9
- Sublist
Vị từ này có hai đối số : sublist( S , L )
Vị từ xét xem list S có phải là một list con của List L không.
sublist( S, L ) :- conc(L1, L2, L), conc( S , L3 , L2 ).
L
L1 S L3
L2
10
- CÁC THAO TÁC TRÊN LIST
2.1 Quan heä thaønh vieân:
Vò töø member( X , L ) xeùt xem X coù phaûi laø moät
phaàn töû cuûa list L.
Thí duï: member( b, [ a,b,c ]) true
member( b, [ a| [b, c] ]) false
member( X, [ X _ ]).
member( X, [ Head Tail ]):- member( X, Tail).
11
- Hoán vị
Công dụng: sinh ra các hoán vị của một list.
Vị từ :
permutation( [ ], [ ]).
permutation( [X L], P ) :- permutation( L, L1), insert( X , L1, P ).
Vị từ insert đã định nghĩa ở phần trước.
?- permutation( [ a,b,c ], P).
p = [ a,b,c ];
p = [ a,c,b ]; 3!=6
p = [ b,c,a ];
p = [b,a,c ];
p = [ c,a,b ];
p = [ c,b,a ];
12
- SỐ HỌC
Các phương tiện để tính toán số ở Prolog khá đơn giản. Các toán tử có sẵn gồm:
+, -, *, /, mod
Lưu ý:
Trong Prolog khi viết X = 1 + 2, X được dùng đồng nhất với toán hạng 1 + 2
?- X = 1+ 2.
X=3
Toán tử is bắt buộc sự định trị của biểu thức số học đi sau nó:
?- X is 1 + 2
X=3
Số học có liên quan đến khi so sánh các trị số học.
?- 277*39 > 10000.
yes
Các toán tử số học so sánh:
>
<
>=
- Toán tử = ở X = Y khiến cho hai đối tượng X và Y hợp nhất với nhau
(khiến cho biến trong X và Y được gán trị cụ thể).
Trái lại toán tử X =:= Y khiến cho X và Y được định trị số học với hai
trị đem so sánh với nhau.
?- 1+2 =:= 2+1
yes
?- 1+2 = 2+1
no
Vài thí dụ:
Tìm ước số chung lớn nhất của 2 số nguyên, X, Y.
Nếu X = Y thì D = X
Nếu X < Y thì D là ước số chung lớn nhất của X và Y – X
Nếu Y < X thì giống như (2) những đổi vai trò Y và X
gcd(X,X,X).
gcd(X,Y,D):- X
- SỬ DỤNG CẤU TRÚC
Trong Prolog, ngoài list, cấu trúc (structure) là một phương
tiện lập trình khá mạnh để tạo cấu trúc dữ liệu.
Trong mục này, chúng ta học cách sử dụng cấu trúc qua một
thí dụ lập trình: bài toán Tám Con Hậu.
Bài toán 8 con hậu:
Đặt 8 con hậu trên một bàn cờ rộng ( 8 8 ô) sao cho không
có con hậu nào tấn công được các con hậu khác.
Lời giải sẽ được lập trình như một vị từ một đối số:
solution( Pos)
mà là đúng nếu Pos diễn tả một sắp xếp trong đó 8 con hậu
không thể tấn công nhau.
Có nhiều ý tưởng khác nhau cho bài toán này. Ta xem xét 3
chương trình khác nhau.
15
- Cách giải 1
Chương trình 1:
Vấn đề diễn tả bàn cờ.
Một ô trong bàn cờ được diễn tả bằng một cặp toạ độ
( X ,Y )
p(X ,Y)
Như vậy bài toán là tìm 1 list cặp tọa độ có dạng
[p( X1 , Y1) , p( X2 , Y2), … , p( X8 , Y8)] mà
thoả mãn đòi hỏi không tấn công.
16
- 1 2 3 4 5 6 7 8
[p(1,4) , p(2,2),
8 X p( 3,7), p(4,3) ,..,
p(7,5) , p(8,1)]
7 X laø moät lôøi giaûi
6 X
5 X
4 X
3 X
2 X
1 X
17
- Cách giải 1 (tt)
Quan hệ solution được định nghĩa bằng cách xem xét 2 trường
hợp:
Case1. list các con hậu rỗng: list rỗng là một lời giải vì không có sự tấn công.
Case2. List các con hậu khác rỗng: [p(X , Y)| Others]
Con hậu thứ nhất ở vị trí (X , Y) và những con hậu khác ở các ô được mô tả
bởi list Others. Nếu đây là một lời giải thì 3 điều kiện sau phải thoả:
Bản thân Others cũng là lời giải đối với bàn cờ nhỏ hơn (n – 1)(n – 1).
X và Y phải là số nguyên từ 1 đến 8.
Con hậu ở ô (X,Y) không tấn công bất cứ con hậu nào ở danh sách Others.
solution([p(X ,Y) I Others]):-
solution(Others),
member( Y, [1,2,3,4,5,6,7,8]),
noattack( p(X,Y), others).
18
- Cách giải 1 (tt)
Bây giờ cần phải định nghĩa điều kiện: “con hậu ở một ô
không tấn công một con hậu ở một ô khác”. Tức là không
cùng hàng, không cùng cột, và không cùng đường chéo.
Cái khuôn mẫu của lời giải sẽ đảm bảo các con hậu ở trên
các cột khác nhau. Do đó chỉ cần:
Các toạ độ Y của con hậu phải khác nhau
Chúng không cùng trên đường chéo tức là khoảng cách giữa các
ô theo trục X phải khác khoảng cách các ô theo trục Y.
19
- % solution( boardposition)
solution([ ]).
solution([ p(X , Y) I Others]):-
solution( Others), member(Y , [1,2,3,4,5,6,7,8]),
noattack(p(X,Y), Others).
noattack( _ , [ ]).
noattack(p(X,Y), [ p(X1,Y1) I Others]):-
Y =\= Y1 , Y1 – Y = \ = X1 – X , Y1 – Y =\= X – X1,
noattack(p(X , Y), Others).
member( I,[ I |_ ]).
member(I, [_I Rest]):- member(I , Rest).
?-solution([p(1,Y1),p(2,Y2),p(3,Y3),p(4,Y4), p(5,Y5),
p(6,Y6), p(7,Y7), p(8,Y8)]).
20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
