分类加法与分步乘法计数原理.ppt

《分类加法与分步乘法计数原理.ppt》由会员分享，可在线阅读，更多相关《分类加法与分步乘法计数原理.ppt（25页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、济宁育才中学济宁育才中学 C123【分类加法计数原理分类加法计数原理】如果完成一件事有如果完成一件事有n n类不同方案，在第类不同方案，在第1 1类方案中有类方案中有m1 1种不同的方法，在第种不同的方法，在第2 2类方案中有类方案中有m2 2种不同的方法，种不同的方法，在，在第第n n类方案中有类方案中有mn n种不同的方法，那么种不同的方法，那么完成这件事的方法总数为完成这件事的方法总数为N Nm1 1m2 2mn n【分步乘法计数原理分步乘法计数原理】如果完成一件事需要如果完成一件事需要n n个步骤，做第个步骤，做第1 1步有步有m1 1种不同的方法，做第种不同的方法，做第2 2步有步有

2、m2 2种不同的方法，种不同的方法，做第，做第n n步有步有mn n种种不同的方法，那么完成这件事的方法不同的方法，那么完成这件事的方法总数为总数为N Nm1 1m2 2mn nP P6 6例例5 5：给程序模块命名，需要用：给程序模块命名，需要用3 3个字符，个字符，其中首字符要求用字母其中首字符要求用字母A AG G或或U UZ Z，后两，后两个要求用数字个要求用数字1 19 9，问，问最多最多可以给可以给多少个程序命名？多少个程序命名？答答:(7:(7+6)+6)9 9=1053,故最多可以给故最多可以给10531053个程序命名个程序命名.P P7 7例例6 6：核糖核酸（：核糖核酸（

3、RNARNA）分子是在生物细胞）分子是在生物细胞中发现的化学成分，一个中发现的化学成分，一个RNARNA分子是一个有着分子是一个有着数百个甚至数千个位置的长链，长链中每一数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占个位置上都由一种称为碱基的化学成分所占据据.总共有总共有4 4种不同的碱基，分别用种不同的碱基，分别用A A，C C，G G，U U表示表示.在一个在一个RNARNA分子中，各种碱基能够以任分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关与其他位置上的碱基无关.假设有一类假设有一

4、类RNARNA分分子由子由100100个碱基组成，那么能有多少个不同的个碱基组成，那么能有多少个不同的RNARNA分子？分子？A AG GC CU UA AA AA AU U G GG GC CC C答：答：4 4100100个。个。例补：例补：某某4 4名名田径运动员报名参加田径运动员报名参加100m100m，200m200m和和400m400m三项三项短跑比赛短跑比赛.（1 1）每人限报）每人限报1 1个项目，共有多少种不同的报名方个项目，共有多少种不同的报名方法？法？（2 2）每个项目限报）每个项目限报1 1人，共有多少种不同的报名方人，共有多少种不同的报名方法？法？（1 1）3 34

5、48181种；种；（2 2）4 43 36464种种.【跟踪练习跟踪练习】课本课本P13页页B组组2T。P7例例7 7：电子元件很容易实现电路的通与断、电位：电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种的高与低等两种状态，而这也是最容易控制的两种状态状态.因此计算机内部就采用了每一位只有因此计算机内部就采用了每一位只有0 0或或1 1两两种数字的记数法，即二进制种数字的记数法，即二进制.为了使计算机能够识为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存个或多

6、个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由储的最小计量单位，每个字节由8 8个二进制位构成个二进制位构成.问：问：（1 1）一个字节（）一个字节（8 8位）最多可以表示多少个不同的位）最多可以表示多少个不同的字符？字符？（2 2）计算机汉字国际码（）计算机汉字国际码（GBGB码）包含了码）包含了6 7636 763个汉个汉字，一个汉字为一个字符，要对这些汉字进行编码，字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？每个汉字至少要用多少个字节表示？2 2个个 P P8 8例例8 8：计算机编程人员在编写好程序以后：计算机编程人员在编写好程序以

7、后需要对程序进行测试，程序员需要知道到底需要对程序进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的有多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据路线），以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成一般地，一个程序模块由许多子模块组成.如如图所示图所示是一个具有许多执行路径的程序模块是一个具有许多执行路径的程序模块.（1 1）这个程序模块有多少条执行路径；）这个程序模块有多少条执行路径；（2 2）为了减少测试时间，程序员需要设法减）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试少测试次数，你能帮助程

8、序员设计一个测试方法，以减少测试次数吗？方法，以减少测试次数吗？开始开始子模块子模块1 11818条执行路径条执行路径子模块子模块5 54343条执行路径条执行路径子模块子模块4 43838条执行路径条执行路径子模块子模块3 32828条执行路径条执行路径子模块子模块2 24545条执行路径条执行路径结束结束A A答（答（1 1）：）：73717371条条答（答（2）：178178次次p p9 9例例9 9：随着人们生活水平的提高，某城市家庭随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容汽车拥有量迅速增长，汽车牌照号码需要扩容.交交通管理部门出台了一种汽车牌照组成方

9、法，每一个通管理部门出台了一种汽车牌照组成方法，每一个汽车牌照都必须有汽车牌照都必须有3 3个不重复的英文字母和个不重复的英文字母和3 3个不重个不重复的阿拉伯数字，并且复的阿拉伯数字，并且3 3个字母必须合成一组出现，个字母必须合成一组出现，3 3个数字也必须合成一组出现个数字也必须合成一组出现.那么这种办法共能给那么这种办法共能给多少辆汽车上牌照？多少辆汽车上牌照？答：共能给答：共能给22 464 00022 464 000辆汽车上牌照辆汽车上牌照.【跟踪练习跟踪练习】课本课本P10页练习页练习1、2、3、4例例1 1：要从甲、乙、丙：要从甲、乙、丙3 3名工人中选出名工人中选出2 2名分

10、别上日班和晚班，有多少种不同的名分别上日班和晚班，有多少种不同的选法？选法？第一步第一步：选：选1 1人上日班；人上日班；第二步：第二步：选选1 1人上晚班人上晚班.有有3 3种方法种方法有有2 2种方法种方法N N3 32 26 6（种）（种）例例2 2：由数字由数字0 0，1 1，2 2，3 3，4 4，5 5可以可以组成多少个组成多少个无重复无重复数字的数字的三位数三位数？百位百位 十位十位 个位个位5 5种种4 4种种5 5种种N N5 55 54 4100100（种）（种）例例3 3：从：从5 5人中选人中选4 4人参加数、理、化人参加数、理、化学科竞赛，其中数学学科竞赛，其中数学2

11、 2人，理、化各人，理、化各1 1人，求共有多少种不同的选法？人，求共有多少种不同的选法？数学数学2 2人人化学化学1 1人人物理物理1 1人人5 5种种4 4种种3 3种种N N5 54 43 36060（种）（种）另：也可先从数学入手有另：也可先从数学入手有10种，答：种，答：103 2.例例4 4：从从3 3，2 2，1 1，0 0，1 1，2 2，3 3中任取三个不同的数作为抛物线中任取三个不同的数作为抛物线y=y=ax x2 2+bx+x+c(a0)0)的系数，如果抛物的系数，如果抛物线线过原点过原点，且顶点在，且顶点在第一象限第一象限，问这，问这样的抛物线共有多少条？样的抛物线共有

12、多少条？c取值取值a取值取值b取值取值1 1种种3 3种种3 3种种故故N N3 33 31 19 9（种）（种）c c0 0 a a0 0 b b0 0故故N N5 54 43 33 3180180（种）（种）5 54 43 33 3例例5 5：用：用5 5种不同颜色给图中种不同颜色给图中A A，B B，C C，D D四个区域涂色，每个区域只涂一四个区域涂色，每个区域只涂一种颜色，相邻区域的颜色不同，求共种颜色，相邻区域的颜色不同，求共有多少种不同的涂色方法？有多少种不同的涂色方法？A AD DC CB B解解:按地图按地图A、B、C、D四个区域依次分四步四个区域依次分四步完成完成,第一步第

13、一步,m1=3 种种,第二步第二步,m2=2 种种,第三步第三步,m3=1 种种,第四步第四步,m4=1 种种,故有根据乘法原理故有根据乘法原理,得到不同的涂色方案种数得到不同的涂色方案种数共有共有 N=3 2 11=6 种。种。如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?练习1.课堂练习：课堂练习：问问:若用若用2色、色、4色、色、5色等色等,结果又怎样呢结果又怎样呢?答答:它们的涂色方案种数它们的涂色方案种数分别是：分别是：0；4322=48；5433=180 种。种。如图,要给地图A、B、

14、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?变练：*例例6 6：在：在1 1，2 2，3 3，200200这些自然数这些自然数中，各个数位上都不含数字中，各个数位上都不含数字8 8的自然数共的自然数共有多少个？有多少个？不含不含8 8的一位数的一位数不含不含8 8的二位数的二位数不含不含8 8的三位数的三位数8 8个个8 89=729=72个个9 99+1=829+1=82个个N N8 872728282162162（个）（个）详解析：由题意分三类解决由题意分三类解决.第一类：第一类：一位数中有一位数中有8个大于个大

15、于0且不含数字且不含数字8的自然数的自然数.第二类第二类：两位数中有多少不含数字：两位数中有多少不含数字8的自然数，的自然数，此类需要分两步，此类需要分两步，第一步第一步：个位上除：个位上除8之外有之外有9种选法，种选法，第二步第二步：十位数上除：十位数上除0和和8之外有之外有8种选法，要根据分步计数原理，种选法，要根据分步计数原理，得第二类数中有得第二类数中有89=72(个个)数符合要求数符合要求.第三类：第三类：三位数中有多少不含数字三位数中有多少不含数字8的自然数，的自然数，此类需要分两个小类，此类需要分两个小类，一类是百位数为一类是百位数为1的三位数，的三位数，此类需分三步，此类需分三

16、步，第一步第一步：百位数为：百位数为1，有，有1种选法种选法.第二步第二步：十位数上除：十位数上除8之外有之外有9种选法；种选法；第三步第三步：个位上除：个位上除8之外有之外有9种选法；种选法；.根据分步计数原理，得此类数中有根据分步计数原理，得此类数中有991=81(个个)数符合要求数符合要求.另一类是百位数为另一类是百位数为2的三位数，的三位数，即即200，就是，就是1个。个。由分类计数原理得此时第三类的三位数中有由分类计数原理得此时第三类的三位数中有81+1=82(个个)不含数字不含数字8的自然数的自然数.即先用分类计数原理再结合分步计数原理。即先用分类计数原理再结合分步计数原理。综上得

17、从综上得从1到到200的自然数中各个数位上都不含数字的自然数中各个数位上都不含数字8的自然数的自然数有有N=8+72+82=162(个个).课下讨论：课下讨论：某艺术组有某艺术组有9人，每人至少会钢琴和小号中一种人，每人至少会钢琴和小号中一种乐器，其中乐器，其中7人会钢琴，人会钢琴，3人会小号，从中选出会人会小号，从中选出会钢琴与会小号的各钢琴与会小号的各1人，有多少种不同的选法？人，有多少种不同的选法？解：由题意可知，在艺术组9人中，有且仅有一人既会钢琴又会小号，只会钢琴的有6人，只会小号的有2人，把会钢琴、小号各1人的选法分为两类：第一类：多面手入选，另一人只需从其他8人中任选一个，故这类

18、选法共有8 8种第二类第二类：多面手不入选，则会钢琴者只能从多面手不入选，则会钢琴者只能从6个只会钢个只会钢琴的人中选出，会小号的琴的人中选出，会小号的1人也只能从只会小号的人也只能从只会小号的 2人人中选出，中选出，故这类选法共有故这类选法共有6212种，种，加法原理加法原理和和乘法原理乘法原理的共同点是什么？不同点的共同点是什么？不同点什么？什么？加法原理乘法原理相同点它们都是研究完成一件事情它们都是研究完成一件事情,共有多少种不共有多少种不同的方法同的方法不不 同同 点点方式的不同方式的不同分类完成分类完成分类完成分类完成任何一类办法中的任任何一类办法中的任何一个方法都能完成何一个方法都

19、能完成这件事这件事分步完成分步完成分步完成分步完成这些方法需要分步这些方法需要分步,各各个步骤顺次相依个步骤顺次相依,且每且每一步都完成了一步都完成了,才能完才能完成这件事情成这件事情小结与作业：小结与作业：何时用加法原理、乘法原理呢?加法原理 完成一件事情有n类方法,若每一类方法中的任何一种方法均能将这件事情从头至尾完成.乘法原理 完成一件事情有n个步骤,若每一步的任何一种方法只能完成这件事的一部分,并且必须且只需完成互相独立的这n步后,才能完成这件事.分类要做到“不重不漏”分步要做到“步骤完整”加法原理加法原理 乘法原理乘法原理联系联系区别一区别一完成一件事情共有n类办法，关键词是“分类”完成一件事情,共分n个步骤，关键词是“分步”区别二区别二每类办法都能独立完成这件事情。每一步得到的只是中间结果，任何一步都不能能独立完成这件事情，缺少任何一步也不能完成这件事情，只有每个步骤完成了，才能完成这件事情。分类计数原理和分步计数原理，回答的都是关于完成一件事情的不同方法的种数的问题。区别三区别三各类办法是互斥的、并列的、独立的各步之间是相关联的分类计数与分步计数原理的区别和联系：作业：作业：1.P12习题习题1.1A组：组：15.2.书练习及习题；预习并完成三维。书练习及习题；预习并完成三维。