《分类加法与分步乘法计数原理.ppt》由会员分享，可在线阅读，更多相关《分类加法与分步乘法计数原理.ppt（25页珍藏版）》请在三一办公上搜索。
1、济宁育才中学 C123,【分类加法计数原理】,如果完成一件事有n类不同方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，在第n类方案中有mn种不同的方法，那么完成这件事的方法总数为Nm1m2mn,【分步乘法计数原理】,如果完成一件事需要n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事的方法总数为Nm1m2mn,P6例5：给程序模块命名，需要用3个字符，其中首字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少个程序命名？,答:(7+6)9 9=1053,故最多可以给1053个程序命名.,P7例6：核
2、糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据.总共有4种不同的碱基，分别用A，C，G，U表示.在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关.假设有一类RNA分子由100个碱基组成，那么能有多少个不同的RNA分子？,答：4100个。,例补：某4名田径运动员报名参加100m，200m和400m三项短跑比赛.（1）每人限报1个项目，共有多少种不同的报名方法？（2）每个项目限报1人，共有多少种不同的报名方法？,（1）3481种；,（2）4364
3、种.,【跟踪练习】课本P13页B组2T。,P7例7：电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制.为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成.问：（1）一个字节（8位）最多可以表示多少个不同的字符？（2）计算机汉字国际码（GB码）包含了6 763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,2个,P8例8：计算机编程人员在编写好程序以后需要对程序
4、进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.如图所示是一个具有许多执行路径的程序模块.（1）这个程序模块有多少条执行路径；（2）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？,答（1）：7371条,答（2）：178次,p9例9：随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌照组成方法，每一个汽车牌照都必须有3个不重复的英文字母和3个不重复的阿拉伯数字，并且3个字母必须合成一组出现，3个数字
5、也必须合成一组出现.那么这种办法共能给多少辆汽车上牌照？,答：共能给22 464 000辆汽车上牌照.,【跟踪练习】课本P10页练习1、2、3、4,例1：要从甲、乙、丙3名工人中选出2名分别上日班和晚班，有多少种不同的选法？,第一步：选1人上日班；,第二步：选1人上晚班.,有3种方法,有2种方法,N326（种）,例2：由数字0，1，2，3，4，5可以组成多少个无重复数字的三位数？,5种,4种,5种,N554100（种）,例3：从5人中选4人参加数、理、化学科竞赛，其中数学2人，理、化各1人，求共有多少种不同的选法？,5种,4种,3种,N54360（种）,另：也可先从数学入手有10种，答：103
6、 2.,例4：从3，2，1，0，1，2，3中任取三个不同的数作为抛物线y=ax2+bx+c(a0)的系数，如果抛物线过原点，且顶点在第一象限，问这样的抛物线共有多少条？,c取值a取值b取值,故N3319（种）,c0 a0 b0,分析：,故N5433180（种）,5,4,3,3,例5：用5种不同颜色给图中A，B，C，D四个区域涂色，每个区域只涂一种颜色，相邻区域的颜色不同，求共有多少种不同的涂色方法？,涂色问题：,解:按地图A、B、C、D四个区域依次分四步完成,第一步,m1=3 种,第二步,m2=2 种,第三步,m3=1 种,第四步,m4=1 种,故有根据乘法原理,得到不同的涂色方案种数共有 N
7、=3 2 11=6 种。,如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?,练习1.,课堂练习：,问:若用2色、4色、5色等,结果又怎样呢?,答:它们的涂色方案种数分别是：0；4322=48；5433=180 种。,如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?,变练：,*例6：在1，2，3，200这些自然数中，各个数位上都不含数字8的自然数共有多少个？,不含8的一位数不含8的二位数不含8的三位数,N8
8、7282162（个）,？,分析：,详解析：由题意分三类解决.第一类：一位数中有8个大于0且不含数字8的自然数.第二类：两位数中有多少不含数字8的自然数，此类需要分两步，第一步：个位上除8之外有9种选法，第二步：十位数上除0和8之外有8种选法，要根据分步计数原理，得第二类数中有89=72(个)数符合要求.第三类：三位数中有多少不含数字8的自然数，此类需要分两个小类，一类是百位数为1的三位数，此类需分三步，第一步：百位数为1，有1种选法.第二步：十位数上除8之外有9种选法；第三步：个位上除8之外有9种选法；.根据分步计数原理，得此类数中有991=81(个)数符合要求.另一类是百位数为2的三位数，即
9、200，就是1个。由分类计数原理得此时第三类的三位数中有81+1=82(个)不含数字8的自然数.即先用分类计数原理再结合分步计数原理。综上得从1到200的自然数中各个数位上都不含数字8的自然数有N=8+72+82=162(个).,课下讨论：,某艺术组有9人，每人至少会钢琴和小号中一种乐器，其中7人会钢琴，3人会小号，从中选出会钢琴与会小号的各1人，有多少种不同的选法？,解：由题意可知，在艺术组9人中，有且仅有一人既会钢琴又会小号，只会钢琴的有6人，只会小号的有2人，把会钢琴、小号各1人的选法分为两类：,第一类：多面手入选，另一人只需从其他8人中任选一个，故这类选法共有8种,第二类：多面手不入选
10、，则会钢琴者只能从6个只会钢琴的人中选出，会小号的1人也只能从只会小号的 2人中选出，故这类选法共有6212种，,加法原理和乘法原理的共同点是什么？不同点什么？,小结与作业：,何时用加法原理、乘法原理呢?,加法原理,完成一件事情有n类方法,若每一类方法中的任何一种方法均能将这件事情从头至尾完成.,乘法原理,完成一件事情有n个步骤,若每一步的任何一种方法只能完成这件事的一部分,并且必须且只需完成互相独立的这n步后,才能完成这件事.,分类要做到“不重不漏”,分步要做到“步骤完整”,联系,区别一,完成一件事情共有n类办法，关键词是“分类”,完成一件事情,共分n个步骤，关键词是“分步”,区别二,每类办法都能独立完成这件事情。,每一步得到的只是中间结果，任何一步都不能能独立完成这件事情，缺少任何一步也不能完成这件事情，只有每个步骤完成了，才能完成这件事情。,分类计数原理和分步计数原理，回答的都是关于完成一件事情的不同方法的种数的问题。,区别三,各类办法是互斥的、并列的、独立的,各步之间是相关联的,分类计数与分步计数原理的区别和联系：,作业：,1.P12习题1.1A组：15.2.书练习及习题；预习并完成三维。,
