离散数学集合与序列.ppt

第1页，共25页，星期日，2025年，2月5日集合定义集合就是具有共同属性的对象集合，其中每一个对象称为集合的元素。集合中元素的个数称之为集合长度。集合中元素是无序的、不可重复的。第2页，共25页，星期日，2025年，2月5日集合运算则A与B的并集为A∪B，A与B的交集A∩B，A的补-AA与B的差A-B：A-B：A∩（-B）第3页，共25页，星期日，2025年，2月5日集合运算和实现算法2.2.1：求两个集合交集的算法：//求出集合A和B的交集FindIntersection(setA,setB){iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;iiALength;i++){for(j=0;jiBLength;j++)if(A[i]==B[j]){//添加交集元素到交集C中C[k]=A[i];k++;break；}}ReturnC;//集合C就是AB交集}第4页，共25页，星期日，2025年，2月5日集合运算和实现算法2.2.1：求两个集合交集的算法：算法2.2.2：求两个集合并集的算法：FindUnion(setA,setB)//求出集合A和B的并集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度C=B；//用集合C存储集合的并集，//把B中的元素赋值到C中。for(i=0;iiALength;i++){bFind=false;for(j=0;jiBLength;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并集}第5页，共25页，星期日，2025年，2月5日集合运算和实现算法2.2.1：求两个集合交集的算法：算法2.2.3：集合减法运算算法：FindDeference(setA,setB)//求出集合A-B的差集{iALength=length(A)//集合A的长度iBLength=length(B)//集合B的长度for(i=0;iiBLength;i++){for(j=0;jiALength;j++)if(A[j]==B[i]){从集合A中去掉元素A[i]；//具体算法不列出Break；}}ReturnA;//集合A就是AB的差集}第6页，共25页，星期日，2025年，2月5日集合运算和性质算法2.2.1：求两个集合交集的算法：交换律： 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)通过这些性质，可以看出实现同一集合运算有不同算法。第7页，共25页，星期日，2025年，2月5日集合运算和性质例2.3.1：集合A表示班级男生集合，B是离散数学考试及格的同学，C是数据结构考试及格的同学。求出至少有一门考试不及格的男同学。第8页，共25页，星期日，2025年，2月5日集合运算和性质(A-B)表示离散数学考试不及格的男同学。(A-C)表示数据结构考试不及格的男同学至少有一门考试不及格的男同学可以表示为：(A-C)∪(A-B)。根据摩根定律可知：(A-C)∪(A-B)=A-(B∩C)。第9页，共25页，星期日，2025年，2月5日集合运算和性质//找出至少有一门考试不及格的男同学//A表示班级男生集合//B是离散