离散数学集合与序列

离散数学集合与序列第一页，共二十五页，2022年，8月28日集合定义集合就是具有共同属性的对象集合，其中每一个对象称为集合的元素。集合中元素的个数称之为集合长度。集合中元素是无序的、不可重复的。第二页，共二十五页，2022年，8月28日集合运算则A与B的并集为A∪B，A与B的交集A∩B，A的补-AA与B的差A-B：

A-B：A∩（-B）第三页，共二十五页，2022年，8月28日集合运算和实现算法：求两个集合交集的算法：//求出集合A和B的交集FindIntersection(setA,setB){iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;i<iALength;i++){for(j=0;j<iBLength;j++)if(A[i]==B[j]){//添加交集元素到交集C中C[k]=A[i];k++;break；}}ReturnC;//集合C就是AB交集}第四页，共二十五页，2022年，8月28日集合运算和实现算法：求两个集合交集的算法：算法：求两个集合并集的算法：FindUnion(setA,setB)//求出集合A和B的并集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度C=B；//用集合C存储集合的并集，//把B中的元素赋值到C中。for(i=0;i<iALength;i++){bFind=false;for(j=0;j<iBLength;j++)//循环1if(A[i]==B[j]){bFind=true;//A[i]为公共元素；break；//跳出循环1}Ifnotfind////A[i]不是为公共元素；

C[iBlength+1]=A[i];//把A[i]加入到集合B中；

iClength=iClength+1;}ReturnC;//集合B就是AB并集}第五页，共二十五页，2022年，8月28日集合运算和实现算法：求两个集合交集的算法：算法：集合减法运算算法：FindDeference(setA,setB)//求出集合A-B的差集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;i<iBLength;i++){for(j=0;j<iALength;j++)if(A[j]==B[i]){从集合A中去掉元素A[i]；//具体算法不列出Break；}}ReturnA;//集合A就是AB的差集}第六页，共二十五页，2022年，8月28日集合运算和性质算法：求两个集合交集的算法：交换律：

A∩B=B∩A A∪B=B∪A结合律：（A∩B）∩C=A∩（B∩C） （A∪B）∪C=A∪（B∪C）分配律：

A∩（B∪C）=（A∩B）∪（B∩C）

A∪（B∩C）=（A∪B）∩（B∪C）摩根定律：

-（A∪B）=-A∩-B-（A∩B）=-A∪-BA-(B∪C)=(A-B)∩(A-C) A-(B∩C)=(A-B)∪(A-C)通过这些性质，可以看出实现同一集合运算有不同算法。第七页，共二十五页，2022年，8月28日集合运算和性质例2.3.1：集合A表示班级男生集合，B是离散数学考试及格的同学，C是数据结构考试及格的同学。求出至少有一门考试不及格的男同学。

第八页，共二十五页，2022年，8月28日集合运算和性质(A-B)表示离散数学考试不及格的男同学。(A-C)表示数据结构考试不及格的男同学至少有一门考试不及格的男同学可以表示为：(A-C)∪(A-B)。根据摩根定律可知：(A-C)∪(A-B)=A-(B∩C)。第九页，共二十五页，2022年，8月28日集合运算和性质//找出至少有一门考试不及格的男同学//A表示班级男生集合//B是离散数学考试及格的同学//C是数据结构考试及格的同学。FinsMaleNotPa∈（setA，setB，setC）{//求出BC的交集

setD=FindIntersection(B,C)；

//A-(B∩C)FindDeference(setA,setD)//求出集合A-B的差集}第十页，共二十五页，2022年，8月28日集合运算和性质例：学生20人，学号分别为1-20；集合A为选修离散数学的学生，集合B为成绩不及格的学生，集合C为女生。找出。要求：写出所有选修离散数学，成绩不及格的男生的集合D的表示，并写出求集合D中元素的算法。解:D=E-(A∩B)FindD{SetE=FindIntersection(setA,setB);D=FindDeference(setE,setC)}第十一页，共二十五页，2022年，8月28日集合运算和性质例：集合A表示借阅图书《离散数学》的学生，集合B表示借阅图书《数据结构》的学生，C表示目前没有图书馆书籍的学生，写出目前至少还有一本图书没有归还的学生的集合D；解:算法A∪B：借阅过图书的学生。至少还有一本图书没有归还的学生的集合D：D=A∪B-CFindD{SetE=FindUnion(setA,setB);D=FindDeference(setE,setC)}第十二页，共二十五页，2022年，8月28日序列与串序列也是信息处理中常用到一种数学工具，一个序列是考虑了元素顺序的一个列表，与集合相比，序列中允许元素重复。在数列中元素的顺序是十分重要的，一般用下标法标注元素在序列中的位置，如序列S：2，4，6，8，…,2n则s1=2，s2=3，s3=6，…如序列T：a，a，b，c，…则t1=a，t2=a，t3=b，…一个序列中元素的个数为序列长度。第十三页，共二十五页，2022年，8月28日子序列定义2.4.1:对序列S=s1,s2,s3,…,sn,T=sm1sm2,…,smk，如sm1sm2,…,smk都是s1,s2,s3,…,sn中元素，且m1,m2,…,mk是递增的，则称T是S的子序列。如S=1，2，3，4，5,6，7,8则T=2，4，6是S的子序列。另外：T1=1,3,6,8T2=2,5,7T3=4,5,8都是S的子序列，而T4=2，5，4，3T5=6，5，4不是S的子序列。第十四页，共二十五页，2022年，8月28日子序列判定一序列是不是另外一个序列的算法如下：//判定序列T是不是序列S的子序列isSubsequence(S,T){n=iSLength;//序列S的长度m=iTLength;//序列T的长度k=1;i=1;j=1;ifm>nreturnfalse;while((i<=m)and(j<=n)){if(Ti=Sj)//字符匹配

i=i+1;j=j+1}ifi=m+1returntrue//T是S的子序列returnfalse;}第十五页，共二十五页，2022年，8月28日字符串长度有限的序列又称字符串，字符串T的长度记作：|T|。两个字符串可以执行连接运算+，字符串S和字符T的连接运算如下：S=“abcdefg”T=“hijklmn”S+T=“abcdefghijklmn”。T+S=“hijklmnabcdefg”。第十六页，共二十五页，2022年，8月28日子串字符串中子串的概念，在计算机编程语言中的概念和数学中的子序列的概念有所不同，在计算机语言中，子串的定义为：定义2.4.2:对序列S=s1,s2,s3,…,sn,T=sm1sm2,…,smk，，如果T是S的子序列，且sm1sm2,…,smk，在S中是连续的，则称T是S的子串。如S=“abcdefg”,则子串为：“abc”，“cde”“efg”等，“bdf”虽然是S的子序列，但不是S的子串。第十七页，共二十五页，2022年，8月28日子串思考：子串判定的算法第十八页，共二十五页，2022年，8月28日矩阵定义2.3.1矩阵是一个数据的矩形阵列。如果A有m行和n列，则称A的大小是m乘以n的(记为mxn)。经常将矩阵简写为A＝(aij)mxn。在矩阵中，aij表示A中出现在第i行第j列的元素。第十九页，共二十五页，2022年，8月28日矩阵例：矩阵

有2行3列，所以它的大小是2X3。如果记A＝(aij)2x3，则有，a11=2，a21=-l。第二十页，共二十五页，2022年，8月28日方阵如果矩阵的行数和列数相等，则称该矩阵为方阵。第二十一页，共二十五页，2022年，8月28日矩阵运算加法定义2.3.3设A＝(aij)和B＝(bij)是两个mXn矩阵。A和B的和定义为mxn矩阵C=(cij),其中cij=aij+bij第二十二页，共二十五页，2022年，8月28日矩阵运算乘法定义2.3.4设A=(aij)是mXn矩阵，B＝(bjk)是nXl矩阵。A和B的乘积定义为mXl矩阵

C=AXB＝其中乘法要求矩阵A的列数等于矩阵B的行数，

乘法要求矩阵A的列数等于矩阵B的行数，第二十三页，共二十五页，2022年，8月28日矩阵运算乘法

c11=1X1+6X4=25c12=1X2+6X7=44c13=1X-1+6X0=-1c21=4X1+2X4=12………

第二十四