第2章集合与序列

1、1 2集合论的产生集合论的产生: 18761883年间，年间， 康托康托（George Cantor 18451918年年, 德国数学家）对任德国数学家）对任意元素的集合进行了系统意元素的集合进行了系统的研究。康托被公认为集的研究。康托被公认为集合理论的创始人。合理论的创始人。 3456 A =0, 1, 2, 3。 自然数集自然数集N用列举法表示是用列举法表示是0, 1, 2, 3, 。 7 大于大于0小于小于1的实数集合：的实数集合： x | (0 x1)且且 xR ; 所有正奇数的集合：所有正奇数的集合： x | x2y+1且且 yN 。 891011 AA12 1314 设设Aa, e

2、, f , Ba, f, g, h 则：则： AB_ BA_ ?15B1642算法算法2.1.1：求两个集合交集的算法。求两个集合交集的算法。A1645234BC12452364依次扫描依次扫描A、B中的元素，若相同，则把其添加到中的元素，若相同，则把其添加到C中中紧凑存储方式下的集合运算的实现紧凑存储方式下的集合运算的实现217iBLength = length(B) /集合集合B的长度的长度 for(i=0;iiALength;i+) for(j=0;jiBLength;j+) if(Ai=Bj) Ck=Ai; /添加交集元素到交集添加交集元素到交集C中中 k+; break； Retur

3、n C; /集合集合C就是就是A与与B的交集的交集1842算法算法2.2.2：A1245234BC152364把把A中的元素加到中的元素加到C中，再扫描中，再扫描B，把其不再，把其不再A中中的元素加入的元素加入C。421563619iBLength = length(B) /集合集合B的长度的长度C=B；/用集合用集合C存储集合的并集，把存储集合的并集，把B中的元素赋值到中的元素赋值到C中中iCLength = iBLengthfor(i=0;iiALength;i+) bFind=false; for(j=0;jiBLength;j+) /循环循环1 if(Ai=Bj) bFind=true

4、; /Ai为公共元素；为公共元素； break； /跳出循环跳出循环1 if not bFind /Ai不是公共元素；不是公共元素； CiClength+1=Ai; /把把Ai加入到集合加入到集合C中；中； iClength=iClength+1; Return C; /集合集合C就是就是A与与B 的并集的并集20算法算法2.2.2：A1245234B234删除在删除在B中出现的中出现的A的元素。的元素。41562621iALength = length(A) /集合集合A的长度的长度iBLength = length(B) /集合集合B的长度的长度for(i=0;iiBLength;i+)

5、for(j=0;jn return false;i=1; j=1;while(i=m) and (j=n) if (ti = sj) /字符匹配字符匹配 i=i+1; j=j+1；if i=m+1 return true; /T是是S的子序列的子序列return false; S246783T473383940414243 44 12111121.( 1).nniijiij nnijknij k nAAAAAAAAAAAA 45 46500166350010055003335ABAB47 4849一个班里有一个班里有50个学生，在第一次考个学生，在第一次考试中有试中有26人得人得5分，在第二次考试分，在第二次考试中有中有21人得人得5分。如果两次考试中分。如果两次考试中都没得都没得5分的有分的有17人，那么在两次人，那么在两次考试都得考试都得5分的有多少人？分的有多少人？50在165个学生当中,8个人既学习微积分和心理学又学习计算机科学，33个人既学习微积分又学习计算