《离散数学集合与序列.ppt》由会员分享，可在线阅读，更多相关《离散数学集合与序列.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学集合与序离散数学集合与序列列现在学习的是第1页，共25页集合定义集合定义 l集合就是具有共同属性的对象集合，其中每一个对象称为集合的元素。集合中元素集合中元素的个数称之为集合长度的个数称之为集合长度。集合中元素是无无序的、不可重复的序的、不可重复的。现在学习的是第2页，共25页集合运算集合运算l则则A与与B的并集为的并集为A B，lA与与B的交集的交集AB，lA的补的补-AlA与与B的差的差A-B：A-B：A（-B）现在学习的是第3页，共25页集合运算和实现集合运算和实现l算法算法2.2.1：求两个集合交集的算法：求两个集合交集的算法：l/求出集合求出集合A 和和 B 的交集的交集lF
2、indIntersection(set A,set B)lliALength=length(A)/集合集合A的长度的长度liBLength=length(B)/集合集合B的长度的长度lfor(i=0;iiALength;i+)ll for(j=0;jiBLength;j+)l if(Ai=Bj)ll/添加交集元素到交集添加交集元素到交集C中中lCk=Ai;lk+;lbreak；l llReturn C;/集合集合C就是就是A B 交集交集l现在学习的是第4页，共25页集合运算和实现集合运算和实现l算法算法2.2.1：求两个集合交集的算法：求两个集合交集的算法：l算法算法2.2.2：求两个集合并
3、集的算法：求两个集合并集的算法：lFindUnion(set A,set B)/求出集合求出集合A 和和 B 的并集的并集lliALength=length(A)/集合集合A的长度的长度liBLength=length(B)/集合集合B的长度的长度lC=B；/用集合用集合C存储集合的并集，存储集合的并集，l/把把B中的元素赋值到中的元素赋值到C中。中。lfor(i=0;iiALength;i+)llbFind=false;l for(j=0;jiBLength;j+)/循环循环1l if(Ai=Bj)ll bFind=true;/Ai为公共元素；为公共元素；lbreak；/跳出循环跳出循环1l
4、 l If not find /Ai不是为公共元素；不是为公共元素；l CiBlength+1=Ai;/把把Ai加入到集合加入到集合B中；中；l iClength=iClength+1;llReturn C;/集合集合B就是就是A B 并集并集l现在学习的是第5页，共25页集合运算和实现集合运算和实现l算法算法2.2.1：求两个集合交集的算法：求两个集合交集的算法：l算法算法2.2.3：集合减法运算算法：集合减法运算算法：lFindDeference(set A,set B)/求出集合求出集合A-B的差集的差集lliALength=length(A)/集合集合A的长度的长度liBLength=
5、length(B)/集合集合B的长度的长度lfor(i=0;iiBLength;i+)ll for(j=0;jn l return false;lwhile(i=m)and(j=n)ll if(Ti=Sj)/字符匹配l i=i+1;l j=j+1llif i=m+1 l return true /T是S的子序列lreturn false;l现在学习的是第15页，共25页字符串字符串l长度有限的序列又称字符串字符串，字符串T的长度记作：|T|。两个字符串可以执行连接运算+，字符串S和字符T的连接运算如下：lS=“abcdefg”lT=“hijklmn”lS+T=“abcdefghijklmn”。
6、lT+S=“hijklmnabcdefg”。现在学习的是第16页，共25页子串子串l字符串中子串的概念，在计算机编程语言中的概念和数学中的子序列的概念有所不同，在计算机语言中，子串的定义为：l定义定义2.4.2:对序列对序列S=s1,s2,s3,sn,T=sm1sm2,smk，如果，如果T是是S的子序列，且的子序列，且sm1sm2,smk，在，在S中是中是连续的，则称连续的，则称T是是S的子串。的子串。l如S=“abcdefg”,则子串为：“abc”，“cde”“efg”等，“bdf”虽然是S的子序列，但不是S的子串。现在学习的是第17页，共25页子串子串l思考：子串判定的算法 现在学习的是第
7、18页，共25页矩阵矩阵l定义定义2.3.1 矩阵矩阵l是一个数据的矩形阵列。是一个数据的矩形阵列。l 如果A有m行和n列，则称A的大小是m乘以n的(记为mxn)。经常将矩阵简写为A(aij)mxn。在矩阵中，aij表示A中出现在第i行第j列的元素。现在学习的是第19页，共25页矩阵矩阵l例例2.3.1：矩阵：矩阵l有有2行行3列，所以它的大小是列，所以它的大小是2X3。如果记。如果记A(aij)2x3，则有，则有，la11=2，a21=-l。现在学习的是第20页，共25页方阵方阵l如果矩阵的行数和列数相等，则称该矩阵为方阵。如果矩阵的行数和列数相等，则称该矩阵为方阵。现在学习的是第21页，共
8、25页矩阵运算矩阵运算 加法加法l定义定义2.3.3 设设A(aij)和和B(bij)是是两个两个mXn矩阵。矩阵。A和和B的和定义为的和定义为mxn矩阵矩阵C=(cij),其中其中lcij=aij+bij现在学习的是第22页，共25页矩阵运算矩阵运算 乘法乘法l定义定义2.3.4 设设A=(aij)是是mXn矩阵，矩阵，B(bjk)是是nXl矩阵。矩阵。A和和B的乘积定义为的乘积定义为m X l矩阵矩阵l l C=A X Bl其中其中l乘法要求矩阵乘法要求矩阵A的列数等于矩阵的列数等于矩阵B的行数，的行数，l 乘法要求矩阵A的列数等于矩阵B的行数，现在学习的是第23页，共25页矩阵运算矩阵运
9、算 乘法乘法l l c11=1X1+6X4=25l c12=1X2+6X7=44l c13=1X-1+6X0=-1l c21=4X1+2X4=12l 现在学习的是第24页，共25页矩阵运算矩阵运算 乘法乘法l矩阵相乘需要大量的数据运算，可以借助计算机完成，矩阵相乘算法为：矩阵相乘需要大量的数据运算，可以借助计算机完成，矩阵相乘算法为：lMatrixMulti(Matrix A,Matrix B)ll for(i=0;im;i+)l for(j=0;jl:j+)l l cij=0l for(k=0;kn:k+)l cij=cij+aikXbkjl l return C;ll 现在学习的是第25页，共25页