1.1.2分類加法計數(shù)原理與分步乘法計數(shù)原理.ppt

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