分類加法和分步乘法PPT課件

.,1,1.1分類加法計數(shù)原理與分步乘法計數(shù)原理,計數(shù)原理,.,2,2008年29屆夏季奧運會在北京舉行奧運會足球賽共有個隊參賽它們先分成個小組進行循環(huán)賽，決出強，這個隊按確定的程序進行淘汰賽后，最后決出冠亞軍，此外還決出了第三、第四名問一共安排了多少場比賽？,實際問題,要回答這個問題，就要用到排列、組合的知識在運用排列、組合方法時，經(jīng)常要用到分類加法計數(shù)原理與分步乘法計數(shù)原理,.,3,問題2秋天到了，學校舉行“全民健身”登山活動,山的南面有3條登山路線,山的北面有2條登山路線,要登上山頂,問共有多少種不同的路線？,問題1某班級有34位男生,15位女生,現(xiàn)要選一位同學參加演講比賽,則有多少種不同的選法？,探究1：你能說說以上兩個問題的共同特征嗎？,.,4,分類加法計數(shù)原理,完成一件事有兩類不同方案，在第1類方案中有m種不同的方法,在第2類方案中有n種不同的方法.那么完成這件事共有N=m+n種不同的方法.,.,5,問題2秋天到了，學校舉行“全民健身”登山活動,山的南面有3條登山路線,山的北面有2條登山路線,要登上山頂,問共有多少種不同的路線？,問題1我們班級有34位男生,15位女生,現(xiàn)要選一位同學參加演講比賽,則有多少種不同的選法？,在第1類方案中有m種不同的方法,在第2類方案中有n種不同的方法.那么完成這件事共有N=m+n種不同的方法.,完成一件事,有兩類不同方案,.,6,例1：在填寫高考志愿表時,一名高中畢業(yè)生了解到,A,B兩所大學各有一些自己感興趣的強項專業(yè)，具體情況如下：A大學B大學生物學數(shù)學化學會計學醫(yī)學信息技術學物理學法學工程學如果這名同學只能選擇一個專業(yè),那么他共有多少種選擇呢？,.,7,想一想在填寫高考志愿表時,一名高中畢業(yè)生了解到,A,B,C三所大學各有一些自己感興趣的強項專業(yè)，具體情況如下：A大學B大學生物學數(shù)學化學會計學醫(yī)學信息技術學物理學法學工程學如果這名同學只能選擇一個專業(yè),那么他共有多少種選擇呢？,C大學環(huán)境科學地質(zhì)學車輛工程,.,8,探究2：如果完成一件事有三類不同方案,在第1類方案中有m1種不同的方法,在第2類方案中有m2種不同的方法，在第3類方案中有m3種不同的方法,那么完成這件事共有多少種不同的方法？,N=m1+m2+m3,.,9,想一想：如果完成一件事情有n類不同方案，在每一類中都有若干種不同方法，那么應當如何計數(shù)呢？,一般歸納：完成一件事情，有n類方案，在第1類辦法中有種不同的方法，在第2類方案中有種不同的方法在第n類方案中有種不同的方法.那么完成這件事共有種不同的方法.,.,10,1、一件工作可以用2種方法完成，有5人會用第1種方法完成，另有4人會用第2種方法完成，從中選出1人來完成這件工作，不同選法的種數(shù)是.,2、現(xiàn)有高中一年級的學生3名，高中二年級的學生5名，高中三年級的學生4名.從中任選1人參加接待外賓的活動，有多少種不同的選法？,3、用一個大寫英文字母或一個阿拉伯數(shù)字給教室里的座位編號，總共能編出多少種不同的號碼？,練習：,.,11,問題3用前6個大寫英文字母和19九個阿拉伯數(shù)字，以,，,的方式給教室里的座位編號，總共能編出多少個不同的號碼？,問題4某班級有34位男生,15位女生,現(xiàn)要從中選出男生、女生各一名同學參加演講比賽,則共有多少種不同的選法？,探究3：你能說說以上兩個問題的共同特征嗎？,探究4：你能試著解決這兩個問題嗎？,.,12,分步乘法計數(shù)原理,完成一件事需要分二個步驟，在第1步中有m種不同的方法，在第2步中有n種不同的方法.那么完成這件事共有N=mxn種不同的方法.,.,13,如果做一件事情，完成它需要n個步驟，在第一步中有m1種不同的方法，在第二步中有m2種不同的法，在第n步中有mn類不同的方法，那么完成這件事情有N=m1m2m3.mn種不同的方法.,如果做一件事情，完成它需要三個步驟，在第一步中有m1種不同的方法，在第二步中有m2種不同的法，在第三步中有m3類不同的方法，那么完成這件事情有N=m1m2m3種不同的方法.,.,14,分類計數(shù)原理與分步計數(shù)原理有什么異同？,不同點：分類計數(shù)原理與“分類”有關，各種方法相互獨立，用其中任何一種方法都可以完成這件事；分步計數(shù)原理與“分步”有關，各個步驟相互依存，只有各個步驟都完成了，這件事才算完成,相同點：分類計數(shù)原理與分步計數(shù)原理都是涉及完成一件事的不同方法的種數(shù)的問題。,.,15,完成一件事，共有n類辦法，關鍵詞“分類”,區(qū)別1,完成一件事，共分n個步驟，關鍵詞“分步”,區(qū)別2,區(qū)別3,每類辦法都能獨立地完成這件事情，它是獨立的、一次的、且每次得到的是最后結果，只須一種方法就可完成這件事。,每一步得到的只是中間結果，任何一步都不能獨立完成這件事，缺少任何一步也不能完成這件事，只有各個步驟都完成了，才能完成這件事。,各類辦法是互相獨立的。,各步之間是互相關聯(lián)的。,即：類類獨立，步步關聯(lián)。,.,16,例2書架的第1層放有4本不同的計算機書，第2層放有3本不同的文藝書，第3層放有2本不同的體育書（1）從書架上任取1本書，有多少種不同的取法？（2）從書架的第1、2、3層各取1本書，有多少種不同的取法？,.,17,例3.要從甲、乙、丙3幅不同的畫中選出2幅，分別掛在左、右兩邊墻上的指定位置，問共有多少種不同的掛法？,解：第1步：從3幅畫中選1幅掛在左邊墻上，有3種選法第2步：從剩下的2幅畫中選1幅掛在右邊墻上，有2種選法根據(jù)分步乘法計數(shù)原理，不同掛法的種數(shù)是N326,.,18,1、在由電鍵組A、B組成的串聯(lián)電路中，如圖，要接通電源，使電燈發(fā)光的方法有幾種？,練習：,.,19,2、某學校的一個班級組織學生義務獻血，在體檢合格的學生中，是o型血的有10人，A型血的有7人，B型血的有8人，AB型血的有5人，（1）從中任選1名學生去獻血，有多少種不同的選法？,練習：,（2）從四種血型的學生中各選1名學生去獻血，有多少種不同的選法？,（3）從中任選2名具有不同血型的學生去獻血，有多少種不同的選法？,.,20,例4、給程序模塊命名，需要用3個字符，其中首字符要求用字母AG或UZ，后兩個要求用數(shù)字19，問最多可以給多少個程序命名？,解：第1步：選首字符，共有7613種選法第2步：選中間字符，共有9種選法第3步，選最后一個字符，共有9種選法根據(jù)分步計數(shù)原理，最多可以有13991053個不同的名稱,.,21,例5核糖核酸（RNA）分子是在生物細胞中發(fā)現(xiàn)的化學成分，一個RNA分子是一個有著數(shù)百個甚至數(shù)千個位置的長鏈，長鏈中每一個位置上都由一種稱為堿基的化學成分所占據(jù).總共有4種不同的堿基，分別用A，C，G，U表示.在一個RNA分子中，各種堿基能夠以任意次序出現(xiàn)，所以在任意一個位置上的堿基與其他位置上的堿基無關.假設有一類RNA分子由100個堿基組成，那么能有多少個不同的RNA分子？,4100個,.,22,例6電子元件很容易實現(xiàn)電路的通與斷、電位的高與低等兩種狀態(tài)，而這也是最容易控制的兩種狀態(tài).因此計算機內(nèi)部就采用了每一位只有0或1兩種數(shù)字的記數(shù)法，即二進制.為了使計算機能夠識別字符，需要對字符進行編碼，每個字符可以用一個或多個字節(jié)來表示，其中字節(jié)是計算機中數(shù)據(jù)存儲的最小計量單位，每個字節(jié)由8個二進制位構成.問：（1）一個字節(jié)（8位）最多可以表示多少個不同的字符？（2）計算機漢字國際碼（GB碼）包含了6763個漢字，一個漢字為一個字符，要對這些漢字進行編碼，每個漢字至少要用多少個字節(jié)表示？,(1)256個,(2)2個,.,23,例7計算機編程人員在編寫好程序以后需要對程序進行測試，程序員需要知道到底有多少條執(zhí)行路徑（即程序從開始到結束的路線），以便知道需要提供多少個測試數(shù)據(jù).一般地，一個程序模塊由許多子模塊組成.如圖所示是一個具有許多執(zhí)行路徑的程序模塊.（1）這個程序模塊有多少條執(zhí)行路徑；（2）為了減少測試時間，程序員需要設法減少測試次數(shù)，你能幫助程序員設計一個測試方法，以減少測試次數(shù)嗎？,.,24,7371條,178次,.,25,例8隨著人們生活水平的提高，某城市家庭汽車擁有量迅速增長，汽車牌照號碼需要擴容.交通管理部門出臺了一種汽車牌照組成方法，每一個汽車牌照都必須有3個不重復的英文字母和3個不重復的阿拉伯數(shù)字，并且3個字母必須合成一組出現(xiàn)，3個數(shù)字也必須合成一組出現(xiàn).那么這種辦法共能給多少輛汽車上牌照？,共能給22464000輛汽車上牌照.,用兩個計數(shù)原理解決計數(shù)問題時，最重要的是在開始計算之前要進行仔細分析需要分類還是需要分步。,分類要做到“不重不漏”，分步要做到“步驟完整”,.,26,1、要從甲、乙、丙3名工人中選出2名分別上日班和晚班，有多少種不同的選法？,練習：,3、從數(shù)字1、2、3、4、5中任選三個數(shù)字可以組成多少個無重復數(shù)字的三位數(shù)？,2、乘積（a1+a2+a3）（b1+b2+b3+b4）（c1+c2+c3+c4+c5）展開后共有多少項？,4、由數(shù)字0，1，2，3，4，5可以組成多少個有重復數(shù)字的三位數(shù)？,5、個班分別從個風景點中選擇一處游覽，不同選法的種數(shù)是還是？,.,27,7、集合A=1,2,3,4,B=5,6,7,從A到B的映射有多少個？,6、某中學的一幢5層教學樓共有3處樓梯，問從1樓到5樓共有多少種不同的走法？,8、用5種不同顏色給圖中A，B，C，D四個區(qū)域涂色，每個區(qū)域只涂一種顏色，相鄰區(qū)域的顏色不同，求共有多少種不同的涂色方法？,9、如圖，從甲地到乙地有2條路，從乙地到丁地有3條路；從甲地到丙地有4條路可以走，從丙地到丁地有2條路。從甲地到丁地共有多少種不同地走法？,.,28,10、如圖,該電路,從A到B共有多少條不同的線路可通電？,A,B,.,29,11、集合A=1,2,-3,B=-1,-2,3,4從A,B中各取1個元素作為點P(x,y)的坐標（1）可以得到多少個不同的點？（2）這些點中，位于第一象限的有幾個？,13、在所有的兩位數(shù)中，個位數(shù)字比十位數(shù)字大的兩位數(shù)有多少個？,12、甲、乙、丙3個班各有三好學生3，5，2名，現(xiàn)準備推選兩名來自不同班的三好學生去參加校三好學生代表大會，共有幾種不同的推選方法.,14、有架樓梯共6級，每次只允許上一級或兩級，求上完這架樓梯共有多少種不同的走法？,15、某藝術組有9人，每人至少會鋼琴和小號中的一種樂器，其中7人會鋼琴，3人會小號，從中選出會鋼琴與會小號的各1人，有多少種不同的選法？,.,30,16、將一個四棱錐的每個頂點染上一種顏色，并使同一條棱上的兩端點顏色不同，如果只有5種顏色可供使用，求共有多少種不同的染色方法？,.,31,用0，1，2，9可以組成多少個8位號碼；,用0，1，2，9可以組成多少個有兩個重復數(shù)字的4位整數(shù),用0，1，2，9可以組成多少個無重復數(shù)字的4位奇數(shù)；,用0，1，2，9可以組成多少個有重復數(shù)字的4位整數(shù)；,用0，1，2，9可以組成多少個無重復數(shù)字的4位整數(shù)；,用0，1，2，9可以組成多少個8位整數(shù)；,17、,.,32,例5.核糖核酸（RNA）分子是在生物細胞中發(fā)現(xiàn)的化學成分，一個RNA分子是一個有著數(shù)百個甚至數(shù)千個位置的長鏈，長鏈中每一個位置上都由一種稱為堿基的化學成分所占據(jù)，總共有個不同的堿基，分別用A，C，G，U表示，在一個RNA分子中，各種堿基能夠以任意次序出現(xiàn)，所以在任意一個位置上的堿基與其他位置上的堿基無關。假設有一類RNA分子由100個堿基組成，那么能有多少種不同的RNA分子？,分析:用100個位置表示由100個堿基組成的長鏈，每個位置都可以從A、C、G、U中任選一個來占據(jù)。,解：100個堿基組成的長鏈共有100個位置，在每個位置中，從A、C、G、U中任選一個來填入，每個位置有4種填充方法。根據(jù)分步計數(shù)原理，共有,種不同的RNA分子.,.,33,例6.電子元件很容易實現(xiàn)電路的通與斷、電位的高與底等兩種狀態(tài)，而這也是最容易控制的兩種狀態(tài)。因此計算機內(nèi)部就采用了每一位只有0或1兩種數(shù)字的計數(shù)法，即二進制，為了使計算機能夠識別字符，需要對字符進行編碼，每個字符可以用一個或多個字節(jié)來表示，其中字節(jié)是計算機中數(shù)據(jù)存儲的最小計量單位，每個字節(jié)由個二進制位構成，問（1）一個字節(jié)（8位）最多可以表示多少個不同的字符？（2）計算機漢字國標碼（GB碼）包含了6763個漢字，一個漢字為一個字符，要對這些漢字進行編碼，每個漢字至少要用多少個字節(jié)表示？,如00000000，10000000，11111111.,.,34,例7.計算機編程人員在編寫好程序以后要對程序進行測試。程序員需要知道到底有多少條執(zhí)行路（即程序從開始到結束的線），以便知道需要提供多少個測試數(shù)據(jù)。一般的，一個程序模塊又許多子模塊組成，它的一個具有許多執(zhí)行路徑的程序模塊。問：這個程序模塊有多少條執(zhí)行路徑？另外為了減少測試時間，程序員需要設法減少測試次數(shù)，你能幫助程序員設計一個測試方式，以減少測試次數(shù)嗎？,.,35,分析：整個模塊的任意一條路徑都分兩步完成：第1步是從開始執(zhí)行到A點；第2步是從A點執(zhí)行到結束。而第步可由子模塊1或子模塊2或子模塊3來完成