2 集合與序列.ppt

1、1,第2章 集合與序列,2,集合論的產(chǎn)生: 18761883年間， 康托（George Cantor 18451918年, 德國數(shù)學家）對任意元素的集合進行了系統(tǒng)的研究?？低斜还J為集合理論的創(chuàng)始人。,2.1 集合的定義和運算,3,2.1.1 集合的定義 一、集合（sets）的概念 集體 集合 組成集合的事物（也稱個體）叫做該集合的元素（elements）。 例如： 計算機學院2011級全體同學； 全體自然數(shù)； 方程 x2-10的解；,抽象成數(shù)學概念,4,二、集合的表示 集合-用大寫字母A, B, 等標識。 元素-用小寫字母a, b, 等標識。 記法：若個體a是集合A的元素, 則記為aA,讀作

2、“a屬于A”; 否則，記為a A, 讀作“a不屬于A”。,5,【定義】沒有任何元素的集合叫空集(empty set), 記為 。 【定義】當我們所討論的集合都是某一集合的子集時, 這某一集合就稱為全集(universal set), 并用E表示。,6,下面將本書中常用的集合符號列舉如下: N: 全體自然數(shù)的集合（包括0）, 稱作自然數(shù)集; Z:全體整數(shù)的集合, 稱作整數(shù)集; Q: 全體有理數(shù)的集合, 稱作有理數(shù)集; R: 全體實數(shù)的集合, 稱作實數(shù)集; C: 全體復(fù)數(shù)的集合, 稱作復(fù)數(shù)集; Zm（mN）: 介于0和m-1之間的全體非負整數(shù)的集合。,7,表示一個集合的方法通常有以下三種: 1.

3、列舉法。 如： A =0, 1, 2, 3。 自然數(shù)集N用列舉法表示是0, 1, 2, 3, 。,根據(jù)所列元素, 容易判斷N中的其余元素,8,2. 描述法：說明集合A中的元素x應(yīng)滿足的條件。 記為： Ax | x滿足的條件 如: 大于0小于1的實數(shù)集合： x | (0x1)且 xR ; 所有正奇數(shù)的集合： x | x2y+1且 yN 。,9,3. 遞歸法(遞推法) 數(shù)列常常用遞歸定義。 【例】斐波那契數(shù)列: f1=1, f2=1, fn=fn-1+fn-2，n=3,4,10,【定義】集合A中元素的個數(shù)稱為A的基（基數(shù), cardinality），也稱為長度，記作|A|。 當|A|是有限數(shù)時,

4、集合A稱作有限集, 否則稱為無限集。 顯然, |0。,11,羅素悖論：,在一個僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？,解：設(shè) Cx|x是不給自己刮臉的人 b是這位理發(fā)師 如果這位理發(fā)師不自己刮臉, 即bC，則 bC； 如果這位理發(fā)師自己刮臉, 即bC，則 bC。 bC或bC都不能成立,12,設(shè)A、B是兩個集合，E是全集，則 A和B的并集(union) AB、 A和B的交集(intersection) AB、 A的補集(complement) 分別定義如下： AB x | xA 或 xB AB x | xA 且

5、xB x | x A 且 xE,三、集合的運算,13,直觀地表示集合間關(guān)系的文氏圖：,注：文氏(John Venn), 1834-1923, 英國邏輯學家。,注意：文氏圖只能幫助我們形象地理解復(fù)雜的集合關(guān)系, 一般不作為一種證明方法。,14,設(shè)A、B是兩個集合，A與B的差集(difference) AB 定義為: ABx | xA且x B,15,設(shè)Aa, e, f , Ba, f, g, h 則： AB_ BA_,AB = BA。,?,16,由定義或文氏圖都容易得到下面的公式: AB A ,17,如何在計算機中表示集合? 如何在計算機中計算集合的運算?,2.1.2 集合運算的實現(xiàn),18,1、程

6、序中怎樣來表示集合？ 選用面向過程還是面向?qū)ο?面向過程：數(shù)組 面向?qū)ο螅簐ector 有序還是無序存儲 有序利于集合的運算 無序輸入數(shù)據(jù)簡單 元素與元素之間是否需要緊湊存儲 緊湊存儲節(jié)省空間，運算時間長（大量檢索） 不緊湊存儲則是以空間換取時間 2、如何利用程序?qū)崿F(xiàn)集合的運算？,19,4,2,算法2.2.1：求兩個集合交集的算法。,1,6,4,5,2,3,4,1,2,4,5,2,3,6,4,依次掃描A、B中的元素，若相同，則把其添加到C中,一、緊湊存儲方式下的集合運算的實現(xiàn),2,20,算法2.2.1：求兩個集合交集的算法。 FindIntersection(set A, set B) /求出

7、集合A和B的交集 iALength = length(A) /集合A的長度 iBLength = length(B) /集合B的長度 for(i=0;iiALength;i+) for(j=0;jiBLength;j+) if(Ai=Bj) Ck=Ai; /添加交集元素到交集C中 k+; break； Return C; /集合C就是A與B的交集 ,21,4,2,算法2.2.2：求兩個集合并集的算法。,1,2,4,5,2,3,4,1,5,2,3,6,4,把A中的元素加到C中，再掃描B，把其不再A中的元素加入C。,3,6,22,算法2.2.2：求兩個集合并集的算法： FindUnion (set

8、 A, set B) /求出集合A 和 B 的并集 iALength = length(A) /集合A的長度 iBLength = length(B) /集合B的長度 C=B；/用集合C存儲集合的并集，把B中的元素賦值到C中 iCLength = iBLength for(i=0;iiALength;i+) bFind=false; for(j=0;jiBLength;j+) /循環(huán)1 if(Ai=Bj) bFind=true; /Ai為公共元素； break； /跳出循環(huán)1 if not find /Ai不是公共元素； CiClength+1=Ai; /把Ai加入到集合C中； iClengt

9、h=iClength+1; Return C; /集合C就是A與B 的并集 ,23,算法2.2.2：求兩個集合減法的算法。,1,2,4,5,2,3,4,2,3,4,刪除在B中出現(xiàn)的A的元素。,4,1,5,6,2,6,24,算法2.2.3：集合減法運算算法。 FindDeference (set A, set B) /求出集合A-B的差集 iALength = length(A) /集合A的長度 iBLength = length(B) /集合B的長度 for(i=0;iiBLength;i+) for(j=0;jiALength;j+) if(Aj=Bi) A=A-Ai；/從集合A中去掉元素A

10、i Break； Return A; /集合A就是A與B的差集 ,25,算法時間復(fù)雜度分析： for(i=0;iiALength;i+) for(j=0;jiBLength;j+) 時間復(fù)雜度：O(n2),思考：若集合中元素按次序存儲在數(shù)組中，則算法可以怎樣改進？,26,假定全集E是有限的。首先為E的元素任意規(guī)定一個順序，例如d1，d2，dn，于是可以用長度為n的位串(布爾型數(shù)組)表示E的子集A： 如果di屬于A，則位串中第i位是1； 如果di不屬于A，則位串中第i位是0。,二、非緊湊存儲方式下的集合運算的實現(xiàn),27,例 令E=1，2，3，4，5，6，7，8，9，10，而且E的元素從小到大排序

11、，即di=i。問：表示E中所有奇數(shù)的子集、所有偶數(shù)的子集和不超過5的整數(shù)的子集的位串是什么? 解 表示E中所有奇數(shù)的子集即1，3，5，7，9的位串，其第1、3、5、7、9位為1，其他位為0，即 10101 01010 (位串分成長度為5的兩段以便閱讀),28,類似地，E中所有偶數(shù)的子集即2，4，6，8，10，由位串 01010 10101 表示 。 E中不超過5的所有整數(shù)的集合即1，2，3，4，5，由位串 11111 00000 表示。,29,用位串表示集合便于計算集合的補集、并集、交集和差集。 1）要從表示集合的位串計算它的補集的位串，只須簡單地把每個1改為0，每個0改為1。即按位取反。,3

12、0,例 我們已經(jīng)知道集合1，3，5，7，9的位串是 10101 01010 它的補集的位串是什么? 解 用0取代1，用1取代0，即可得到此集合的補集的位串 01010 10101 這對應(yīng)著集合2，4，6，8，10。,31,要得到兩個集合的并集和交集的位串，我們可以對表示這兩個集合的位串按位做布爾運算： 2）并集的位串是兩個集合位串的按位或：只要兩個位串的第i字位有一個是1，則并集的位串的第i位是1，當兩個字位都是0時為0。 3）交集的位串是兩個集合位串的按位與：當兩個位串的第i字位均為1時，交集的位串第i位為1，否則為0。,32,例 集合1，2，3，4，5和1，3，5，7，9的位串分別是111

13、11 00000和10101 01010。用位串找出它們的并集和交集。 解 這兩個集合的并集的位串是 11111 0000010101 01010 = 11111 01010 它表示的集合是1，2，3，4，5，7，9。 這兩個集合的交集的位串是 11111 0000010101 01010 = 10101 00000 它表示的集合是1，3，5。,33,例 集合A=1，2，3，4，5和B=1，3，5，7，9的位串分別是11111 00000和10101 01010。試用位串求差集AB 。 解 利用公式AB A ,34,算法時間復(fù)雜度分析： for(i=0;in;i+) /按位取反、按位做布爾運算

14、 時間復(fù)雜度：O(n),35,作業(yè)： 教材P16: 習題: 1, 2 編程練習：題庫12*號題（編號待定） 描述：現(xiàn)有一個放置了N（1=N=100)個編號分別為1N的球的箱子，小明第一次從箱子中取出M個球（1=M=N），并記錄各個球的編號，然后把球重新放入箱子內(nèi)，第二次在從箱子中取出S個球（1=S=N），并記錄各個球的編號。根據(jù)兩次取球記錄，求出那些球是兩次都被取到的。 輸入：輸入數(shù)據(jù)有三行，第一行輸入N的值；第二行輸入M的值和M個球的從小到大的編號，第三行為S的值和S個球的從小到大的編號。 輸出： 兩次都被取出的球的編號的從小到大序列。 （要求：第5周星期五前完成。 ）,36,2. 結(jié)合律

15、A(BC)(AB)C A(BC)(AB)C,1. 交換律 ABBA ABBA,3. 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC),2.1.3 集合運算的性質(zhì),37,4. 德摩根定律,5. AB A ,德摩根 (De Morgan, 1806-1871) 生于印度, 英國數(shù)學家。 主要貢獻: 數(shù)學歸納法,極限的定義, 符號邏輯,由4和5可得： 6. A(BC) ( AB )( AC ) A(BC) ( AB )( AC ),通過這些性質(zhì)，可以看出實現(xiàn)同一集合運算有不同算法。,38,例2.1.1 ：集合A表示班級男生集合，B是離散數(shù)學考試及格的同學，C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學。求

16、出至少有一門考試不及格的男同學。,分析：(A-B) 表示離散數(shù)學考試不及格的男同學; (A-C) 表示數(shù)據(jù)結(jié)構(gòu)考試不及格的男同學; 至少有一門考試不及格的男同學可以表示為： (A-C)(A-B) 根據(jù)摩根定律可知： (A-C)(A-B)=A-(BC),39,/找出至少有一門考試不及格的男同學 /A表示班級男生集合 /B是離散數(shù)學考試及格的同學 /C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學 FindMaleNotPass（set A，set B，set C） /求出B與C的交集 set D= FindIntersection(B,C)； / A-(BC) FindDeference (set A, set D)

17、 /求出集合A-D ,40,利用前面公式, 可以證明集合恒等式。 【例】 對任意集合A, B, C, 證明: (AB) C A (BC),41,2.2 序列與串,一、序列 序列：是考慮了元素順序的一個列表，與集合相比，序列中允許元素重復(fù)。 序列元素：用下標法標注元素在序列中的位置。 如序列S：2，4，6，8，, 2n 則 s1=2，s2=4，s3=6， 序列長度：一個序列中元素的個數(shù)。 子序列：從一個序列中去掉一些元素，余下的元素組成了一個新的序列，稱為原序列的子序列。,42,判定一個序列T是不是另一個序列S的子序列算法： 判定原則：T中的元素是否在S中按次序出現(xiàn)。 例：,43,isSubse

18、quence(S,T) /判定序列T是不是序列S的子序列 n=iSLength; /序列S的長度 m=iTLength; /序列T的長度 if mn 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; ,j=1,i=1,j=2,i=2,j=3,j=4,i=3,j=5,j=6,i=4m,j=7,44,二、字符串 長度有限的字符序列又稱字符串，字符串T的長度記作：|T|。 兩個字符串可以執(zhí)行連接運算“+”，

19、字符串S和字符T的連接運算如下： S=“abcdefg” T=“hijklmn” S+T = “abcdefghijklmn”。 T+S = “hijklmnabcdefg”。,45,字符串中子串的概念，在計算機編程語言中的概念和數(shù)學中的子序列的概念有所不同。 如果字符串的子序列是由原字符串中連續(xù)的元素構(gòu)成的，則該子序列稱為原字符串的子串。 如S=“abcdefg”,則子串為： “abc”， “cde”，“efg”等 “bdf”雖然是S的子序列，但不是S的子串。,思考： 子串判定的算法,46,2.3 矩陣,一、矩陣相加的算法 MatrixSum(Matrix A, Matrix B) for(i=0;im;i+) for(j=0;jn;j+) aij=aij+bij return A; ,47,二、矩陣相乘的算法,MatrixMulti(Matrix A, Matrix B) for(i=0;im;i+) for(j=0;jl;j+) cij=0; for(k=0;kn;k+) cij=cij+aikbkj return C; ,48,容斥原理,如果已知|A|和|B|, 能否求出|AB|和|AB|? |AB|、 |AB|和