集合是由具有某些共同特征的元素构成的一个整体。在pascal中,一个集合是由具有同一有序类型的一组数据元素所组成,这一有序类型称为该集合的基类型。
一、集合类型的定义和变量的说明
集合类型的一般形式为:
set of 基类型;
基类型可以是任意顺序类型, 而不能是实型或其它构造类型。同时,基类型的数据的序号不得超过255。例如下列说明是合法的:
type numbers =set of 0..9;
ch=set of char;
day=(sun,mon,tue,wed,thu,fri,sat);
var s: numbers; c:ch; weekday:day;
可以将类型说明与变量说明合并在一起,如:
var s:set of 0..9; { 子界型 }
c:set of char;
weekday: (sun,mon,tue,wed,thu,fri,sat); { 枚举型 }
注意:集合的元素个数不超过256个,因此 var s:set of integer; 是错误的。
二、集合的值
1、集合的值放在一对方括号中,中间各元素之间用逗号隔开。如:[1,2,5] 和 ['a','e','i'] 都是集合。
2、在集合中可以没有任何元素,这样的集合称为空集。[] 空集
3、在集合中,如果元素的值是连续的,则可用子界型的表示方法表示。例如:
[1,2,3,4,5, 10,15] 可以表示成: [1..5,10,15]
4、集合的值与方括号内元素出现的次序无关。例如[1,5,8 ]和[5,1,8]的值相等。
5、在集合中同一元素的重复出现对集合的值没有影响。例如,[1,8,5,1,8]与[1,5,8]的值相等。
6、每个元素可用基类型所允许的表达式来表示。如 [1,1+2,4]、[succ(ch)]。
三、集合的运算
集合类型变量不能进行算术运算,集合是无序的,不能使用ord、pred、succ等函数。
1、赋值运算
只能通过赋值语句给集合变量赋值,不能通过读语句赋值,也不能通过写语句直接输出集合变量的值。如:
集合变量赋值: c:=['2']; i:=[5]; w:=[];
集合变量赋子界值: c:=['a'..'z']; i:=[1..7];
集合变量赋枚举值: c:=['a','b','d','m']; i:=[2,4,6,8,10];
2、集合的并、交、差运算
可以对集合进行并(+)、交(*)、差 (-)三种运算,每种运算只有一个运算符、两个运算对象,运算结果仍为集合。注意它们与算术运算的区别。
① 并运算 (关系代数运算符∪)
A,B为两个集合,由集合A中的元素加上集合B中的与A不重复的所有元素组成的集合,称为集合A和B的并。即A+B,如:
[X,Y,Z]+[X] 为 [X,Y,Z] { 两个集合中不重复的所有元素 }
[1]+[4] 为[1,4]
② 交运算 (关系代数运算符∩)
A,B为两个集合,由既属于集合A中的元素又属于集合B中的所有元素组成的集合,称为集合A和B的交。即A*B,如:
[X,Y,Z]*[X] 为 [X] { 两个集合中的相同元素 }
[X,Y,Z]*[M] 为 []
③差运算 (关系代数运算符-)
A,B为两个集合,由集合A中的元素除去集合B中与A相同的元素组成的集合,称为集合A和B的差。即AB,如:
[X,Y,Z]-[X] 为 [Y,Z ] { 在集合A中又不在集合B中的所有元素 }
[X,Y,Z]-[M] 为 [X,Y,Z]
3、集合的关系运算: 运算结果为布尔值
关系运算符: = 相等、<> 不相等、
>= 包含,表示前者蕴含后者,相当于集合论中的 。
<= 包含于,表示前者蕴含于后者,相当于集合论中的 。
例如:[a,b,c]=[b,c,a] 为true,元素个数相同,内容相同,不管排列顺序如何。
[a,b,c]>=[a] 为true;
[a,b]<=[a,b,c] 为true。
in运算:in的右边为集合,左边为与集合基类型相同的表达式,为布尔值。in测试一个元素是否在集合中。相当于集合论中的∈。它们都是二目运算,且前4个运算符的运算对象都是相容的集合类型。例如:a in[b,c] 为false。
设集合a:=[1..10]; x 为integer,如x在集合a中即删除a中的元素x,否则把元素x添加到集合a中。程序段如下:
if x in a then a:=a-[x] else a:=a+[x]
例1、设全集E={1,2,3,4,5},集合A={1,4},B={1,2,5},C={2,4},则集合
(A∩B)∪~C 为( )。 ( NOIP2003单选8 )
A)空集 B){1} C){3,5} D){1,5} E){1,3,5}
例2、输入一系列字符,对其中的数字字符、字母字符和其它字符分别计数。输入'?'后结束。
var ch:char;
letter:set of char;
digit:set of '0'..'9';
i,j,k:integer;
begin
letter:=['a'..'z','A'..'Z']; digit:=['0'..'9'];
i:=0; j:=0; k:=0;
repeat
read(ch);
if ch in letter
then i:=i+1
else if ch in digit then j:=j+1 else k:=k+1;
until ch='?';
writeln('letter:',i,'digit:',j,'other:',k)
end.
例3、求出2~n之间的素数。
由希腊数学家Eratosthense提出“筛法”,步骤如下:(以2到20为例)
①将所有的候选数放入筛子集合中;[1,2,3,4,…,20], 素数集合为 []。
②找筛中最小数(必为素数)next,放入素数集合中;
③将next的所有倍数从筛中筛去;
④重复②~③,直到筛空。素数集合中即所求。每次循环如下:
筛子集合 素数集合
[3,5,7,9,11,13,15,17,19] [2]
[5,7,11,13,17,19] [2,3]
[7,11,13,17,19] [2,3,5]
…… ……
[] [2,3,5,7,11,13,17,19]
const n=200;
var sieve,primes:set of 2..n;
j,next:integer;
begin
sieve:=[2..n]; primes:=[]; { 将所有的候选数放入筛中,素数集合置空 }
next:=2;
repeat
while not(next in sieve) do
next:=succ(next); { 找筛中最小数next }
primes:= primes+[next]; { 将筛中最小数next,放入素数集合中 }
j:=next;
while j<=n do
begin sieve:= sieve-[j]; j:=j+next end { 将next的倍数从筛中筛去 }
until sieve=[];
for next:=2 to n do
if next in primes then write(next:5); { 输出素数集合中的所有元素}
writeln
end.