Kiểu dữ liệu tập hợp (set) trong Pascal
- Thứ sáu - 31/07/2020 10:21
- In ra
- Đóng cửa sổ này
Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất. Trong Pascal, điều đó có nghĩa là có cùng một mô tả kiểu, kiểu này được gọi là kiểu cơ bản. Kiểu cơ bản bắt buộc phải là một kiểu vô hướng hay một đoạn con và không được là số thực. Các đối tượng này được gọi là các phần tử của tập. Số phần tử cực đại cho phép có thể còn phụ thuộc vào từng chương trình dịch Pascal của các hãng khác nhau.
1. KIỂU TẬP HỢP
Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất. Trong Pascal, điều đó có nghĩa là có cùng một mô tả kiểu, kiểu này được gọi là kiểu cơ bản. Kiểu cơ bản bắt buộc phải là một kiểu vô hướng hay một đoạn con và không được là số thực. Các đối tượng này được gọi là các phần tử của tập. Số phần tử cực đại cho phép có thể còn phụ thuộc vào từng chương trình dịch Pascal của các hãng khác nhau. Ví dụ: Trong Turbo Pascal sô này là 256. Khái niệm tập hợp trong ngôn ngữ Pascal gắn liền với khái niệm tập hợp trong toán học.
Để mô tả kiểu và khai báo biến kiểu tập hợp, người ta dùng từ khóa SET OF theo sau là kiểu cơ bản T (kiểu của các phần tử của tập).
- Ví dụ:
TYPE
ALPHABET = SET OF CHAR;
CHU_SO = SET OF 0..9;
NGAY = (Hai, Ba, Tu, Nam, Sau, Bay, ChuNhat);
VAR
A, B, C,: SET OF 0..300;
L: ALPHABET;
SN: CHU_SO;
NGAY_LV: SET OF NGAY;
2. XÁC LẬP MỘT TẬP
Một tập hợp được xác lập bằng cách liệt kê các phần tử của tập hợp, chúng cách nhau bằng dấu phẩy và được đặt giữa hai dấu móc vuông. Ví dụ với các biến đã được khai báo ở trên, ta có thể viết các tập:
[ ]; {Tập rỗng, không có phần tử}
[3..5]; {Tập các chữ số 3,4,5}
[3,4,5,8] hoặc [3..5,8];
[‘A’..’C’,’Y’,’Z’];
[HAI...TU, Chunhat] {Tập hợp số ngày trong tuần}
Bản thân các phần tử của tập cũng có thể cho bằng biến hoặc bằng biểu thức: [X + Y, I*J, 3,4] biểu diễn tập hợp các số nguyên gồm số 3 và 4, và các số nguyên nhận được qua giá trị biểu thức X + Y và I * J (với X, Y, I, J là các số nguyên).
Khác với kiểu Array, ta không thể truy xuất trực tiếp đến từng phần tử của một tập hợp. Trong tập hợp không tồn tại thứ tự. Khi xét đến tập hợp người ta chỉ quan tâm xem một phần tử có nằm trong tập hợp không chứ không quan tâm nó nằm vị trí nào trong tập hợp.
3. CÁC PHÉP TOÁN TRÊN TẬP
a) Phép gán
Các giá trị có được từ các biểu thức xác lập một tập hợp có thể gán cho các biến có kiểu là tập hợp và kiểu cơ bản của chúng đương nhiên phải là giống nhau.
- Ví dụ:
Với mô tả và khai báo ở trên, ta có thể viết các câu lệnh:
A := [3..5];
B := [4-6,10,123];
C := A;
L := [‘A’,’B’,’D’];
L := [‘A’, ‘D’, ‘M’, ‘P’];
NGAY_LV := [Ba,Sau];
L := [ ] [tập rỗng, không có phần tử]
- Tập rỗng có thể đem gán cho mọi biến kiểu tập khác nhau.
- Chúng ta không thể gán L := [3,5] vì kiểu cơ bản của chúng không tương thích với nhau.
b) Phép hợp. Phép hợp được kí hiệu bằng dấu +
Hợp của hai tập A, B là một tập có các phần tử bao gồm tất cả các phần tử thuộc hai tập.
■ Ví dụ:
A := [3, 51
B := “= [4..6, 10, 12, 22];
C := A + B; {Tập C sẽ là [3..6, 10, 12, 22]}
c) Phép giao. Phép giao được kí hiệu bằng dấu *
Giao của hai tập A, B là một tập C có các phần tử chung của A và B nghĩa là các phần tử của C vừa nằm trong A vừa nằm trong B.
■ Ví dụ:
C := A * B; {Tập C sẽ là [4, 5]}
d) Phép hiệu. Phép hiệu được kí hiệu bằng dấu
Hiệu của hai tập là một tập có các phần tử thuộc tập thứ nhất nhưng không có trong tập thứ hai.
■ Ví dụ:
C := A - B; {Tập C sẽ là [3]}
C := B - A; {Tập C sẽ là [6, 10, 12, 22]}
e) Phép thử “thuộc về”
Là một phép thử để xem một biến hay một giá trị có thuộc một tập nào đó không. Kết quả của phép thuộc về có kiểu là Boolean. Phép thử này dùng với từ khóa IN.
■ Ví dụ:
Để thử xem biến Ch (Kiểu Char) có nằm trong câu trả lời Có bằng tiếng Việt hoặc bằng tiếng Anh là Yes hay không, bằng cách thử thông thường ta viết:
Readln (Ch);
If (Ch = 'Y') or (Ch = 'y') or (Ch = 'C') or (Ch = 'c') then...
Song ta có thể viết gọn lại với phép thử IN như sau:
If Ch IN ['Y', y, 'C, 'c'] then...
Hoặc nếu dùng một biến A (kiểu tập)
A := ['Y', ‘y’,’C','c'];
If Ch IN A then...
f) Các phép so sánh <>, =, <=, >=
Hai tập được đem ra so sánh bằng các phép toán so sánh này trước hết phải có cùng kiểu cơ bản. Kết quả của các phép so sánh này là giá trị kiểu Boolean, tức là TRUE hoặc FALSE.
Hai tập là bằng nhau nếu chúng có các phần tử như nhau từng đôi một (không kể thứ tự sắp xếp các phần tử trong hai tập). Ngược lại với phép = là phép so sánh khác nhau <>.
■ Ví dụ:
A := [3, 5, 9];
B := [9, 3, 5];
If A = B then Writeln (’Hai tap A va B bang nhau !’)
Else Writeln ('Tap A khac tap B !');
Phép so sánh <= (nhỏ hơn hoặc bằng nhau) sẽ có giá trị là True nếu tất cả các phần tử tập thứ nhất thuộc tập thứ hai.
Phép so sánh >= (lớn hơn hoặc bằng nhau) sẽ có giá trị là True nếu tất cả các phần tử tập thứ hai đều thuộc tập thứ nhất.
Cần lưu ý là trong Pascal không tồn tại phép so. sánh nhỏ hơn < và lớn hơn >. Muốn so sánh lớn hơn hay nhỏ hơn ta có thể dùng thủ thuật sau:
If (A <= B) and (A <> B) then Writeln (‘A < B');
Để thử xem hai tập A và B có phần tử nào chung không, ta có thể dùng phép thử:
If A* B = [1 ] then Writeln (A và B khong co phan tu chung');
4. GHI ĐỌC VÀ ĐỌC DỮ LIỆU KIỂU TẬP
Lệnh Read và Write không cho phép đọc và viết trực tiếp dữ liệu kiểu tập hợp. Song ta có thể lập chương trình thực hiện các thao tác này khi mà kiểu cơ bản của tập hợp là số nguyên, kí tự.
a. Ví dụ:
Đọc vào n kí tự để xây dựng một tập các kí tự Alpha nghĩa là xác định xem trong số n kí tự được đưa vào có các loại kí tự nào được gõ vào (không kể số lần gõ). Sau đó in ra kết quả.
TYPE
ALPHBET = SET OF 'A'..'Z';
VAR
A,B: ALPHBET;
I, N: INTEGER;
Ch : CHAR;
BEGIN
A:= [ ];
Write ('Enter n :’);
Readln (n);
FOF I := 1 TO n DO
Begin
Readln (Ch);
Ch:= Upcase (Ch);
A:= A + [Ch];
End;
Writeln ('Cac chu trong tap A la:');
FOR Ch := 'A' TO ’Z' do
If Ch IN Then Writeln (Ch);
END.
5. VÍ DỤ ỨNG DỤNG
• Tính các số nguyên tố:
Có nhiều thuật toán khác nhau để tìm các số nguyên tố. Chương trình sau tạo ra một tập hợp các số nguyên tố trong phạm vi từ 1 đến n theo phương pháp Eratosthene, nó được chọn vì tính đơn giản, không cần đến các phép nhân. Thuật toán như sau: xuất phát từ một tập các số nguyên từ 1 đến n. Mỗi lần gặp một số nguyên tố, ta sẽ loại trừ ra khỏi tập này tất cả các số là bội của số nguyên tố này. (Tương truyền rằng Eratosthene là một nhà bác học thời chưa có giấy viết. Vì vậy bài toán tìm số nguyên tố được ông sáng tác và thực hiện trên mặt đất: ông kẻ một dãy ô, trong đó ghi các số tự nhiên từ 1 đến N. Sau đó số nào không phải là số nguyên tố thì bị loại ra bằng cách lấy que chọc một lỗ vào đó để xóa nó đi. Kết quả trên mặt đất lỗ chỗ như một cái sàng, sàng lọc các số).
Trong thí dụ trên cần lưu ý sự khác nhau giữa cách viết dòng lệnh:
While not (number IN Sang) DO Number:= Number + 1;
với cách viết không đúng:
While not Number Sang DO Number:= Number + 1;
Vì lúc này toán tử Not Not sẽ được thực hiện trước và là toán tử Not số học, còn cách viết đầu là toán tử logic.
• Kết hợp các cấu trúc dữ liệu với kiểu tập:
Chúng ta có thề kết hợp kiểu tập với các kiểu cấu trúc dữ liệu khác như mảng trong các ví dụ sau:
PROGRAM Sang_Eratosthene;
CONST
N = 100
TYPE
Nguyen = l..n;
VAR
Nguyen_to, Sang: Set of Nguyen;
Number: Nguyen;
I: Integer;
BEGIN
Nguyen_to:= [ ];
Sang:= [2..n];
Number:= 2
Repeat
While not (Number IN Sang) Do Number Number + 1;
Nguyen_to := Nguyen_to + [Number ];
Write (Number, ' ’);
I:= Number;
While I <= n Do
Begin
Sang:= Sang - [I];
I := I + Number;
End;
Until Sang = [ 1;
END.
Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất. Trong Pascal, điều đó có nghĩa là có cùng một mô tả kiểu, kiểu này được gọi là kiểu cơ bản. Kiểu cơ bản bắt buộc phải là một kiểu vô hướng hay một đoạn con và không được là số thực. Các đối tượng này được gọi là các phần tử của tập. Số phần tử cực đại cho phép có thể còn phụ thuộc vào từng chương trình dịch Pascal của các hãng khác nhau. Ví dụ: Trong Turbo Pascal sô này là 256. Khái niệm tập hợp trong ngôn ngữ Pascal gắn liền với khái niệm tập hợp trong toán học.
Để mô tả kiểu và khai báo biến kiểu tập hợp, người ta dùng từ khóa SET OF theo sau là kiểu cơ bản T (kiểu của các phần tử của tập).
- Ví dụ:
TYPE
ALPHABET = SET OF CHAR;
CHU_SO = SET OF 0..9;
NGAY = (Hai, Ba, Tu, Nam, Sau, Bay, ChuNhat);
VAR
A, B, C,: SET OF 0..300;
L: ALPHABET;
SN: CHU_SO;
NGAY_LV: SET OF NGAY;
2. XÁC LẬP MỘT TẬP
Một tập hợp được xác lập bằng cách liệt kê các phần tử của tập hợp, chúng cách nhau bằng dấu phẩy và được đặt giữa hai dấu móc vuông. Ví dụ với các biến đã được khai báo ở trên, ta có thể viết các tập:
[ ]; {Tập rỗng, không có phần tử}
[3..5]; {Tập các chữ số 3,4,5}
[3,4,5,8] hoặc [3..5,8];
[‘A’..’C’,’Y’,’Z’];
[HAI...TU, Chunhat] {Tập hợp số ngày trong tuần}
Bản thân các phần tử của tập cũng có thể cho bằng biến hoặc bằng biểu thức: [X + Y, I*J, 3,4] biểu diễn tập hợp các số nguyên gồm số 3 và 4, và các số nguyên nhận được qua giá trị biểu thức X + Y và I * J (với X, Y, I, J là các số nguyên).
Khác với kiểu Array, ta không thể truy xuất trực tiếp đến từng phần tử của một tập hợp. Trong tập hợp không tồn tại thứ tự. Khi xét đến tập hợp người ta chỉ quan tâm xem một phần tử có nằm trong tập hợp không chứ không quan tâm nó nằm vị trí nào trong tập hợp.
3. CÁC PHÉP TOÁN TRÊN TẬP
a) Phép gán
Các giá trị có được từ các biểu thức xác lập một tập hợp có thể gán cho các biến có kiểu là tập hợp và kiểu cơ bản của chúng đương nhiên phải là giống nhau.
- Ví dụ:
Với mô tả và khai báo ở trên, ta có thể viết các câu lệnh:
A := [3..5];
B := [4-6,10,123];
C := A;
L := [‘A’,’B’,’D’];
L := [‘A’, ‘D’, ‘M’, ‘P’];
NGAY_LV := [Ba,Sau];
L := [ ] [tập rỗng, không có phần tử]
- Tập rỗng có thể đem gán cho mọi biến kiểu tập khác nhau.
- Chúng ta không thể gán L := [3,5] vì kiểu cơ bản của chúng không tương thích với nhau.
b) Phép hợp. Phép hợp được kí hiệu bằng dấu +
Hợp của hai tập A, B là một tập có các phần tử bao gồm tất cả các phần tử thuộc hai tập.
■ Ví dụ:
A := [3, 51
B := “= [4..6, 10, 12, 22];
C := A + B; {Tập C sẽ là [3..6, 10, 12, 22]}
c) Phép giao. Phép giao được kí hiệu bằng dấu *
Giao của hai tập A, B là một tập C có các phần tử chung của A và B nghĩa là các phần tử của C vừa nằm trong A vừa nằm trong B.
■ Ví dụ:
C := A * B; {Tập C sẽ là [4, 5]}
d) Phép hiệu. Phép hiệu được kí hiệu bằng dấu
Hiệu của hai tập là một tập có các phần tử thuộc tập thứ nhất nhưng không có trong tập thứ hai.
■ Ví dụ:
C := A - B; {Tập C sẽ là [3]}
C := B - A; {Tập C sẽ là [6, 10, 12, 22]}
e) Phép thử “thuộc về”
Là một phép thử để xem một biến hay một giá trị có thuộc một tập nào đó không. Kết quả của phép thuộc về có kiểu là Boolean. Phép thử này dùng với từ khóa IN.
■ Ví dụ:
Để thử xem biến Ch (Kiểu Char) có nằm trong câu trả lời Có bằng tiếng Việt hoặc bằng tiếng Anh là Yes hay không, bằng cách thử thông thường ta viết:
Readln (Ch);
If (Ch = 'Y') or (Ch = 'y') or (Ch = 'C') or (Ch = 'c') then...
Song ta có thể viết gọn lại với phép thử IN như sau:
If Ch IN ['Y', y, 'C, 'c'] then...
Hoặc nếu dùng một biến A (kiểu tập)
A := ['Y', ‘y’,’C','c'];
If Ch IN A then...
f) Các phép so sánh <>, =, <=, >=
Hai tập được đem ra so sánh bằng các phép toán so sánh này trước hết phải có cùng kiểu cơ bản. Kết quả của các phép so sánh này là giá trị kiểu Boolean, tức là TRUE hoặc FALSE.
Hai tập là bằng nhau nếu chúng có các phần tử như nhau từng đôi một (không kể thứ tự sắp xếp các phần tử trong hai tập). Ngược lại với phép = là phép so sánh khác nhau <>.
■ Ví dụ:
A := [3, 5, 9];
B := [9, 3, 5];
If A = B then Writeln (’Hai tap A va B bang nhau !’)
Else Writeln ('Tap A khac tap B !');
Phép so sánh <= (nhỏ hơn hoặc bằng nhau) sẽ có giá trị là True nếu tất cả các phần tử tập thứ nhất thuộc tập thứ hai.
Phép so sánh >= (lớn hơn hoặc bằng nhau) sẽ có giá trị là True nếu tất cả các phần tử tập thứ hai đều thuộc tập thứ nhất.
Cần lưu ý là trong Pascal không tồn tại phép so. sánh nhỏ hơn < và lớn hơn >. Muốn so sánh lớn hơn hay nhỏ hơn ta có thể dùng thủ thuật sau:
If (A <= B) and (A <> B) then Writeln (‘A < B');
Để thử xem hai tập A và B có phần tử nào chung không, ta có thể dùng phép thử:
If A* B = [1 ] then Writeln (A và B khong co phan tu chung');
4. GHI ĐỌC VÀ ĐỌC DỮ LIỆU KIỂU TẬP
Lệnh Read và Write không cho phép đọc và viết trực tiếp dữ liệu kiểu tập hợp. Song ta có thể lập chương trình thực hiện các thao tác này khi mà kiểu cơ bản của tập hợp là số nguyên, kí tự.
a. Ví dụ:
Đọc vào n kí tự để xây dựng một tập các kí tự Alpha nghĩa là xác định xem trong số n kí tự được đưa vào có các loại kí tự nào được gõ vào (không kể số lần gõ). Sau đó in ra kết quả.
TYPE
ALPHBET = SET OF 'A'..'Z';
VAR
A,B: ALPHBET;
I, N: INTEGER;
Ch : CHAR;
BEGIN
A:= [ ];
Write ('Enter n :’);
Readln (n);
FOF I := 1 TO n DO
Begin
Readln (Ch);
Ch:= Upcase (Ch);
A:= A + [Ch];
End;
Writeln ('Cac chu trong tap A la:');
FOR Ch := 'A' TO ’Z' do
If Ch IN Then Writeln (Ch);
END.
5. VÍ DỤ ỨNG DỤNG
• Tính các số nguyên tố:
Có nhiều thuật toán khác nhau để tìm các số nguyên tố. Chương trình sau tạo ra một tập hợp các số nguyên tố trong phạm vi từ 1 đến n theo phương pháp Eratosthene, nó được chọn vì tính đơn giản, không cần đến các phép nhân. Thuật toán như sau: xuất phát từ một tập các số nguyên từ 1 đến n. Mỗi lần gặp một số nguyên tố, ta sẽ loại trừ ra khỏi tập này tất cả các số là bội của số nguyên tố này. (Tương truyền rằng Eratosthene là một nhà bác học thời chưa có giấy viết. Vì vậy bài toán tìm số nguyên tố được ông sáng tác và thực hiện trên mặt đất: ông kẻ một dãy ô, trong đó ghi các số tự nhiên từ 1 đến N. Sau đó số nào không phải là số nguyên tố thì bị loại ra bằng cách lấy que chọc một lỗ vào đó để xóa nó đi. Kết quả trên mặt đất lỗ chỗ như một cái sàng, sàng lọc các số).
Trong thí dụ trên cần lưu ý sự khác nhau giữa cách viết dòng lệnh:
While not (number IN Sang) DO Number:= Number + 1;
với cách viết không đúng:
While not Number Sang DO Number:= Number + 1;
Vì lúc này toán tử Not Not sẽ được thực hiện trước và là toán tử Not số học, còn cách viết đầu là toán tử logic.
• Kết hợp các cấu trúc dữ liệu với kiểu tập:
Chúng ta có thề kết hợp kiểu tập với các kiểu cấu trúc dữ liệu khác như mảng trong các ví dụ sau:
PROGRAM Sang_Eratosthene;
CONST
N = 100
TYPE
Nguyen = l..n;
VAR
Nguyen_to, Sang: Set of Nguyen;
Number: Nguyen;
I: Integer;
BEGIN
Nguyen_to:= [ ];
Sang:= [2..n];
Number:= 2
Repeat
While not (Number IN Sang) Do Number Number + 1;
Nguyen_to := Nguyen_to + [Number ];
Write (Number, ' ’);
I:= Number;
While I <= n Do
Begin
Sang:= Sang - [I];
I := I + Number;
End;
Until Sang = [ 1;
END.