分類加法計數(shù)原理與分步乘法計數(shù)原理(優(yōu)質課).ppt

兩類 能 26種10種 26 10 36種 或一個阿拉伯數(shù)字給教室里的座位編號 總共能夠編出多少種不同的號碼 請思考 問題1 用一個大寫的英文字母 用一個大寫的英文字母或一個阿拉伯數(shù)字給教室里的座位編號 假如你從平川到蘭州 請問你共有多少種不同的走法 客車每天有3個班次 火車每天有2個班次 可以坐直達客車或直達火車 引例 平川 蘭州 分析 完成從平川到蘭州這件事有2類方案 所以 從平川到蘭州共有3 2 5種方法 問題1 你能否發(fā)現(xiàn)這兩個問題有什么共同特征 1 都是要完成一件事 2 用任何一類方法都能直接完成這件事 3 都是采用加法運算 完成一件事有兩類不同的方案 分類加法計數(shù)原理 在第1類方案中有m種不同的方法 在第2類方案中有n種不同的方法 那么完成這件事共有N m n種不同的方法 例1 在填寫高考志愿表時 一名高中畢業(yè)生了解到A B兩所大學各有一些自己感興趣的強項專業(yè) 具體情況如下 如果這名同學只能選一個專業(yè) 那么他共有多少種選擇呢 變式 在填寫高考志愿表時 一名高中畢業(yè)生了解到 A B C三所大學各有一些自己感興趣的強項專業(yè) 具體情況如下 如果這名同學只能選一個專業(yè) 那么他共有多少種選擇呢 N 5 4 5 14 種 如果完成一件事情有3類不同方案 在第1類方案中有m1種不同的方法 在第2類方案中有m2種不同的方法 在第3類方案中有m3種不同的方法 那么完成這件事情有種不同的方法 N m1 m2 m3 分類加法計數(shù)原理的推廣 完成一件事有n類不同的方案 在第1類方案中有m1種不同的方法 在第2類方案中有m2種不同的方法 那么完成這件事共有種不同的方法 在第n類方案中有mn種不同的方法 分析 完成給教室里的座位編號編號這件事分兩步完成 第1步 先確定一個英文字母第2步 后確定一個阿拉伯數(shù)字 字母數(shù)字得到的號碼 123456789 A1A2A3A4A5A6A7A8A9 樹形圖 A 分析 完成給教室里的座位編號這件事需要兩個步驟 第1步 確定一個英文字母 有6種不同方法 第2步 確定一個阿拉伯數(shù)字 有9種不同方法 所以 編號共有6 9 54種方法 例2 設某班有男生30名 女生24名 現(xiàn)要從中選出男 女生各一名代表班級參加比賽 共有多少種不同的選法 例3 長征的部分電話號碼是0943665 后面每個數(shù)字來自0 9這10個數(shù) 問可以產生多少個不同的電話號碼 變式 若要求最后4個數(shù)字不重復 則又有多少種不同的電話號碼 0943665 分析 分析 分類加法計數(shù)原理 完成一件事需要兩個步驟 做第1步有m種不同的方法 做第2步有n種不同的方法 那么完成這件事共有 N m n 分步乘法計數(shù)原理 種不同的方法 分步乘法計數(shù)原理的推廣 那么完成這件事共有種不同的方法 完成一件事需要n個步驟 做第1步有m1種不同的方法 做第2步有m2種不同的方法 做第n步有mn種不同的方法 兩個計數(shù)原理 用來計算 完成一件事 的方法種數(shù) 每類方案中的每一種方法都能 完成這件事 每步 才算完成這件事情 每步中的每一種方法不能獨立完成這件事 類類相加 步步相乘 類類獨立 步步相依 獨立 依次完成 不重不漏 步驟完整 分類完成 分步完成 解 從書架上任取1本書 例3書架上的第1層放著4本不同的計算機書 第2層放著3本不同的文藝書 第3層放著2本不同的體育書 第1類方法是從第1層取1本計算機書 有4種方法 第2類方法是從第2層取1本文藝書 有3種方法 第3類方法是從第3層取1本體育書 有2種方法 根據(jù)分類加法計數(shù)原理 不同取法的種數(shù)是 N 4 3 2 9 1 從書架上任取1本書 有幾種不同的取法 有三類方法 2 從書架上的第1 2 3層各取1本書 有幾種不同的取法 例3書架上的第1層放著4本不同的計算機書 第2層放著3本不同的文藝書 第3層放著2本不同的體育書 1 從書架上任取1本書 有幾種不同的取法 解 從書架的第1 2 3層各取1本書 第1步 從第1層取1本計算機書 有4種方法 第2步 從第2層取1本文藝書 有3種方法 第3步 從第3層取1本體育書 有2種方法 根據(jù)分步計數(shù)原理 不同取法的種數(shù)是 N 4 3 2 24 可以分成三個步驟完成 解答計數(shù)問題的一般思維過程 完成一件什么事 例4要從甲 乙 丙 3幅不同的畫中選出2幅 分別掛在左 右兩邊墻上的指定位置 問共有多少種不同的掛法 甲 乙 丙 解 從3幅畫中選出2幅分別掛在左 右兩邊墻上 可以分兩個步驟完成 第一步 從3幅畫中選1幅掛在左邊墻上 有3種選法 第二步 從剩下的2幅畫中選1幅掛在右邊墻上 有2種選法 根據(jù)分步計數(shù)原理 不同掛法的種數(shù)是 N 3 2 6 思考 還有其他解答本題的方法嗎 例4要從甲 乙 丙 3幅不同的畫中選出2幅 分別掛在左 右兩邊墻上的指定位置 問共有多少種不同的掛法 甲 乙 丙 解 從3幅畫中選出2幅分別掛在左 右兩邊墻上 可以分兩個步驟完成 第一步 從3幅畫中選出2幅 有3種選法 甲 乙 甲 丙 乙 丙 第二步 將選出的2幅畫掛好 有2中掛法 根據(jù)分步計數(shù)原理 不同掛法的種數(shù)是 N 3 2 6 變式要從甲 乙 丙 丁 戊5幅不同的畫中選出2幅 分別掛在左 右兩邊墻上的指定位置 問共有多少種不同的掛法 解 從5幅畫中選出2幅分別掛在左 右兩邊墻上 可以分兩個步驟完成 第一步 從5幅畫中選1幅掛在左邊墻上 有5種選法 第二步 從剩下的4幅畫中選1幅掛在右邊墻上 有4種選法 根據(jù)分步計數(shù)原理 不同掛法的種數(shù)是 N 5 4 20 例5 五名學生報名參加四項體育比賽 每人限報一項 報名方法的種數(shù)為多少 又他們爭奪這四項比賽的冠軍 獲得冠軍的可能性有多少種 解 1 5名學生中任一名均可報其中的任一項 因此每個學生都有4種報名方法 5名學生都報了項目才能算完成這一事件故報名方法種數(shù)為4 4 4 4 4 種 2 每個項目只有一個冠軍 每一名學生都可能獲得其中的一項獲軍 因此每個項目獲冠軍的可能性有5種故有n 5 種 例6 給程序模塊命名 需要用3個字符 其中首個字符要求用字母A G或U Z 后兩個要求用數(shù)字1 9 問最多可以給多少個程序命名 分析 要給一個程序模塊命名 可以分三個步驟 第一步 選首字符 第二步 先中間字符 第三步 選末位字符 解 首字符共有7 6 13種不同的選法 答 最多可以給1053個程序命名 中間字符和末位字符各有9種不同的選法 根據(jù)分步計數(shù)原理 最多可以有13 9 9 1053種不同的選法 例7 核糖核酸 RNA 分子是在生物細胞中發(fā)現(xiàn)的化學成分 一個RNA分子是一個有著數(shù)百個甚至數(shù)千個位置的長鏈 長鏈中每一個位置上都由一種稱為堿基的化學成分所占據(jù) 總共有 個不同的堿基 分別用A C G U表示 在一個RNA分子中 各種堿基能夠以任意次序出現(xiàn) 所以在任意一個位置上的堿基與其他位置上的堿基無關 假設有一類RNA分子由100個堿基組成 那么能有多少種不同的RNA分子 分析 用100個位置表示由100個堿基組成的長鏈 每個位置都可以從A C G U中任選一個來占據(jù) 解 100個堿基組成的長鏈共有100個位置 在每個位置中 從A C G U中任選一個來填入 每個位置有4種填充方法 根據(jù)分步計數(shù)原理 共有 種不同的RNA分子 例8 電子元件很容易實現(xiàn)電路的通與斷 電位的高與底等兩種狀態(tài) 而這也是最容易控制的兩種狀態(tài) 因此計算機內部就采用了每一位只有0或1兩種數(shù)字的計數(shù)法 即二進制 為了使計算機能夠識別字符 需要對字符進行編碼 每個字符可以用一個或多個字節(jié)來表示 其中字節(jié)是計算機中數(shù)據(jù)存儲的最小計量單位 每個字節(jié)由 個二進制位構成 問 1 一個字節(jié) 8位 最多可以表示多少個不同的字符 2 計算機漢字國標碼 GB碼 包含了6763個漢字 一個漢字為一個字符 要對這些漢字進行編碼 每個漢字至少要用多少個字節(jié)表示 如00000000 10000000 11111111 例9 計算機編程人員在編寫好程序以后要對程序進行測試 程序員需要知道到底有多少條執(zhí)行路 即程序從開始到結束的線 以便知道需要提供多少個測試數(shù)據(jù) 一般的 一個程序模塊又許多子模塊組成 它的一個具有許多執(zhí)行路徑的程序模塊 問 這個程序模塊有多少條執(zhí)行路徑 另外為了減少測試時間 程序員需要設法減少測試次數(shù) 你能幫助程序員設計一個測試方式 以減少測試次數(shù)嗎 分析 整個模塊的任意一條路徑都分兩步完成 第1步是從開始執(zhí)行到A點 第2步是從A點執(zhí)行到結束 而第步可由子模塊1或子模塊2或子模塊3來完成 第二步可由子模塊4或子模塊5來完成 因此 分析一條指令在整個模塊的執(zhí)行路徑需要用到兩個計數(shù)原理 再測試各個模塊之間的信息交流是否正常 需要測試的次數(shù)為 3 2 6 如果每個子模塊都正常工作 并且各個子模塊之間的信息交流也正常 那么整個程序模塊就正常 這樣 測試整個模塊的次數(shù)就變?yōu)?72 6 178 次 2 在實際測試中 程序員總是把每一個子模塊看成一個黑箱 即通過只考察是否執(zhí)行了正確的子模塊的方式來測試整個模塊 這樣 他可以先分別單獨測試5個模塊 以考察每個子模塊的工作是否正常 總共需要的測試次數(shù)為 18 45 28 38 43 172 例10 隨著人們生活水平的提高 某城市家庭汽車擁有量迅速增長 汽車牌照號碼需要擴容 交通管理部門出臺了一種汽車牌照組成辦法 每一個汽車牌照都必須有 個不重復的英文字母和 個不重復的阿拉伯數(shù)字 并且 個字母必須合成一組出現(xiàn) 個數(shù)字也必須合成一組出現(xiàn) 那么這種辦法共能給多少輛汽車上牌照 如圖 從甲地到乙地有2條路 從乙地到丁地有3條路 從甲地到丙地有4條路可以走 從丙地到丁地有2條路 從甲地到丁地共有多少種不同地走法 課堂練習