1、1.1分類計數(shù)原理分類計數(shù)原理與分步計數(shù)原理分步計數(shù)原理【教學(xué)目標(biāo)【教學(xué)目標(biāo)】 知識與技能：知識與技能：理解分類加法計數(shù)原理與分步乘法計數(shù)原理；會利用兩個原理分析和解決一些簡單的應(yīng)用問題 。 過程與方法：過程與方法：通過豐富的實例，理解分類加法計數(shù)原理與分步乘法計數(shù)原理，培養(yǎng)學(xué)生的歸納概括能力 。 情感態(tài)度與價值觀：情感態(tài)度與價值觀：引導(dǎo)學(xué)生形成 “自主學(xué)習(xí)”與“合作學(xué)習(xí)”等良好的學(xué)習(xí)方式 。【重點與難點【重點與難點】 重點：重點：分類計數(shù)原理(加法原理)與分步計數(shù)原理(乘法原理) ； 難點：難點：分類計數(shù)原理(加法原理)與分步計數(shù)原理(乘法原理) 的應(yīng)用。 用AZ或09給教室的座位編號思考思

2、考1思考思考2你能否發(fā)現(xiàn)這兩個問題有什么共同特征？你能否發(fā)現(xiàn)這兩個問題有什么共同特征？1 1、都是要完成一件事、都是要完成一件事2 2、用任何一類方法都能直接完成這件事、用任何一類方法都能直接完成這件事3 3、都是采用加法運算、都是采用加法運算 完成一件事有完成一件事有兩類不同的方案兩類不同的方案，在在第第1 1類類方案中有方案中有m種不同的方法，種不同的方法，在在第第2 2類類方案中有方案中有n種不同的方法，種不同的方法，那么完成這件事共有那么完成這件事共有 N = = m + + n種不同的方法。種不同的方法。兩類中的方法不相同例1 在填寫高考志愿表時,一名高中畢業(yè)生了解到,A,B兩所大學(xué)

3、各有一些自己感興趣的強項專業(yè),具體如下:A大學(xué)生物學(xué)生物學(xué)化學(xué)化學(xué)醫(yī)學(xué)醫(yī)學(xué)物理學(xué)物理學(xué)工程學(xué)工程學(xué)B大學(xué)數(shù)學(xué)數(shù)學(xué)會計學(xué)會計學(xué)信息技術(shù)學(xué)信息技術(shù)學(xué)法學(xué)法學(xué)分析分析: :兩大兩大學(xué) 只 能 選學(xué) 只 能 選一 所 一 專一 所 一 專業(yè)業(yè), ,且沒有且沒有共 同 的 強共 同 的 強項專業(yè)項專業(yè)54+=9 如果這名同學(xué)只能選一個專業(yè)如果這名同學(xué)只能選一個專業(yè),那么他共有那么他共有多少種選擇呢多少種選擇呢?變式： 在填寫高考志愿表時,一名高中畢業(yè)生了解到,A,B兩所大學(xué)各有一些自己感興趣的強項專業(yè),具體如下:A大學(xué)生物學(xué)生物學(xué)化學(xué)化學(xué)醫(yī)學(xué)醫(yī)學(xué)物理學(xué)物理學(xué)工程學(xué)工程學(xué)B大學(xué)數(shù)學(xué)數(shù)學(xué)會計學(xué)會計學(xué)信息技術(shù)

4、學(xué)信息技術(shù)學(xué)法學(xué)法學(xué)54+=14 如果這名同學(xué)只能選一個專業(yè)如果這名同學(xué)只能選一個專業(yè),那么他共有那么他共有多少種選擇呢多少種選擇呢?C大學(xué)大學(xué)機械制造機械制造建筑學(xué)建筑學(xué)廣告學(xué)廣告學(xué)漢語言文學(xué)漢語言文學(xué)韓語韓語+5 如果完成一件事情有如果完成一件事情有3類不同方案，類不同方案，在第在第1類方案中有類方案中有m1種不同的方法，種不同的方法，在第在第2類方案中有類方案中有m2種不同的方法，種不同的方法，在第在第3類方案中有類方案中有m3種不同的方法，種不同的方法，那么完成這件事情有那么完成這件事情有 種不同的方法種不同的方法N=m1+m2+m3探究探究1 完成一件事有完成一件事有 n 類不同的方

5、案類不同的方案，在在第第1 1類類方案中有方案中有 m1 種不同的方法，種不同的方法，在在第第2 2類類方案中有方案中有 m2 種不同的方法，種不同的方法，那么完成這件事共有那么完成這件事共有 種不同的方法。種不同的方法。 在在第第n類類方案中有方案中有mn種不同的方法，種不同的方法，nmmmN 21 用前6個大寫英文字母和19個阿拉伯?dāng)?shù)字,以A1,A2,B1,B2的方式給教室的座位編號.A123456789A1A2A3A4A5A6A7A8A99種B1234567899種6 9 =54思考思考3這件事這件事 分兩步完成：分兩步完成： 第第1步，步，確定一個英文字母，有確定一個英文字母，有6種種

6、不同方法不同方法 第第2步，步，確定一個阿拉伯?dāng)?shù)字，有確定一個阿拉伯?dāng)?shù)字，有9種種不同方法不同方法 如圖如圖,由由A村去村去B村的道路有村的道路有3條，由條，由B村去村去C村的道路有村的道路有2條。從條。從A村經(jīng)村經(jīng)B村去村去C村，村，共有多少種不同的走法共有多少種不同的走法?A村村B村C村村北北南南中中北北南南分析分析: 從從A村經(jīng)村經(jīng) B村去村去C村有村有 2 步步, 第一步第一步, 由由A村去村去B村有村有 3 種方法種方法, 第二步第二步, 由由B村去村去C村有村有 2 種方法種方法,所以從所以從A村經(jīng)村經(jīng) B村去村去C村共有村共有 3 2 = 6 種不同種不同的方法的方法思考思考4

7、完成一件事有完成一件事有兩類兩類不同方案不同方案, ,在第在第1 1類方案中有類方案中有m種不種不同的方法同的方法, ,在第在第2 2類類方案中有方案中有n種不同的種不同的方法方法. .那么完成這件那么完成這件事共有事共有 種不同的方法種不同的方法. .N= =m+ +n分類加法計數(shù)原理：分類加法計數(shù)原理： 完成一件事需完成一件事需要要兩個步驟兩個步驟, ,做第做第1 1步有步有m種不同的方法種不同的方法, ,做第做第2 2步有步有n種不同種不同的方法的方法. .那么完成這那么完成這件事共有件事共有 N= =mn分步乘法計數(shù)原理分步乘法計數(shù)原理：種不同的方法種不同的方法. .例2 設(shè)某班有男生

8、30名,女生24名.現(xiàn)要從中選出男、女各一名代表班級參加比賽,共有多少種不同的選法?分兩步進行選取男女3024=720再根據(jù)分步乘法原理若再要從語,數(shù),英三科科任老師中選出一名代表參加比賽,那又共 有 多 少 種 選 法 ?老師3=2160 如果完成一件事情需要如果完成一件事情需要3個步驟，個步驟，第第1步有步有m1種不同的方法，種不同的方法，第第2步有步有m2種不同的方法，種不同的方法，第第3步有步有m3種不同的方法，種不同的方法，那么完成這件事情有那么完成這件事情有 種不同的方法種不同的方法N=m1m2m3探究探究2 完成一件事需要完成一件事需要 n 個步驟個步驟，第第1 1步步有有 m1

9、 種不同的方法，種不同的方法，第第2 2步步有有 m2 種不同的方法，種不同的方法，那么完成這件事共有那么完成這件事共有 種不同的方法。種不同的方法。 第第n步步有有mn種不同的方法，種不同的方法，nmmmN21例3 書架第1層放有4本不同的計算機書,第2層放有3本不同的文藝書,第3層放有2本不同的體育書.(1)從書架中取1本書,有多少種不同取法?有3類方法,根據(jù)分類加法計數(shù)原理N=4+3+2=9(2)從書架第1,2,3層各取1本書,有多少種不同取法?分3步完成,根據(jù)分步乘法計數(shù)原理N=432=24 要從甲、乙、丙3幅不同的畫中選出2幅,分別掛在左、右兩邊墻上的指定位置,問共有多少種不同的掛法

10、?分兩步完成左邊右邊甲乙丙乙丙甲丙甲乙32第一步第二步例4分類加法計數(shù)原理分類加法計數(shù)原理分步乘法計數(shù)原理分步乘法計數(shù)原理相同點相同點不同點不同點注意點注意點用來計算用來計算“完成一件事完成一件事”的方法種數(shù)的方法種數(shù)每類每類方案中的每一方案中的每一種方法都能種方法都能_ _ 完成這件事完成這件事每步每步_才才算完成這件事情算完成這件事情（每步中的每一種（每步中的每一種方法方法不能獨立不能獨立完成完成這件事）這件事）類類類類相加相加步步步步相乘相乘分類分類完成完成分步分步完成完成?.91,ZUGA,3,5序序命命名名問問最最多多可可以以給給多多少少個個程程后后兩兩個個要要求求用用數(shù)數(shù)字字或或要

11、要求求用用字字母母其其中中首首字字符符個個字字符符需需要要用用給給程程序序模模塊塊命命名名例例.3;,2;,1:,類類而而首首字字符符又又可可以以分分為為兩兩符符步步選選最最后后一一個個字字第第選選中中間間字字符符步步第第選選首首字字符符步步第第可可以以分分三三個個步步驟驟要要給給一一個個程程序序模模塊塊命命名名分分析析.1367,.種選法首字符共有由分類加法計數(shù)原理先計算首字符的選法解.1053,10539913,.個程序命名即最多可以給個不同的名稱最多可以有理由分步乘法計數(shù)原名稱再計算可能的不同程序?嗎嗎你還能給出不同的解法你還能給出不同的解法例5?RNA,100RNA.,RNA.U,G,

12、C,A,4.,RNA.RNA6分分子子少少種種不不同同的的那那么么能能有有多多個個堿堿基基組組成成分分子子由由有有一一類類假假設(shè)設(shè)位位置置上上的的堿堿基基無無關(guān)關(guān)個個位位置置上上的的堿堿基基與與其其他他所所以以在在任任意意一一序序出出現(xiàn)現(xiàn)各各種種堿堿基基能能夠夠以以任任意意次次中中分分子子在在一一個個表表示示分分別別用用同同的的堿堿基基種種不不總總共共有有分分所所占占據(jù)據(jù)一一種種稱稱為為堿堿基基的的化化學(xué)學(xué)成成由由長長鏈鏈中中每每一一個個位位置置上上都都至至數(shù)數(shù)千千個個位位置置的的長長鏈鏈甚甚分分子子是是一一個個有有著著數(shù)數(shù)百百個個一一個個的的化化學(xué)學(xué)成成分分現(xiàn)現(xiàn)分分子子是是在在生生物物細(xì)細(xì)胞

13、胞中中發(fā)發(fā)核核糖糖核核酸酸例例例6.U,G,C,A,100,100任選一個來占據(jù)任選一個來占據(jù)中中每個位置都可以從每個位置都可以從個位置個位置這時我們有這時我們有個堿基組成的長鏈個堿基組成的長鏈用下面的圖來表示由用下面的圖來表示由分析分析位位第第1位位第第2位位第第3位位第第100種種4種種4種種4種種4 .4,U,G,C,A,.,100100充方法種填每個位置有中任選一個填入從置中從左到右依次在每個位如上圖所示個位置個堿基組成的長鏈共有解長度為根據(jù)分步乘法計數(shù)原理,分子數(shù)目有的所有可能的不同RNA100.4444100個 4100個.NAR.,106.1460100資資料料的的有有關(guān)關(guān)閱閱一

14、一下下以以自自己己查查的的同同學(xué)學(xué)可可有有興興趣趣數(shù)數(shù)非非常常大大的的這這是是一一個個 ?,6763GB2?81:.8,.,10.,7表示表示字至少要用多少個字節(jié)字至少要用多少個字節(jié)每個漢每個漢要對這些漢字進行編碼要對這些漢字進行編碼個漢字為一個字符個漢字為一個字符一一個漢字個漢字包含了包含了碼碼計算機漢字國標(biāo)碼計算機漢字國標(biāo)碼同的字符同的字符最多可以表示多少個不最多可以表示多少個不位位一個字節(jié)一個字節(jié)問問個二進制位構(gòu)成個二進制位構(gòu)成每個字節(jié)由每個字節(jié)由最小計量單位最小計量單位據(jù)存儲的據(jù)存儲的其中字節(jié)是計算機中數(shù)其中字節(jié)是計算機中數(shù)多個字節(jié)來表示多個字節(jié)來表示每個字符可以用一個或每個字符可以用

15、一個或需要對字符進行編碼需要對字符進行編碼字符字符為了使計算機能夠識別為了使計算機能夠識別即二進制即二進制種數(shù)字的記數(shù)法種數(shù)字的記數(shù)法兩兩或或了每一位只有了每一位只有因此計算機內(nèi)部就采用因此計算機內(nèi)部就采用狀態(tài)狀態(tài)兩種兩種而這也是最容易控制的而這也是最容易控制的的高與低等兩種狀態(tài)的高與低等兩種狀態(tài)的通與斷、電位的通與斷、電位易實現(xiàn)電路易實現(xiàn)電路容容電子元件很電子元件很例例例7.,1 , 0,8數(shù)原理求解本題數(shù)原理求解本題因此可以用分步乘法計因此可以用分步乘法計字符字符同的同的而且不同的順序代表不而且不同的順序代表不兩種選擇兩種選擇值都有值都有每一位上的每一位上的個二進制位個二進制位由于每個字節(jié)

16、有由于每個字節(jié)有分析分析;256222222222,.2,88個不同的字符一個字節(jié)最多可以表示法計數(shù)原理根據(jù)分步乘種選擇每位上有位一個字節(jié)有來表示一個字節(jié)用圖解31.1位位第第1位位第第2位位第第3位位第第8種種2種種2種種2種種2 31.1圖圖 .256,256.2,6763,12種表示方法后一個字節(jié)也有種不同的表示方法前一個字節(jié)有能夠表示多少個字符個字節(jié)我們就考慮用個字符不夠不同用一個字節(jié)所能表示的知由.2,.6763,536652562562,個字節(jié)表示每個漢字至少要用所以要表示這些漢字的漢字個數(shù)經(jīng)大于漢字國標(biāo)碼包含這已個不同字符示個字節(jié)可以表根據(jù)分步乘法計數(shù)原理?,?:.,41.1.,

17、.),(.8以以減減少少測測試試次次數(shù)數(shù)嗎嗎法法序序員員設(shè)設(shè)計計一一個個測測試試方方少少測測試試次次數(shù)數(shù)你你能能幫幫助助程程程程序序員員需需要要設(shè)設(shè)法法減減時時間間為為了了減減少少測測試試另另外外執(zhí)執(zhí)行行路路徑徑這這個個程程序序模模塊塊有有多多少少條條問問路路徑徑的的程程序序模模塊塊它它是是一一個個具具有有許許多多執(zhí)執(zhí)行行如如圖圖模模塊塊組組成成一一個個程程序序模模塊塊由由許許多多子子的的一一般般個個測測試試數(shù)數(shù)據(jù)據(jù)以以便便知知道道需需要要提提供供多多少少線線路路即即程程序序從從開開始始到到結(jié)結(jié)束束的的徑徑多多少少條條執(zhí)執(zhí)行行路路到到底底有有程程序序員員需需要要知知道道要要對對程程序序進進行行

18、測測試試好好程程序序以以后后需需計計算算機機編編程程人人員員在在編編寫寫例例例8條執(zhí)行路徑條執(zhí)行路徑子模塊子模塊181條執(zhí)行路徑條執(zhí)行路徑子模塊子模塊452條執(zhí)行路徑條執(zhí)行路徑子模塊子模塊283條執(zhí)行路徑條執(zhí)行路徑子模塊子模塊435條執(zhí)行路徑條執(zhí)行路徑子模塊子模塊384結(jié)束結(jié)束開始開始A.A2;A1:到到結(jié)結(jié)束束點點執(zhí)執(zhí)行行步步是是從從第第點點步步是是從從開開始始執(zhí)執(zhí)行行到到第第成成行行路路徑徑都都分分兩兩步步完完整整個個模模塊塊的的任任意意一一條條執(zhí)執(zhí)分分析析來來或子模塊或子模塊或子模塊或子模塊步可由子模塊步可由子模塊而第而第3211;完成完成.542來完成來完成或子模塊或子模塊步可由子模塊

19、步可由子模塊第第.原理原理計數(shù)計數(shù)執(zhí)行路徑需要用到兩個執(zhí)行路徑需要用到兩個一條指令在整個模塊的一條指令在整個模塊的分析分析因此因此,);(91284518321,條的子路徑共有子模塊或或子模塊子模塊由分類加法計數(shù)原理解);(81433854條的子路徑共有或子模塊子模塊).(73718191,條有整個模塊的執(zhí)行路徑共又由分步乘法計數(shù)原理.1724338284518.,5,.,試次數(shù)為總共需要測作是否一正常以考察每個子模塊的工塊個模它可以先分別單獨測試這樣來測試整個模塊了正確的子模塊的方式即通過只考察是否執(zhí)行黑箱模塊看成一個程序員總是把每一個子在實際測試中.632,21,需要測試次數(shù)為常之間的信息

20、交流是否正步中的各子模塊步中的各個子模塊和第試程序第只需要測信息交流是否正常再測試各個模塊之間的 .1786172,.,次為試整個模塊的次數(shù)就變測這樣作正常那么整個程序模塊就工息交流也正常并且各子模塊之間的信工作如果每個子模塊都正常.7371178,的差距是非常大的與顯然?實現(xiàn)減少測試次數(shù)的嗎你看出了程序員是如何?.3 ,3,33,.,9少輛汽車上牌照少輛汽車上牌照那么這種辦法共能給多那么這種辦法共能給多必須合成一組出現(xiàn)必須合成一組出現(xiàn)個數(shù)字也個數(shù)字也現(xiàn)現(xiàn)個字母必須合成一組出個字母必須合成一組出并且并且字字個不重復(fù)的阿拉伯?dāng)?shù)個不重復(fù)的阿拉伯?dāng)?shù)復(fù)的英文字母和復(fù)的英文字母和個不重個不重有有每一個汽

21、車牌照都必須每一個汽車牌照都必須成辦法成辦法種汽車牌照組種汽車牌照組交通管理部門出臺了一交通管理部門出臺了一擴容擴容汽車牌照號碼需要汽車牌照號碼需要庭汽車擁有量迅速增長庭汽車擁有量迅速增長某城市家某城市家高高著人們生活水平的提著人們生活水平的提隨隨例例.6.,2,個個步步驟驟的的字字母母和和數(shù)數(shù)字字可可以以分分確確定定一一個個牌牌照照在在右右母母組組合合在在左左和和字字母母組組合合即即字字類類牌牌照照可可以以分分為為按按照照新新規(guī)規(guī)定定分分析析例9.,2類的字母組合在右另一一類字母組合在左類將汽車牌照分為解:6,字母和數(shù)字照的個步驟確定一個汽車牌分字母組合在左時;26,126,1種選法有放在首

22、位個個字母中選從步第;25,2,125,2種選法有位放在第個個字母中選從剩下的步第;24,3,124,3種選法有位放在第個個字母中選從剩下的步第;10,4,110,4種選法有位放在第個個數(shù)字中選從步第;9,5,19,5種選法有位放在第個個數(shù)字中選從剩下的步第.8,6,18,6種選法有位放在第個個數(shù)字中選從剩下的步第.000232118910242526,個有字母組合在左的牌照共根據(jù)分步乘法計數(shù)原理.00023211,個有字母組合在右的牌照也同理.224640001123200011232000,輛汽車上牌照共能給所以 在所有的兩位數(shù)中,個位數(shù)字大于十位數(shù)字的兩位數(shù)共有多少個？練習(xí) 一個三位密碼

23、鎖一個三位密碼鎖,各位上數(shù)字由各位上數(shù)字由0,1,2,3,4,5,6,7,8,9十個數(shù)字組成十個數(shù)字組成,可以設(shè)置多少種三位數(shù)的可以設(shè)置多少種三位數(shù)的密碼密碼(各位上的數(shù)字允許重復(fù)各位上的數(shù)字允許重復(fù))?首位數(shù)字不為首位數(shù)字不為0的的密碼數(shù)是多少密碼數(shù)是多少?首位數(shù)字是首位數(shù)字是0的密碼數(shù)又是多少的密碼數(shù)又是多少? 分析分析: 按密碼位數(shù)按密碼位數(shù),從左到右從左到右依次設(shè)置第一位、第二位、第三依次設(shè)置第一位、第二位、第三位位, 需分為三步完成需分為三步完成; 第一步第一步, m1 = 10; 第二步第二步, m2 = 10; 第三步第三步, m3 = 10. 根據(jù)乘法原理根據(jù)乘法原理, 共可以

24、設(shè)置共可以設(shè)置 N = 101010 = 103 種三位數(shù)的密碼。種三位數(shù)的密碼。練習(xí) 答答:首位數(shù)字不為首位數(shù)字不為0的密碼數(shù)是的密碼數(shù)是 N =91010 = 9102 種種, 首位數(shù)字是首位數(shù)字是0的密碼數(shù)是的密碼數(shù)是 N = 11010 = 102 種。種。 由此可以看出由此可以看出, 首位數(shù)字不為首位數(shù)字不為0的密碼數(shù)與首的密碼數(shù)與首位數(shù)字是位數(shù)字是0的密碼數(shù)之和等于密碼總數(shù)。的密碼數(shù)之和等于密碼總數(shù)。問問: 若設(shè)置四位、五位、六位、若設(shè)置四位、五位、六位、十位等、十位等密碼密碼,密碼數(shù)分別有多少種？密碼數(shù)分別有多少種？答答:它們的密碼種數(shù)依次是它們的密碼種數(shù)依次是 104 , 10

25、5, 106, 種。種。解解: 按地圖按地圖A、B、C、D四個區(qū)域依次分四四個區(qū)域依次分四步完成步完成, 第一步第一步, m1 = 3 種種, 第二步第二步, m2 = 2 種種, 第三步第三步, m3 = 1 種種, 第四步第四步, m4 = 1 種種,所以根據(jù)乘法原理所以根據(jù)乘法原理, 得到不同的涂色方案種得到不同的涂色方案種數(shù)共有數(shù)共有 N = 3 2 11 = 6 種。種。 如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種?練習(xí)問問: 若用若用2色、色、4色、色、5色等色等,結(jié)果又怎樣呢結(jié)果又

26、怎樣呢? 答答:它們的涂色方案種它們的涂色方案種數(shù)分別是數(shù)分別是 0, 4322 = 48, 5433 = 180 種。種。 如圖,要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種,允許同一種顏色使用多次,但相鄰區(qū)域必須涂不同的顏色,不同的涂色方案有多少種?練習(xí)解解: 從總體上看由從總體上看由A到到B的通電線路可分二類的通電線路可分二類, 第一類第一類, m1 = 4 條條 第二類第二類, m3 = 22 = 4, 條條 所以所以, 根據(jù)加法原理根據(jù)加法原理, 從從A到到B共有共有 N = 4 + 4 = 8 條不同的線路可通電條不同的線路可通電.如圖如圖, ,該電路從該電路從A A到到B B共有多少條不同的線路共有多少條不同的線路可通電？可通電？