【正文】 例 4. 要從甲、乙、丙 3幅不同的畫中選出 2幅，分別掛在左、右兩邊墻上的指定位置，問共有多少種不同的掛法？ 解：從 3 幅畫中選出 2 幅分別掛在左、右兩邊墻上，可以分兩個步驟完成：第 1 步，從 3 幅畫中選 1 幅掛在左邊墻上，有 3 種選法；第 2 步，從剩下的 2 幅畫中選 1 幅掛在右邊墻上，有 2 種選法．根據(jù)分步乘法計數(shù)原理，不同掛法的種數(shù)是 [來源 :學(xué)科網(wǎng) ] N=3 2=6 . 6 種掛法可以表示如下： 分類加法計數(shù)原理和分步乘法計數(shù)原理，回答的都是有關(guān)做一件事的不同方法的種數(shù)問題．區(qū)別在于：分類加法計數(shù)原理針對的是“分類”問題，其中各種方法相互獨立，用其中任何一種方法都可以做完這件事，分步乘法計數(shù)原理針對的是“分步”問題，各個步驟中的方法互相依存，只有各個步驟都完成才算做完這件事． 練習(xí) 1．填空： ( 1 ）一件工作可以用 2 種方法完成，有 5 人只會用第 1 種方法完成，另有 4 人只會用第 2 種方法完成，從中選出 l 人來完成這件工作，不 同選法的種數(shù)是＿ 。到 9 之間的一個數(shù)字，那么這個電話局不同的電話號碼最多有多少個 3． 從 5 名同學(xué)中選出正、副組長各 1 名，有多少種不同的選法？ 4． 某商場有 6 個門，如果某人從其中的任意一個門進人商場，并且要求從其他的門出去，共有多少種不同的進出商 場的方式？ 第四課時 例 ，需要用 3 個字符，其中首 字符要求用字母 A～ G 或 U～ Z , 后兩個要求用數(shù)字 1～ 9．問最多可以給多少個程序命名？ 分析：要給一個程序模塊命名，可以分三個步驟：第 1 步，選首字符；第 2 步，選中間字符；第 3 步，選最后一個字符．而首字符又可以分為兩類． 解 ：先計算首字符的選法．由分類加法計數(shù)原理，首字符共有 7 + 6 = 13 種選法． 再計算可能的不同程序名稱．由分步乘法計數(shù)原理，最多可以有 13 9 9 = = 1053 個不同 的名稱，即最多可以給 1053 個程序命 名． 例 2. 核糖核酸（ RNA）分子是在生物細胞中發(fā)現(xiàn)的化學(xué)成分一個 RNA 分子是一個有著數(shù)百個甚至數(shù)千個位置的長鏈，長鏈中每一個位置上都由一種稱為堿基的化學(xué)成分所占據(jù)． 總共有 4 種不同的堿基，分別用 A,C,G,U表示．在一個 RNA 分子中，各種堿基能夠以任意次序出現(xiàn)，所以在任意一個位置上的堿基與其他位置上的堿基無關(guān)．假設(shè)有一類 RNA 分子由 100 個堿基組成，那么能有多少種不同的 RNA 分子？ 分析 ：用圖 1. 1一 2 來表示由 100個堿基組成的長鏈，這時我們共有 100個位置，每個位置都 可以從 A , C , G , U 中任選一個來占據(jù)． 解 ： 100個堿基組成的長鏈共有 100個位置，如圖 1 . 1一 2所示．從左到右依次在每一個位置中，從 A , C , G , U 中任選一個填人，每個位置有 4 種填充方法．根據(jù)分步乘法計數(shù)原理，長度為 100 的所有可能的不同 RNA 分子數(shù)目有 1001004 4 4 4? ? ? ?（個） 例 、電位的高與低等兩種狀態(tài)，而這也是最容易控制的兩種狀態(tài)．因此計算機內(nèi)部就采用了每一位只有 O 或 1 兩種數(shù)字的記數(shù)法，即二進制．為了使計算機能夠識別字符，需 要對字符進行編碼，每個字符可以用一個或多個字節(jié)來表示，其中字節(jié)是計算機中數(shù)據(jù)存儲的最小計量單位，每個字節(jié)由 8 個二進制位構(gòu)成．問： (1）一個字節(jié)（ 8 位）最多可以表示多少個不同的字符？ (2）計算機漢字國標(biāo)碼（ GB 碼）包含了 6 763 個漢字，一個漢字為一個字符，要對這些漢字進行編碼，每個漢字至少要用多少個字節(jié)表示？ 分析 ：由于每個字節(jié)有 8 個二進制位，每一位上的值都有 0,1兩種選擇，而且不同的順序代表不同的字符，因此可以用分步乘法計數(shù)原理求解本題． 解： (1）用圖 3 來表示一個字節(jié)． 圖 1 . 1 一 3 一個字節(jié)共有 8 位，每位上有 2 種選擇．根據(jù)分步乘法計數(shù)原理，一個字節(jié)最多可以表示 2 2 2 2 2 2 2 2= 28 =256 個不同的字符； ( 2）由（ 1 ）知，用一個字節(jié)所能表示的不同字符不夠 6 763 個，我們就考慮用 2 個字節(jié)能夠表示多少個字符．前一個字節(jié)有 256 種不同的表示方法，后一個字節(jié)也有 256 種表示方法．根據(jù)分步乘法計數(shù)原理， 2個字節(jié)可以表示 256 256 = 65536 個不同的字符，這已經(jīng)大于漢字國標(biāo)碼包含的漢字個數(shù) 6 763．所以要表示這些漢字，每個漢字至少要用 2 個字節(jié)表示． 例 ．程序員需要知道到底有多少條執(zhí)行路徑（即程序從開始到結(jié)束的路線），以便知道需要提供多少個測試數(shù)據(jù)．一般地，一個程序模塊由許多子模塊組成．如圖 4，它是一個具有許多執(zhí)行路徑的程序模塊．問：這個程序模塊有多少條執(zhí)行路徑？ 另外，為了減少測試時間，程序員需要設(shè)法減少測試次數(shù)你能幫助程序員設(shè)計一個測試方法，以減少測試次數(shù)嗎？ 圖 4 分析：整個模塊的任意一條執(zhí)行路徑都分兩步完成：第 1 步是從開始執(zhí)行到 A 點；第 2 步是從 A 點執(zhí)行到結(jié)束．而第 1 步可由子模塊 1 或子模塊 2 或子模塊 3 來完成；第 2 步可由子模塊 4 或子模塊 5 來完成．因此，分析一條指令在整個模塊的執(zhí)行路徑需要用到兩個計數(shù)原理． 解：由分類加法計數(shù)原理，子模塊 1 或子模塊 2 或子模塊 3 中的子路徑共有 18 + 45 + 28 = 91 （條） 。至于誰是“接受單位”，不要管它在生活中原來的意義，只要 nm? .個數(shù)為 m 的一個元素就是“接受單位”，于是，方 法還可以簡化為 A少多.這里的“多”只要 ?“少” . ② .被分配元素和接受單位的每個成員都有“歸宿 ” ,并且不限制一對一的分配問題，方法是分組問題的計算公式乘以 kkA . 。 ( 2 ）從書架的第 1 , 2 , 3 層各取 1 本書，可以分成 3 個步驟完成：第 1 步從第 1 層取 1 本計算機書，有 4 種方法；第 2 步從第 2 層取 1 本文藝書，有 3 種方法；第 3 步從第 3 層取 1 本體育書，有 2 種方法．根據(jù)分步乘法計數(shù)原理，不同取法的種數(shù)是 1 2 3N m m m? ? ? =4 3 2=24 . （ 3） 26232434 ???????N 。 子模塊 4 或子模塊 5 中的子路徑共有 38 + 43 = 81 （條） . 又由分步乘法計數(shù)原理，整個模塊的執(zhí)行路徑共有 91 81 = 7 371（條） . 在實際測試中，程序員總是把每一個子模塊看成一個黑箱，即通過只考察是否執(zhí)行了正確的子模塊的方式來測試整個模塊．這樣，他可以先分別單獨測試 5 個模塊，以考察每個子模塊的工作是否正常．總共需要的測試次數(shù)為 18 + 45 + 28 + 38 + 43 =172. 再測試各個模塊之間的信息交流是否正常，只需要測試程序第 1 步中 的各個子模塊和第 2 步中的各個子模塊之間的信息交流是否正常，需要的測試次數(shù)為 3 2=6 . 如果每個子模塊都工作正常，并且各個子模塊之間的信息交流也正常，那么整個程序模塊就工作正常．這樣，測試整個模塊的次數(shù)就變?yōu)? 172 + 6=178（次） . 顯然， 178 與 7371 的差距是非常大的． 你看出了程序員是如何實現(xiàn)減少測試次數(shù)的嗎？ 例 ，某城市家庭汽車擁有量迅速增長，汽車牌照號碼需交通管理部門出臺了一種汽車牌照組成辦法，每一個汽車牌照都必須有 3個不重復(fù)的英文字母和 3 個不重復(fù)的阿拉伯?dāng)?shù)字，并且 3 個字母必須合成一組出現(xiàn)， 3個數(shù)字也必須合成一組出現(xiàn)．那么這種辦法共能給多少輛汽車上牌照？ 分析：按照新規(guī)定，牌照可以分為 2類，即字母組合在左和字母組合在右．確定一個牌照的字母和數(shù)字可以分 6個步驟． 解：將汽車牌照分為 2 類，一類的字母組合在左，另一類的字母組合在右．字母組合在左時，分 6個步驟確定一個牌照的字母和數(shù)字： 第 1步，從 26個字母中選 1個，放在首位，有 26種選法； 第 2步，從剩下的 25個字母中選 1個，放在第 2位，有 25種選法； 第 3步，從剩下的 24個字母中選 1個，放在第 3位，有 24種選法； 第 4步，從 10個數(shù)字中選 1個，放在第 4 位，有 10種選法； 第 5步，從剩下的 9個數(shù)字中選 1個，放在第 5位，有 9種選法； 第 6步，從剩下的 8個字母中選 1個，放在第 6位，有 8種選法． 根據(jù)分步乘法計數(shù)原理，字母組合在左的牌照共有 26 25 24 10 9 8=11 232 000（個） . 同理，字母組合在右的牌照也有 11232 000 個． 所以，共能給 11232 000 + 11232 000 = 22464 000（個） . 輛汽車上牌照． 用兩個計數(shù)原理解決 計數(shù)問題時，最重要的是在開始計算之前要進行仔細分析 ― 需要分類還是需要分步．分類要做到“不重不漏”．分類后再分別對每一類進行計數(shù)，最后用分類加法計數(shù)原理求和，得到總數(shù)．分步要做到“步驟完整” ― 完成了所有步驟，恰好完成任務(wù)，當(dāng)然步與步之間要相互獨立．分步后再計算每一步的方法數(shù)，最后根據(jù)分步乘法計數(shù)原理，把完成每一步的方法數(shù)相乘，得到總數(shù)． 練習(xí) 1． 乘積 1 2 3 1 2 3 1 2 3 4