【正文】 8381 2022/7/13 例 4 （續(xù)） 1. selection_sorts(s,n){ 2. //基本情況 3. if (n= =1) 5. //找到最大的元素 6. max_index = 1 //初始時認為 s1是最大的元素 7. for i=2 to n 8. if (sismax_index)//比較得到較大的元素 ， 并更新最大元素 9. max_index = i 10. //將最大的元素移至序列尾 11. swap((sn, smax_index) 12. selection_sort(s, n1) 13. } 8382 2022/7/13 例 4 解 設(shè)計算 n個數(shù)排序的比較執(zhí)行次數(shù)為 bn， 則該算法中的比較語句的執(zhí)行次數(shù)的 遞歸關(guān)系 為： bn= bn1 + n – 1， 其 初始條件 為： b1 = 0。 8379 2022/7/13 例 3 Fibonacci數(shù)列 假定一對新出生的兔子一個月又成熟 ， 并且再過一個月開始生出一對小兔子 。 試問該電子鎖 至少應(yīng)具備多少個特征 ？每位科學工作者的 “ 鑰匙 ” 至少應(yīng)有多少種特征 ？ 解 為了使任意 3個人在場時至少缺少一個特征而打不開門 ， 該電子鎖應(yīng)具備 C(7,3)=35種特征；每個科學工作者的 “ 鑰匙 ” 至少要有 C(6,3)= 20種特征 。 8338 2022/7/13 集合的排列 定義 從 n 元集 S 中有序、不重復選取的 r 個元素稱為 S 的一個 r 排列 ， S 的所有 r 排列的數(shù)目記作 P(n,r) 定理 證明 使用乘法法則 推論 1 S 的環(huán)排列數(shù) = ?????????rnrnrnnrnP0)!(!),(rrnP ),(8339 2022/7/13 集合的組合 ????????rnrnrrnPrnC0!),(),(定義 從 n 元集 S 中無序、不重復選取的 r 個元素稱為 S 的一個 r 組合， S 的所有 r 組合的數(shù)目記作 C(n,r) 定理 )11 ?? ,rC(nrn推論 2 設(shè) n, r為正整數(shù)，則 (1) C(n, r)= (2) C(n, r) = C(n, n?r) (3) C(n, r)=C(n?1,r?1)+C(n?1,r) )11 ?? ,rC ( nrn8340 2022/7/13 證明方法 方法 1：公式代入并化簡 方法 2：組合證明 實例：證明 C(n, r) = C(n, n?r) 證 設(shè) S ={1, 2, … , n}是 n元集合 ， 對于 S 的任意 r組合 A={a1, a2, … , ar}， 都存在一個 S 的 n?r 組合 S?A與之對應(yīng) . 顯然不同的 r 組合對應(yīng)了不同的 n?r 組合 ， 反之也對 ， 因 此 S 的 r 組合數(shù)恰好與 S 的 (n?r)組合數(shù)相等 . C(n, r)=C(n?1,r?1)+C(n?1,r) 稱為 Pascal公式 ， 也對應(yīng)了楊輝三角形 ， 兩種證明方法都適用 . 8341 2022/7/13 楊輝三角 8342 2022/7/13 基本計數(shù)公式的應(yīng)用 解 分類選取 A = {1, 4, …,298} B = {2, 5, …,299} C = {3, 6, …, 300} 分別取自 A, B, C: 各 C(100,3) A, B, C 各取 1 個（分步處理）： C(100,1)3 N= C(100,3) + 1003 = 1485100 例 1 從 1— 300中任取 3個數(shù)使得其和能被 3整除有多少種方法？ 8343 2022/7/13 基本計數(shù)公式的應(yīng)用 (續(xù) ) 解 : 1000!=1000 ?999? 998 ?… ? 2?1 將上面的每個因子分解，若分解式中共有 i 個 5, j 個 2， 那么 min(i, j)就是 0的個數(shù) . 1, …,1000 中有 500個是 2 的倍數(shù)， j 500。 試求滿足下列條件的組合數(shù) 。 當 n≥r = 0時 ， 規(guī)定 C(n, r) = 1。 根據(jù)乘法法則 ， 10個男孩和 5個女孩站成一排 ， 沒有兩個女孩相鄰的排列數(shù)為： 10! P(11, 5) =（ 10! 11!)/6! 。 A E F B D C n個人圍坐圓桌上，有 (n1)！種不同的坐法，我們稱這種排列為 環(huán)排列 ，從 n個人中選出 r個人為圓桌而坐稱為 環(huán)形 r 排列 。 8325 2022/7/13 定理 對滿足 r≤n 的正整數(shù) n和 r有 P ( n ,r ) = n ( n 1 ) ( n ( r 1 ) )第 r位 第 r1位 第 3位 第 2位 第 1位 n n1 n2 … … n(r2) n(r1) 8326 2022/7/13 注意： n個不同元素的排列共有 n！ 種 ， 其中 n ! = n ( n 1 ) 2 18327 2022/7/13 例 2 A,B,C,D,E,F組成的排列中 ， （ 1） 有多少含有 DEF的子串 ？ （ 2） 三個字母 D、 E和 F相連的有多少種 ？ 解 (1)將 DEF看成一個對象 ， 根據(jù)定理 ， 滿足條件的排列為 A,B,C,DEF的全排列 ， 共有 4！ =24種； （ 2） 根據(jù)題意 ， 滿足該條件的排列分為兩步：第一步確定 D, E和 F三個字母的全排列 ， 有 3！ 種排列 ， 第二步將 已排序的 D, E和 F看成一個整體 ， 與 A, B和 C共 4個元素構(gòu)造出 A, B, C, D, E, F的全排列 ， 有 4！ 種排列 。 顯然 ， 當 rn時 ， P(n, r) = 0。 為了使選票上人名的次序不對投票者產(chǎn)生影響 ， 有必要將每一種可能的人名次序打印在選票上 。 根據(jù) 乘法法則 ， 共有 3 5 4 = 60種選法； [法二 ] 根據(jù) (1)的結(jié)論 ， 如果 Egbert為主席 ， 有 20種方法確定余下的職位； 若 Egbert為秘書 ， 有 20種方法確定余下的職位； 若 Egbert為出納員 ， 也有 20種方法確定余下的職位 。 8318 2022/7/13 例 3 由 Alice 、 Ben 、 Connie 、 Dolph 、 Egbert 和Francisco六個人組成的委員會 ， 要 選出一個主席 、一個秘書和一個出納員 。 解 每個點有 256( = 28) 種不同的取值 。問經(jīng)過四次轉(zhuǎn)發(fā) ， 共有多少個接收者 ？ 解 根據(jù) Melissa病毒的擴散原理，經(jīng)過四次轉(zhuǎn)發(fā)， 共有 50 50 50 50+50 50 50+50 50+ 50 +1 = 6377551個接收者。 例 2 100個選手淘汰賽，為產(chǎn)生冠軍至少需要多少輪比賽？ 方法 1： 50+25+12+6+3+2+1=99 方法 2：比賽次數(shù)與淘汰人數(shù)之間存在一一對應(yīng)，總計淘汰 99人，因此至少需要 99場比賽 . 8313 2022/7/13 開胃食品 主食 飲料 種類 價格(元 ) 種類 價格 種類 價格 玉米片(Co) 漢堡 (H) 茶水 (T) 色拉 (Sa) 三明治(S) 牛奶(M) 魚排 (F) 可樂 (C) 啤酒 (B) 表 1 8314 2022/7/13 乘法法則 如果一些工作需要 t步完成 ， 第一步有 n1種不同的選擇 ， 第二步有 n2種不同的選擇 ， … ，第 t步有 nt種不同的選擇 ， 那么完成這項工作所有可能的選擇種數(shù)為： 1 2 tn n n8315 2022/7/13 例 1 Melissa病毒 1990年 ， 一種名叫 Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計算機系統(tǒng) ， 通過以含惡意宏的字處理文檔為附件的電子郵件傳播 。 另外 ， 法國數(shù)學家 Blaise Pascal還發(fā)明了一種機械計算器 ， 這種計算器非常類似于 20世紀40年代在數(shù)字電子計算機發(fā)明之前使用的一種機械計算器 。最主要的方法是 計數(shù)時的合理分類 和 組合模型的轉(zhuǎn)換 。 836 2022/7/13 前言 組合數(shù)學的蓬勃發(fā)展則是在計算機問世和普遍應(yīng)用之后 。 楊輝著 《 詳解九章算法 》 （ 1261年 ）中曾引賈憲的 “ 開方作法本源 ” 圖 （ 即指數(shù)為正整數(shù)的二項式展開系數(shù)表 ， 現(xiàn)