分類加法計數(shù)原理和分步乘法計數(shù)原理的應(yīng)用高二下學(xué)期數(shù)學(xué)（人教A版2019選擇性必修第三冊）

第六章計數(shù)原理6.1分類加法計數(shù)原理與分步乘法計數(shù)原理6.1.2分類加法計數(shù)原理與分步乘法計數(shù)原理的應(yīng)用分類加法計數(shù)原理：完成一件事有兩類不同方案，在第1類方案中有m種不同的方法，在第2類方案中有n種不同的方法，那么完成這件事共有N＝m＋n種不同的方法.一、溫故知新推廣：如果完成一件事有n類不同方案,在第1類方案中有m1種不同的方法,在第2類方案中有m2種不同的方法，…，在第n類方案中有mn種不同的方法，那么完成這件事的方法總數(shù)為N＝m1＋m2＋…＋mn.分步乘法計數(shù)原理：完成一件事需要兩個步驟,做第1步有m種不同的方法，做第2步有n種不同的方法,那么完成這件事共有N＝m×n種不同的方法.推廣：如果完成一件事需要n個步驟,做第1步有m1種不同的方法，做第2步有m2種不同的方法，…，做第n步有mn種不同的方法,那么完成這件事的方法總數(shù)為N＝m1×m2×…×mn例4.要從甲、乙、丙3幅不同的畫中選出2幅,分別掛在左右兩邊墻上的指定位置,問共有多少種不同的掛法？二、自主探究分析:要完成的一件事情是“3幅不同的畫中選出2幅,并分別掛在左右兩邊墻上”,可以分步完成.解:從3幅畫中選出2幅，分別掛在左右兩邊墻上,可以分兩個步驟完成:第1步,從3幅畫中選1幅掛在左邊墻上，有3種選法:第2步,從剩下的2幅畫中選1幅掛在右邊墻上，有2種選法.根據(jù)分步乘法計數(shù)原理,不同掛法的種數(shù)N=3×2=6.

6種掛法如圖6.1-2所示

左邊

右邊相應(yīng)的掛法甲乙丙乙丙甲乙甲丙圖6.1-2乙甲乙丙丙甲丙乙甲乙甲丙1).要從甲、乙、丙3名工人中選出2名分別上白班和晚班，有多少種不同的選法？第一步:從3人中選1人上白班：第二步:從剩余2人中選1人上晚班：有3種方法有2種方法所以共有N＝3×2＝6（種）變式練習(xí)思考:如果先選一人上晚班，再選一人上白班，結(jié)果如何呢？2).從5人中選4人參加數(shù)、理、化學(xué)科競賽,其中數(shù)學(xué)2人，理、化各1人,求共有多少種不同的選法？第一步：先從5人中選一人參加物理競賽：有5種方法所以共有：N＝5×4×3＝60（種）第二步：再從剩下4人中選一人參加化學(xué)競賽：有4種方法第三步：最后從剩下3人中選二人參加數(shù)學(xué)競賽：有6種方法思考：有沒有其他的挑選順序呢？有的話，結(jié)果如何？例5.給程序模塊命名，需要用3個字符，其中首字符要求用字母A～G或U～Z，后兩個要求用數(shù)字1～9，問最多可以給多少個程序命名？分析:要完成的一件事情是“給一個程序模塊命名”,可以分三個步驟完成:第1步，選首字符：第2步，選中間字符:第3步，選最后一個字符.而首字符又可以分為兩類.在解題時有時既要分類又要分步解:由分類加法計數(shù)原理,首字符不同選法的種數(shù)為7+6=13.后兩個字符從1~9中選,因數(shù)字可以重復(fù),所以不同選法的種數(shù)都為9由分步乘法計數(shù)原理，不同名稱的個數(shù)是N=13×9×9=1053即最多可以給1053個程序模塊命名.

例6.

電子元件很容易實現(xiàn)電路的通與斷、電位的高與低等兩種狀態(tài)，而這也是最容易控制的兩種狀態(tài).因此計算機內(nèi)部就采用了每一位只有0或1兩種數(shù)字的記數(shù)法，即二進制.為了使計算機能夠識別字符，需要對字符進行編碼，每個字符可以用一個或多個字節(jié)來表示，其中字節(jié)是計算機中數(shù)據(jù)存儲的最小計量單位，每個字節(jié)由8個二進制位構(gòu)成.問：（1）一個字節(jié)（8位）最多可以表示多少個不同的字符？（2）計算機漢字國際碼（GB碼）包含了6763個漢字，一個漢字為一個字符，要對這些漢字進行編碼，每個漢字至少要用多少個字節(jié)表示？分析:要完成的一件事情是“確定1個字節(jié)各二進制位上的數(shù)字”,由于每個字節(jié)有8個二進制，每一位上的值有0,1兩種選擇，而且不同的順序代表不同的字符因此可以用分步乘法計數(shù)原理求解.如圖6.1-3.第1位第2位第3位第8位

···

2種2種2種2種圖6.1-3解答：一個字節(jié)可以表示28=256個不同的字符

因為一個字節(jié)可以表示256個不同的字符，所以兩個字節(jié)可以表示256×256=65536個不同字符，所以要表示6763個漢字，每個漢字至少要2個字節(jié)表示答案：(1)256；(2)2個

例7.

計算機編程人員在編寫好程序以后需要對程序進行測試，程序員需要知道到底有多少條執(zhí)行路徑（即程序從開始到結(jié)束的路線），以便知道需要提供多少個測試數(shù)據(jù).一般地，一個程序模塊由許多子模塊組成.如圖6.1-4所示是一個具有許多執(zhí)行路徑的程序模塊.（1）這個程序模塊有多少條執(zhí)行路徑；（2）為了減少測試時間，程序員需要設(shè)法減少測試次數(shù)，你能幫助程序員設(shè)計一個測試方法，以減少測試次數(shù)嗎？分析:整個模塊，任意一條執(zhí)行路徑都分兩步完成：第1步是從開始執(zhí)行到A點，第2步是從A點執(zhí)行到結(jié)束。而第1步可以由子模塊1、2、3的任何一個完成，第2步可以由子模塊4、5的任何一個完成。因此，分析一條命令在子模塊中的執(zhí)行路徑需要用到兩個計數(shù)原理。開始子模塊118條執(zhí)行路徑子模塊543條執(zhí)行路徑子模塊438條執(zhí)行路徑子模塊328條執(zhí)行路徑子模塊245條執(zhí)行路徑結(jié)束A圖6.1-4解答：(1)由分類加法計數(shù)原理可知，子模塊1、2、3中子路徑的條數(shù)共有：18+45+28=91條子模塊4、5中子路徑的條數(shù)共有：38+43=81條又由分步乘法計數(shù)原理可知，整個模塊的執(zhí)行路徑條數(shù)共有：91×81=7371條(2)在實際的測試中，程序員總是把每一個子模塊看成一個黑箱，即通過只考察是否執(zhí)行了正確的子模塊的方式來測試整個模塊。這樣，他可以分別單獨測試5個模塊，以考察子模塊的工作是否正常。需要測試的次數(shù)為：18+45+28+91+81=172次再測試各個模塊之間信息交流是否正常，只需要測試第1步和第2步的各個子模塊之間信息交流是否正常，需要測試的次數(shù)為：3×2=6次總共需要測試172+6=178次例8.通常，我國民用汽車牌的編號由兩部分組成:第一部分為用漢字表示的省、自治區(qū)、直轄市簡稱和用英文字母表示的發(fā)牌機關(guān)代號，第二部分由阿拉伯?dāng)?shù)字和英文字母組成的序號(如圖6.1-5).其中，序號的編碼規(guī)則為:(1)由10個阿拉伯?dāng)?shù)字和O,I之外24個英文字母組成;(2)最多只能有2個英文字母.如果某地級市發(fā)牌機關(guān)采用5位序號編碼，那么這個發(fā)牌機關(guān)最多能發(fā)放多少張汽車號牌?粵A·JR005圖6.1-5序號分析:由號牌編號的組成可知，序號的個數(shù)決定了這個發(fā)牌機關(guān)所能發(fā)放的號牌數(shù)，按序號編碼規(guī)則可知，每個序號中的數(shù)字、字母都是可重復(fù)的，并且可將序號分為三類:沒有字母、有一個字母、有兩個字母.以字母所在的位置為分類標(biāo)準(zhǔn)，可將有1個字母的序號分為五個子類，將有兩個字母的序號分為十個子類.解答:①沒有字母時，5位序號都是從0-9這10個數(shù)字中選1個，且必須5位序號都選好才算完成，所以根據(jù)分步乘法計數(shù)原理可知有：105=100000張②有一個字母時，可以分為字母在序號的第1位、第2位、第3位、第4位、第5位這5類；當(dāng)?shù)?位是字母時，根據(jù)分步乘法計數(shù)原理可知有：24×104=240000張

同理其余4類也有240000種，所以這類號牌合計有240000×5=1200000張③有兩個字母時，可以根據(jù)字母在第1和第2位、第1和第3位、第1和第4位、第1和第5位、第2和第3位、第2和第4位、第2和第5位、第3和第4位、第3和第5位、第4和第5位分為10類，每類有：24×24×103=576000張，合計：5760000張綜合以上三類最多可以發(fā)100000+1200000+5760000=7060000張?zhí)柵?1).某班有5人會唱歌，另有4人會跳舞，還有2人能歌善舞,從中任選1人表演一個節(jié)目，共可表演多少個節(jié)目？N＝5＋4＋2×2＝13（種）第1類：從會唱歌者中選1人唱歌；第2類：從會跳舞者中選1人跳舞；第3類：從能歌善舞者中選1人唱歌或跳舞；變式練習(xí)分析:任選1人表演，可以分為會唱歌、會跳舞、能歌善舞三類；(2).有架樓梯共6級,每次只允許上一級或兩級，求上完這架樓梯共有多少種不同的走法？第1類：有3次上兩級要走3步第2類：有2次上兩級需走4步第3類：有1次上兩級需走5步第4類：有0次上兩級需走6步1種走法6種走法5種走法1種走法N＝1＋6＋5＋1＝13（種）分析:上完這架樓梯，可以按上兩級的次數(shù)進行分類，上兩級的次數(shù)有3次、2次、1次和0次；

(3).在1，2，3，…，200這些自然數(shù)中，各個數(shù)位上都不含數(shù)字8的自然數(shù)共有多少個？不含8的一位數(shù)：有8個數(shù)不含8的二位數(shù)：十位不能為0和8有8種選擇，個位數(shù)不能為8有9種選擇，共有8×9=72個數(shù)不含8的三位數(shù)：①百位為1，十位跟個位各有9種選擇，共有9×9=81個數(shù)；②百位為2，只有200這1個數(shù)；綜上總共有N＝8＋72＋81+1＝162（個）分析:可以分別討論不含8的一位數(shù)、二位數(shù)、三位數(shù)；(4).從－3,－2,－1，0，1，2，3中任取三個不同的數(shù)作為拋物線y=ax2+bx+c(a≠0)的系數(shù)，如果拋物線過原點，且頂點在第一象限，問這樣的拋物線共有多少條？c取值a取值b取值1種3種3種N＝3×3×1＝9（種）c＝0a＜0b＞0三、課堂小結(jié)