1. Khai báo
– Một tập hợp thì gồm nhiều gía trị có chung một kiểu dữ liệu, gọi là kiểu cơ bản. Kiểu cơ bản phải là kiểu vô hướng đếm được, tức chỉ có thể là kiểu byte, ký tự , lôgic hay liệt kê.
– Số phần tử của tập hợp tối đa là 256 phần tử. Kiểu tập hợp được mô tả bằng từ khóa SET OF , kế đến là kiểu cơ bản của các phần tử.
* Khai báo gián tiếp:
TYPE Kky_tu = SET OF Char;
Kchu_hoa = SET OF ‘A’.. ‘Z’;
Kso = SET OF Byte;
Var TapA,TapB:Kky_tu; TapH:Kchu_hoa; TapS:Kso;
* Khai báo trực tiếp:
Var TapA,TapB: SET OF Char; TapH: SET OF ‘A’..‘Z’; TapS: SET OF Byte;
Chú ý: Các khai báo dưới đây là sai, vì kiểu cơ bản không thể là Integer, và nếu là đoạn con thì phạm vi của đoạn con không được vượt qúa phạm vi của kiểu Byte:
Var T1: SET OF Integer; T2: SET OF 1..256 ; LLL
2. Xác định một tập hợp
Một tập hợp được xác định bằng cách liệt kê các phần tử của nó, các phần tử được phân cách nhau bởi dấu phẩy, và đặt giữa hai dấu ngoặc vuông.
+ [ ] : tập rỗng
+ [3..6] : tập các số nguyên 4, 3, 5, 6
+ [3..6, 9, 12]: tập các số nguyên 3, 4, 5, 6, 9, 12
[‘A’..’C’, ‘X’, ‘Z’] : tập các chữ ‘A’, ‘B’, ‘C’, ‘X’, ‘Z’
Các phần tử của tập hợp có thể là biến hay biểu thức, ví dụ: [3, 5, i+j, 2*j]: tập hợp này có 4 phần tử là 3, 5, hai phần tử kia có gía trị bằng i+j và 2*j, trong đó i, j là các số nguyên sao cho i+j và 2*j nằm trong phạm vi từ 0 đến 255.
3. Các phép toán
3.1. Phép gán
Có thể gán một tập hợp cho một biến tập hợp cùng kiểu. Ví dụ, với các biến khai báo ở trên, có thể gán: TapA:=[‘1’..’5’, ‘9’, ‘A’];TapH:=[‘C’..’F’];TapS:=[15..20, 30, 40];
Tập rỗng [ ] gán cho biến tập hợp kiểu nào cũng được: TapA:=[ ]; TapH:=[ ];
L Lệnh gán dưới đây là sai vì hai vế không cùng kiểu dữ liệu:
TapA:=[1..8];TapS:=[‘1’..’9’];
3.2. Phép hợp
Hợp của hai tập hợp A và B, ký hiệu là A+B, là một tập hợp gồm các phần tử hoặc thuộc tập A hoặc thuộc tập B.
Ví dụ: [3..5]+[4..6,10, 15]=[3..6,10,15]
3.3. Phép giao
Giao của hai tập hợp A và B, ký hiệu là A*B, là một tập hợp gồm các phần tử đồng thời thuộc A và B. Ví dụ: [1..10]*[5..15] =[5..10]
3.4. Phép hiệu
Hiệu của hai tập hợp A và B, ký hiệu là A-B, là một tập hợp gồm các phần tử thuộc tập A nhưng không thuộc tập B.
Ví dụ: [1..10] – [5..15]=[1..4]
Nhận xét:
– Các phép toán trên chỉ thực hiện được khi A và B cùng kiểu, và kết qủa là một tập hợp C cùng kiểu với A và B. Phép thử IN (thuộc về): Dùng để kiểm tra xem một biến hay một gía trị có phải là phần tử của một tập hợp nào đó không. Biểu thức x IN TapA cho kết qủa là True nếu gía trị x thuộc TapA, cho gía trị False trong trường hợp ngược lại.
Ví dụ: ‘N’ IN [‘N’,‘n’] cho kết qủa là TRUE ‘y’ IN [‘N’, ‘n’] cho kết qủa là FALSE
– Các phép so sánh (=, , =): Cho A và B là hai tập hợp cùng kiểu, kết qủa của các phép so sánh A với B sẽ là TRUE hoặc FALSE. Phép bằng: A=B khi và chỉ khi mỗi phần tử của A đều thuộc B và mỗi phần tử của B đều thuộc A, trong trường hợp ngược lại, ta nói A khác B và viết AB.
Ví dụ: [3,2,4,5]= [2, 3..5] [‘A’, ‘B’][‘a’,’B’]
– Phép nhỏ hơn hoặc bằng: A<=B khi và chỉ khi mọi phần tử của A đều thuộc B.
Ví dụ: [3..5]<=[3..5] [3..5]<=[1..6]
– Phép lớn hơn hoặc bằng: A>=B khi và chỉ khi mọi phần tử của B đều thuộc A, nói cách khác A>=B khi và chỉ khi B<=A. [3..5]>=[3..5] [‘A’..’Z’]>=[‘A’..’D’]
Chú ý: Trong các tập hợp không có phép so sánh nhỏ hơn (<) và lớn hơn (>). Khi cần so sánh lớn hơn hay nhỏ hơn ta có thể viết:
If (AB) then writeln(‘A < B’); If (A>=B) and ( AB) then writeln(‘A > B’);
4. Các ví dụ
Ví dụ 1: Nhập vào một chuỗi St , cho biết trong St có những chữ hoa nào.
Giả sử: St=‘ABc3BAFdzA’ thì có các chữ hoa là A, B, F.
Ví dụ 2: Nhập N số nguyên trong phạm vi từ 0 đến 255. In ra các tập số chẵn, lẻ và cho biết có bao nhiêu số chẵn, bao nhiêu số lẻ (các số trùng nhau chỉ kể 1 lần).
Giả sử: Nhập 9 số : 1, 2, 3, 4, 1, 2, 3, 4, 5 thì có hai số chẵn là 2 và 4 và có 3 số lẻ là 1, 3, 5.
Ví dụ 3. Tìm các số nguyên tố số nguyên dương N cho trước.
Có nhiều cách giải khác nhau, dưới đây giới thiệu phương pháp của Eratosthene, sử dụng dữ liệu kiểu tập hợp và không cần đến các phép toán nhân.
Xuất phát từ tập số nguyên S=[2..N] ta loại ra số nguyên tố đầu tiên và tất cả các bội số của nó ra khỏi S, lặp lại quá trình trên cho đến khi S thành tập rỗng.
Ví dụ: S=[2..15];
Bước 1:
– Đưa 2 vào tập số nguyên tố, Tapsnt:=[2]
– Loại 2 và các bội của 2 ra khỏi S, ta được S=[3,5,7,9,11,13,15 ]
Bước 2:
– Đưa 3 vào tập số nguyên tố, Tapsnt:=[2,3]
– Loại 3 và các bội của 3 ra khỏi S, được S=[5,7,11,13 ]
Bước 3:
– Đưa 5 vào tập số nguyên tố, Tapsnt:=[2,3,5]
– Loại 5 và các bội của 5 ra khỏi S, được S=[7,11,13 ]
Bước 4:
– Đưa 7 vào tập số nguyên tố, Tapsnt:=[2,3,5,7]
– Loại 7 và các bội của 7 ra khỏi S, được S=[11,13 ]
Bước 5:
– Đưa 11 vào tập số nguyên tố, Tapsnt:=[2,3,5,7,11]
– Loại 11 và các bội của 11 ra khỏi S, được S=[13 ]
Bước 6:
– Đưa 13 vào tập số nguyên tố, Tapsnt:=[2,3,5,7,11,13]
– Loại 13 và các bội của 13 ra khỏi S, được S=[ ]
Kết qủa được Tapsnt = [2,3,5,7,11,13]. Tập S giống như một cái sàng để lọc và loại ra các số không phải số nguyên tố.
