11分類加法計數(shù)原理與分步乘法計數(shù)原理

1.1分類加法計數(shù)原理與分步乘法計數(shù)原理2011年9月29日天宮一號成功發(fā)射，此次有4種瀕臨滅絕的植物種子搭載“天宮一號”進(jìn)入太空，希望令種子產(chǎn)生基因變異.大哉，數(shù)學(xué)之為用！從火箭之速，到粒子之微，無處不用數(shù)學(xué)。

核糖核酸(RNA)分子由堿基按一定順序排列而成.已知堿基有4種，由成百上千個堿基組成的RNA分子的種數(shù)非常巨大.你知道它是怎樣算出來的嗎？計數(shù)問題

在計算機(jī)中的字符由二進(jìn)制表示，英文字母和漢字所需的字節(jié)數(shù)不一樣.你知道為什么嗎？問題1漢字在計算機(jī)的機(jī)器語言中是用16位的數(shù)字表示（0或1），你如何“數(shù)出”16位數(shù)字最多可以表示多少個不同的漢字？計數(shù)問題用A~Z或0~9給教室的座位編號有多少不同的號碼?分析:

給座位編號有2類方法,

第一類方法,用英文字母，有26種號碼;

第二類方法,用阿拉伯?dāng)?shù)字，有10種號碼;

所以有26+10=36

種不同號碼.

從甲地到乙地，可以乘火車，也可以乘汽車。一天中，火車有4班，汽車有2班。那么一天中乘坐這些交通工具從甲地到乙地共有多少種不同的走法?分析:

從甲地到乙地有2類方法,

第一類方法,乘火車，有4種方法;

第二類方法,乘汽車，有2種方法;

所以從甲地到乙地共有4+2=6

種方法.你能說出這兩個問題的共同特征嗎?分類加法計數(shù)原理完成一件事有兩類不同方案,在第1類方案中有m種不同的方法,在第2類方案中有n種不同的方法.那么完成這件事共有N=m+n種不同的方法兩類中的方法不相同例在填寫高考志愿表時,一名高中畢業(yè)生了解到,A,B兩所大學(xué)各有一些自己感興趣的強(qiáng)項專業(yè),具體如下:A大學(xué)生物學(xué)

化學(xué)

醫(yī)學(xué)

物理學(xué)

工程學(xué)B大學(xué)數(shù)學(xué)

會計學(xué)

信息技術(shù)學(xué)

法學(xué)這名同學(xué)可能的專業(yè)選擇共有多少種?分析:兩大學(xué)只能選一所一專業(yè),且沒有共同的強(qiáng)項專業(yè)54+=9這名同學(xué)可能的專業(yè)選擇共有9種

從甲地到乙地，可以乘火車，也可以乘汽車，還可以乘輪船。一天中，火車有4班,汽車有2班，輪船有3班。那么一天中乘坐這些交通工具從甲地到乙地共有多少種不同的走法?分析:

從甲地到乙地有3類方法,

第一類方法，乘火車，有4種方法;

第二類方法，乘汽車，有2種方法;

第三類方法，乘輪船，有3種方法;所以從甲地到乙地共有4+2+3=9種方法.

完成一件事有三類不同方案，在第1類方案中有m1種不同的方法，在第2類方案中有m2種不同的方法，在第3類方案中有m3種不同的方法。那么完成這件事共有

m1+m2+m3

種方法.

做一件事情，完成它可以有n類辦法,在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法。那么完成這件事共有＿＿＿＿＿＿＿＿＿＿種不同的方法N=m1+m2+…+mn

用前6個大寫英文字母和1~9個阿拉伯?dāng)?shù)字,以A1,A2,,B1,B2

的方式給教室的座位編號.有多少不同的號碼?A123456789A1A2A3A4A5A6A7A8A99種B1234567899種6×9=54如圖,由A村去B村的道路有3條，由B村去C村的道路有2條。從A村經(jīng)B村去C村，共有多少種不同的走法?A村B村C村北南中北南分析:

從A村經(jīng)B村去C村有2步,

第一步,由A村去B村有3種方法,

第二步,由B村去C村有2種方法,所以從A村經(jīng)B村去C村共有3×2=6

種不同的方法你能說出這兩個問題的共同特征嗎?分步乘法計數(shù)原理完成一件事需要兩個步驟,做第1步有m種不同的方法,做第2步有n種不同的方法,那么完成這件事共有N=m×n種不同的方法.例設(shè)某班有男生30名,女生24名.現(xiàn)要從中選出男、女各一名代表班級參加比賽,共有多少種不同的選法?分兩步進(jìn)行選取男女3024×=720再根據(jù)分步乘法原理若再要從語,數(shù),英三科科任老師中選出一名代表參加比賽,那又共有多少種選法?老師3×=2160

如果完成一件事需要三個步驟,做第1步有m1種不同的方法,做第2步有m2種不同的方法,做第3步有m3種不同的方法,那么完成這件事共有_________________種不同的方法.N=m1×m2×m3做一件事情，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事有_____________________種不同的方法.N=m1×m2×…×mn

例

書架第1層放有4本不同的計算機(jī)書,第2層放有3本不同的文藝書,第3層放有2本不同的體育書.(1)從書架中取1本書,有多少種不同取法?有3類方法,根據(jù)分類加法計數(shù)原理N=4+3+2=9(2)從書架第1,2,3層各取1本書,有多少種不同取法?分3步完成,根據(jù)分步乘法計數(shù)原理N=4×3×2=24解題關(guān)鍵：從總體上看做這件事情是“分類完成”,還是“分步完成”.再根據(jù)其對應(yīng)的計數(shù)原理計算.練習(xí)

要從甲、乙、丙3幅不同的畫中選出2幅,分別掛在左、右兩邊墻上的指定位置,問共有多少種不同的掛法?分兩步完成左邊右邊甲乙丙乙丙甲丙甲乙32第一步第二步×

在所有的兩位數(shù)中,個位數(shù)字大于十位數(shù)字的兩位數(shù)共有多少個？

分析1:

按個位數(shù)字是2,3,4,5,6,7,8,9分成8類,在每一類中滿足條件的兩位數(shù)分別是:1個,2個,3個,4個,5個,6個,7個,8個.根據(jù)加法原理共有1+2+3+4+5+6+7+8=36(個).分析2:

按十位數(shù)字是1,2,3,4,5,6,7,8分成8類,在每一類中滿足條件的兩位數(shù)分別是:8個,7個,6個,5個,4個,3個,2個,1個.根據(jù)加法原理共有8+7+6+5+4+3+2+1=36(個)練習(xí)

一個三位密碼鎖,各位上數(shù)字由0,1,2,3,4,5,

6,7,8,9十個數(shù)字組成,可以設(shè)置多少種三位數(shù)的密碼(各位上的數(shù)字允許重復(fù))?首位數(shù)字不為0的密碼數(shù)是多少?首位數(shù)字是0的密碼數(shù)又是多少?

分析:

按密碼位數(shù),從左到右

依次設(shè)置第一位、第二位、第三

位,需分為三步完成;

第一步,m1=10;

第二步,m2=10;

第三步,m3=10.

根據(jù)乘法原理,共可以設(shè)置

N=10×10×10=103

種三位數(shù)的密碼。練習(xí)

答:首位數(shù)字不為0的密碼數(shù)是

N=9×10×10=9×102

種,

首位數(shù)字是0的密碼數(shù)是

N=1×10×10=102

種。

由此可以看出,

首位數(shù)字不為0的密碼數(shù)與首位數(shù)字是0的密碼數(shù)之和等于密碼總數(shù)。問:若設(shè)置四位、五位、六位、…、十位等密碼,密碼數(shù)分別有多少種？答:它們的密碼種數(shù)依次是104,105,106,……種。開始子模塊118條執(zhí)行路徑子模塊328條執(zhí)行路徑子模塊245條執(zhí)行路徑子模塊543條執(zhí)行路徑子模塊438條執(zhí)行路徑結(jié)束A例5.計算機(jī)編程人員在編寫好程序以后要對程序進(jìn)行測試。程序員需要知道到底有多少條執(zhí)行路（即程序從開始到結(jié)束的線），以便知道需要提供多少個測試數(shù)據(jù)。一般的，一個程序模塊又許多子模塊組成，它的一個具有許多執(zhí)行路徑的程序模塊。問：這個程序模塊有多少條執(zhí)行路徑？另外為了減少測試時間，程序員需要設(shè)法減少測試次數(shù)，你能幫助程序員設(shè)計一個測試方式，以減少測試次數(shù)嗎？開始子模塊118條執(zhí)行路徑子模塊328條執(zhí)行路徑子模塊245條執(zhí)行路徑子模塊543條執(zhí)行路徑子模塊438條執(zhí)行路徑結(jié)束A分析：整個模塊的任意一條路徑都分兩步完成：第1步是從開始執(zhí)行到A點(diǎn)；第2步是從A點(diǎn)執(zhí)行到結(jié)束。而第步可由子模塊1或子模塊2或子模塊3來完成；第二步可由子模塊4或子模塊5來完成。因此，分析一條指令在整個模塊的執(zhí)行路徑需要用到兩個計數(shù)原理。例6.隨著人們生活水平的提高，某城市家庭汽車擁有量迅速增長，汽車牌照號碼需要擴(kuò)容。交通管理部門出臺了一種汽車牌照組成辦法，每一個汽車牌照都必須有３個不重復(fù)的英文字母和３個不重復(fù)的阿拉伯?dāng)?shù)字，并且３個字母必須合成一組出現(xiàn)，３個數(shù)字也必須合成一組出現(xiàn)，那么這種辦法共能給多少輛汽車上牌照?26x25x24x10x9x8=11232000

如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種?練習(xí)解:按地圖A、B、C、D四個區(qū)域依次分四步完成,

第一步,m1=3種,

第二步,m2=2種,

第三步,m3=1種,

第四步,m4=1種,所以根據(jù)乘法原理,得到不同的涂色方案種數(shù)共有N=3×2×1×1=6種。

如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種?練習(xí)問:若用2色、4色、5色等,結(jié)果又怎樣呢?

答:它們的涂色方案種數(shù)分別是0,4×3×2×2=48,5×4×3×3=180種。

如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種?練習(xí)如圖,該電路從A到B共有多少條不同的線路可通電？AB分類完成分步完成解:

從總體上看由A到B的通電線路可分二類,

第一類,m1=4條第二類,m3=2×2=4,條所以,根據(jù)加法原理,從A到B共有

N=4+4=8條不同的線路可通電