Pascal - Kiểu tập hợp

KIỂU TẬP HỢP 15.1.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ử. Ví dụ: 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; Các tập hợp TapA, TapB, TapH, TapS nói trên cũng có thể khai báo trực tiếp như sau: Var TapA, TapB : SET OF Char; TapH : SET OF ‘A’.. ‘Z’; TapS : SET OF Byte; Chú ý rằng 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 ; 15.1.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. 15.1.3. Các phép toán : 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ệ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’]; 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] 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] 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ú ý rằng 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’); 15.1.4. Các ví dụ : Ví dụ 15.1: Nhập vào một chuỗi St , cho biết trong St có những chữ hoa nào. Ví dụ St=‘ABc3BAFdzA’ thì có các chữ hoa là A, B, F. PROGRAM VIDU15_1; Var Taphoa : Set of ‘A’..’Z’; N, i: byte; ch : char; St : String; Begin Write(‘ Nhập chuỗi St: ‘); Readln(St); Taphoa:=[]; N:=length(St); For i:=1 to N do if St[i] IN [‘A’..’Z’] then Taphoa := Taphoa+[ St[i] ]; Writeln(‘ Cac chu hoa co trong St la :’); For ch:=‘A’ to ‘Z’ do if ch IN Taphoa then write(ch:3); Readln; End. Ví dụ 15.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). Ví dụ, 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. PROGRAM VIDU15_2; Const N=10; Var Tapchan, Taple : Set of byte; N1, N2, i, k: byte; Begin Tapchan:=[]; Taple:=[]; For i:=1 to N do begin Write(‘Nhap so thu ‘, i, ‘: ‘); Readln(k); If odd(k)=False then Tapchan:=Tapchan+[k] else Taple:=Taple+[k]; end; writeln(‘ Các số chẵn là: ‘); N1:=0; For i:=0 to (255 div 2) do if 2*i IN Tapchan then begin Write(2*i : 3); N1:=N1+1; end; Writeln( ‘ Co ‘, N1, ‘ số chẵn’); Writeln(‘ Các số lẻ là: ‘); N2:=0; For i:=0 to (255 div 2) do if (2*i +1) IN Taple then begin Write(2*i+1 : 3); N2:=N2+1; end; writeln( ‘ Co ‘, N2, ‘ số lẻ’); Readln; End. Ví dụ 15.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ố. Chương trình cụ thể như sau: PROGRAM VIDU15_3; Const N=20; Var Tapsnt, S: Set of 1..N; snt, i: Integer; Begin S:=[2..N]; Tapsnt:=[]; snt:=2; { so nguyen to nho nhat } Writeln(‘ Cac so nguyen to la :’ ); Repeat { tim snt la so nho nhat trong S} While Not (snt IN S) do snt:=snt+1; Tapsnt:= Tapsnt+[snt]; { dua vao Tapsnt } Write(snt:4); { Loại các bội của snt ra khỏi S } i:=snt; While i<=N do begin S:=S - [i]; i:=i+snt; end; Until S=[]; Readln; End.