1.1.2分類(lèi)加法計(jì)數(shù)原理與分步乘法計(jì)數(shù)原理.ppt

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