離散數(shù)學(xué)集合與序列

離散數(shù)學(xué)集合與序列第一頁，共二十五頁，2022年，8月28日集合定義集合就是具有共同屬性的對象集合，其中每一個對象稱為集合的元素。集合中元素的個數(shù)稱之為集合長度。集合中元素是無序的、不可重復(fù)的。第二頁，共二十五頁，2022年，8月28日集合運算則A與B的并集為A∪B，A與B的交集A∩B，A的補(bǔ)-AA與B的差A(yù)-B：

A-B：A∩（-B）第三頁，共二十五頁，2022年，8月28日集合運算和實現(xiàn)算法：求兩個集合交集的算法：//求出集合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日集合運算和實現(xiàn)算法：求兩個集合交集的算法：算法：求兩個集合并集的算法：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++)//循環(huán)1if(A[i]==B[j]){bFind=true;//A[i]為公共元素；break；//跳出循環(huán)1}Ifnotfind////A[i]不是為公共元素；

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

iClength=iClength+1;}ReturnC;//集合B就是AB并集}第五頁，共二十五頁，2022年，8月28日集合運算和實現(xiàn)算法：求兩個集合交集的算法：算法：集合減法運算算法：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日集合運算和性質(zhì)算法：求兩個集合交集的算法：交換律：

A∩B=B∩A A∪B=B∪A結(jié)合律：（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)通過這些性質(zhì)，可以看出實現(xiàn)同一集合運算有不同算法。第七頁，共二十五頁，2022年，8月28日集合運算和性質(zhì)例2.3.1：集合A表示班級男生集合，B是離散數(shù)學(xué)考試及格的同學(xué)，C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學(xué)。求出至少有一門考試不及格的男同學(xué)。

第八頁，共二十五頁，2022年，8月28日集合運算和性質(zhì)(A-B)表示離散數(shù)學(xué)考試不及格的男同學(xué)。(A-C)表示數(shù)據(jù)結(jié)構(gòu)考試不及格的男同學(xué)至少有一門考試不及格的男同學(xué)可以表示為：(A-C)∪(A-B)。根據(jù)摩根定律可知：(A-C)∪(A-B)=A-(B∩C)。第九頁，共二十五頁，2022年，8月28日集合運算和性質(zhì)//找出至少有一門考試不及格的男同學(xué)//A表示班級男生集合//B是離散數(shù)學(xué)考試及格的同學(xué)//C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學(xué)。FinsMaleNotPa∈（setA，setB，setC）{//求出BC的交集

setD=FindIntersection(B,C)；

//A-(B∩C)FindDeference(setA,setD)//求出集合A-B的差集}第十頁，共二十五頁，2022年，8月28日集合運算和性質(zhì)例：學(xué)生20人，學(xué)號分別為1-20；集合A為選修離散數(shù)學(xué)的學(xué)生，集合B為成績不及格的學(xué)生，集合C為女生。找出。要求：寫出所有選修離散數(shù)學(xué)，成績不及格的男生的集合D的表示，并寫出求集合D中元素的算法。解:D=E-(A∩B)FindD{SetE=FindIntersection(setA,setB);D=FindDeference(setE,setC)}第十一頁，共二十五頁，2022年，8月28日集合運算和性質(zhì)例：集合A表示借閱圖書《離散數(shù)學(xué)》的學(xué)生，集合B表示借閱圖書《數(shù)據(jù)結(jié)構(gòu)》的學(xué)生，C表示目前沒有圖書館書籍的學(xué)生，寫出目前至少還有一本圖書沒有歸還的學(xué)生的集合D；解:算法A∪B：借閱過圖書的學(xué)生。至少還有一本圖書沒有歸還的學(xué)生的集合D：D=A∪B-CFindD{SetE=FindUnion(setA,setB);D=FindDeference(setE,setC)}第十二頁，共二十五頁，2022年，8月28日序列與串序列也是信息處理中常用到一種數(shù)學(xué)工具，一個序列是考慮了元素順序的一個列表，與集合相比，序列中允許元素重復(fù)。在數(shù)列中元素的順序是十分重要的，一般用下標(biāo)法標(biāo)注元素在序列中的位置，如序列S：2，4，6，8，…,2n則s1=2，s2=3，s3=6，…如序列T：a，a，b，c，…則t1=a，t2=a，t3=b，…一個序列中元素的個數(shù)為序列長度。第十三頁，共二十五頁，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|。兩個字符串可以執(zhí)行連接運算+，字符串S和字符T的連接運算如下：S=“abcdefg”T=“hijklmn”S+T=“abcdefghijklmn”。T+S=“hijklmnabcdefg”。第十六頁，共二十五頁，2022年，8月28日子串字符串中子串的概念，在計算機(jī)編程語言中的概念和數(shù)學(xué)中的子序列的概念有所不同，在計算機(jī)語言中，子串的定義為：定義2.4.2:對序列S=s1,s2,s3,…,sn,T=sm1sm2,…,smk，，如果T是S的子序列，且sm1sm2,…,smk，在S中是連續(xù)的，則稱T是S的子串。如S=“abcdefg”,則子串為：“abc”，“cde”“efg”等，“bdf”雖然是S的子序列，但不是S的子串。第十七頁，共二十五頁，2022年，8月28日子串思考：子串判定的算法第十八頁，共二十五頁，2022年，8月28日矩陣定義2.3.1矩陣是一個數(shù)據(jù)的矩形陣列。如果A有m行和n列，則稱A的大小是m乘以n的(記為mxn)。經(jīng)常將矩陣簡寫為A＝(aij)mxn。在矩陣中，aij表示A中出現(xiàn)在第i行第j列的元素。第十九頁，共二十五頁，2022年，8月28日矩陣?yán)壕仃?

有2行3列，所以它的大小是2X3。如果記A＝(aij)2x3，則有，a11=2，a21=-l。第二十頁，共二十五頁，2022年，8月28日方陣如果矩陣的行數(shù)和列數(shù)相等，則稱該矩陣為方陣。第二十一頁，共二十五頁，2022年，8月28日矩陣運算加法定義2.3.3設(shè)A＝(aij)和B＝(bij)是兩個mXn矩陣。A和B的和定義為mxn矩陣C=(cij),其中cij=aij+bij第二十二頁，共二十五頁，2022年，8月28日矩陣運算乘法定義2.3.4設(shè)A=(aij)是mXn矩陣，B＝(bjk)是nXl矩陣。A和B的乘積定義為mXl矩陣

C=AXB＝其中乘法要求矩陣A的列數(shù)等于矩陣B的行數(shù)，

乘法要求矩陣A的列數(shù)等于矩陣B的行數(shù)，第二十三頁，共二十五頁，2022年，8月28日矩陣運算乘法

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

第二十四