1.1.2分類加法計數原理與分步乘法計數原理.ppt

1 分類加法計數原理 完成一件事 有n類辦法 在第1類辦法中有m1種不同的方法 在第2類辦法中有m2種不同的方法 在第n類辦法中有mn種不同的方法 那么完成這件事共有種不同的方法 2 分步乘法計數原理 完成一件事 需要分成n個步驟 做第1步有m1種不同的方法 做第2步有m2種不同的方法 做第n步有mn種不同的方法 那么完成這件事共有種不同的方法 回答的都是有關做一件事的不同方法種數的問題 完成一件事 共有n類辦法 關鍵詞 分類 區(qū)別1 完成一件事 共分n個步驟 關鍵詞 分步 區(qū)別2 區(qū)別3 每類辦法都能獨立地完成這件事情 它是獨立的 一次的 且每次得到的是最后結果 只須一種方法就可完成這件事 每一步得到的只是中間結果 任何一步都不能獨立完成這件事 缺少任何一步也不能完成這件事 只有各個步驟都完成了 才能完成這件事 各類辦法是互相獨立的 各步之間是互相關聯的 即 類類獨立 步步關聯 例2 給程序模塊命名 需要用3個字符 其中首個字符要求用字母A G或U Z 后兩個要求用數字1 9 問最多可以給多少個程序命名 分析 要給一個程序模塊命名 可以分三個步驟 第一步 選首字符 第二步 先中間字符 第三步 選末位字符 解 首字符共有7 6 13種不同的選法 答 最多可以給1053個程序命名 中間字符和末位字符各有9種不同的選法 根據分步計數原理 最多可以有13 9 9 1053種不同的選法 例3 核糖核酸 RNA 分子是在生物細胞中發(fā)現的化學成分 一個RNA分子是一個有著數百個甚至數千個位置的長鏈 長鏈中每一個位置上都由一種稱為堿基的化學成分所占據 總共有 個不同的堿基 分別用A C G U表示 在一個RNA分子中 各種堿基能夠以任意次序出現 所以在任意一個位置上的堿基與其他位置上的堿基無關 假設有一類RNA分子由100個堿基組成 那么能有多少種不同的RNA分子 分析 用100個位置表示由100個堿基組成的長鏈 每個位置都可以從A C G U中任選一個來占據 解 100個堿基組成的長鏈共有100個位置 在每個位置中 從A C G U中任選一個來填入 每個位置有4種填充方法 根據分步計數原理 共有 種不同的RNA分子 例4 電子元件很容易實現電路的通與斷 電位的高與底等兩種狀態(tài) 而這也是最容易控制的兩種狀態(tài) 因此計算機內部就采用了每一位只有0或1兩種數字的計數法 即二進制 為了使計算機能夠識別字符 需要對字符進行編碼 每個字符可以用一個或多個字節(jié)來表示 其中字節(jié)是計算機中數據存儲的最小計量單位 每個字節(jié)由 個二進制位構成 問 1 一個字節(jié) 8位 最多可以表示多少個不同的字符 2 計算機漢字國標碼 GB碼 包含了6763個漢字 一個漢字為一個字符 要對這些漢字進行編碼 每個漢字至少要用多少個字節(jié)表示 如00000000 10000000 11111111 例5 計算機編程人員在編寫好程序以后要對程序進行測試 程序員需要知道到底有多少條執(zhí)行路 即程序從開始到結束的線 以便知道需要提供多少個測試數據 一般的 一個程序模塊又許多子模塊組成 它的一個具有許多執(zhí)行路徑的程序模塊 問 這個程序模塊有多少條執(zhí)行路徑 另外為了減少測試時間 程序員需要設法減少測試次數 你能幫助程序員設計一個測試方式 以減少測試次數嗎 分析 整個模塊的任意一條路徑都分兩步完成 第1步是從開始執(zhí)行到A點 第2步是從A點執(zhí)行到結束 而第1步可由子模塊1或子模塊2或子模塊3來完成 第二步可由子模塊4或子模塊5來完成 因此 分析一條指令在整個模塊的執(zhí)行路徑需要用到兩個計數原理 再測試各個模塊之間的信息交流是否正常 需要測試的次數為 3 2 6 如果每個子模塊都正常工作 并且各個子模塊之間的信息交流也正常 那么整個程序模塊就正常 這樣 測試整個模塊的次數就變?yōu)?72 6 178 次 2 在實際測試中 程序員總是把每一個子模塊看成一個黑箱 即通過只考察是否執(zhí)行了正確的子模塊的方式來測試整個模塊 這樣 他可以先分別單獨測試5個模塊 以考察每個子模塊的工作是否正常 總共需要的測試次數為 18 45 28 38 43 172 例6 隨著人們生活水平的提高 某城市家庭汽車擁有量迅速增長 汽車牌照號碼需要擴容 交通管理部門出