类加法和分步乘.ppt

《类加法和分步乘.ppt》由会员分享，可在线阅读，更多相关《类加法和分步乘.ppt（36页珍藏版）》请在三一办公上搜索。

1、1.1 分类加法计数原理与分步乘法计数原理,计数原理,2008年29届夏季奥运会在北京举行奥运会足球赛共有个队参赛它们先分成个小组进行循环赛，决出强，这个队按确定的程序进行淘汰赛后，最后决出冠亚军，此外还决出了第三、第四名问一共安排了多少场比赛？,实际问题,要回答这个问题，就要用到排列、组合的知识在运用排列、组合方法时，经常要用到分类加法计数原理与分步乘法计数原理,问题2 秋天到了，学校举行“全民健身”登山活动,山的南面有3条登山路线,山的北面有2条登山路线,要登上山顶,问共有多少种不同的路线？,问题1 某班级有34位男生,15位女生,现要选一位同学参加演讲比赛,则有多少种不同的选法？,探究1

2、：你能说说以上两个问题的共同特征吗？,分类加法计数原理,完成一件事有两类不同方案，在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法.那么完成这件事共有 N=m+n种不同的方法.,问题2 秋天到了，学校举行“全民健身”登山活动,山的南面有3条登山路线,山的北面有2条登山路线,要登上山顶,问共有多少种不同的路线？,问题1 我们班级有34位男生,15位女生,现要选一位同学参加演讲比赛,则有多少种不同的选法？,在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法.那么完成这件事共有 N=m+n种不同的方法.,完成一件事,有两类不同方案,例1：在填写高考志愿表时,一名高中毕业生了

3、解到,A,B两所大学各有一些自己感兴趣的强项专业，具体情况如下：A大学 B大学 生物学 数学 化学 会计学 医学 信息技术学 物理学 法学 工程学如果这名同学只能选择一个专业,那么他共有多少种选择呢？,想一想 在填写高考志愿表时,一名高中毕业生了解到,A,B,C三所大学各有一些自己感兴趣的强项专业，具体情况如下：A大学 B大学 生物学 数学 化学 会计学 医学 信息技术学 物理学 法学 工程学如果这名同学只能选择一个专业,那么他共有多少种选择呢？,C大学环境科学地质学车辆工程,探究2：如果完成一件事有三类不同方案,在第1类方案中有m1种不同的方法,在第2类方案中有m2种不同的方法，在第3类方案

4、中有m3种不同的方法,那么完成这件事共有多少种不同的方法？,N=m1+m2+m3,想一想：如果完成一件事情有n类不同方案，在每一类中都有若干种不同方法，那么应当如何计数呢？,一般归纳：完成一件事情，有n类方案，在第1类办法中有 种不同的方法，在第2类方案中有 种不同的方法在第n类方案中有 种不同的方法.那么完成这件事共有 种不同的方法.,1、一件工作可以用2种方法完成，有5人会用第1种方法完成，另有4人会用第2种方法完成，从中选出1人来完成这件工作，不同选法的种数是.,2、现有高中一年级的学生3名，高中二年级的学生5名，高中三年级的学生4名.从中任选1人参加接待外宾的活动，有多少种不同的选法？

5、,3、用一个大写英文字母或一个阿拉伯数字给教室里的座位编号，总共能编出多少种不同的号码？,练习：,问题3 用前6个大写英文字母和19九个阿拉伯数字，以,，,的方式给教室里的座位编号，总共能编出多少个不同的号码？,问题4 某班级有34位男生,15位女生,现要从中选出男生、女生各一名同学参加演讲比赛,则共有多少种不同的选法？,探究3：你能说说以上两个问题的共同特征吗？,探究4：你能试着解决这两个问题吗？,分步乘法计数原理,完成一件事需要分二个步骤，在第1步中有m种不同的方法，在第2步中有n种不同的方法.那么完成这件事共有 N=mxn 种不同的方法.,如果做一件事情，完成它需要n个步骤，在第一步中有

6、m1种不同的方法，在第二步中有m2种不同的法，在第n步中有mn类不同的方法，那么完成这件事情有 N=m1m2m3.mn种不同的方法.,如果做一件事情，完成它需要三个步骤，在第一步中有m1种不同的方法，在第二步中有m2种不同的法，在第三步中有m3类不同的方法，那么完成这件事情有 N=m1m2m3种不同的方法.,分类计数原理与分步计数原理有什么异同？,不同点：分类计数原理与“分类”有关，各种方法相互独立，用其中任何一种方法都可以完成这件事；分步计数原理与“分步”有关，各个步骤相互依存，只有各个步骤都完成了，这件事才算完成,相同点：分类计数原理与分步计数原理都是涉及完成一件事的不同方法的种数的问题。

7、,完成一件事，共有n类办法，关键词“分类”,区别1,完成一件事，共分n个步骤，关键词“分步”,区别2,区别3,每类办法都能独立地完成这件事情，它是独立的、一次的、且每次得到的是最后结果，只须一种方法就可完成这件事。,每一步得到的只是中间结果，任何一步都不能独立完成这件事，缺少任何一步也不能完成这件事，只有各个步骤都完成了，才能完成这件事。,各类办法是互相独立的。,各步之间是互相关联的。,即：类类独立，步步关联。,例2 书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放有2本不同的体育书（1）从书架上任取1本书，有多少种不同的取法？（2）从书架的第1、2、3层各取1本书，有

8、多少种不同的取法？,例3.要从甲、乙、丙3幅不同的画中选出2幅，分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法？,解：第1步：从3幅画中选1幅挂在左边墙上，有3种选法第2步：从剩下的2幅画中选1幅挂在右边墙上，有2种选法根据分步乘法计数原理，不同挂法的种数是N326,1、在由电键组A、B组成的串联电路中，如图，要接通电源，使电灯发光的方法有几种？,练习：,2、某学校的一个班级组织学生义务献血，在体检合格的学生中，是o型血的有10人，A型血的有7人，B型血的有8人，AB型血的有5人，（1）从中任选1名学生去献血，有多少种不同的选法？,练习：,（2）从四种血型的学生中各选1名学生去献血，

9、有多少种不同的选法？,（3）从中任选2名具有不同血型的学生去献血，有多少种不同的选法？,例4、给程序模块命名，需要用3个字符，其中首字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少个程序命名？,解：第1步：选首字符，共有7613种选法第2步：选中间字符，共有9种选法第3步，选最后一个字符，共有9种选法根据分步计数原理，最多可以有13991053个不同的名称,例5 核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据.总共有4种不同的碱基，分别用A，C，G，U表示.在一个RNA分

10、子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关.假设有一类RNA分子由100个碱基组成，那么能有多少个不同的RNA分子？,4100个,例6 电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制.为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成.问：（1）一个字节（8位）最多可以表示多少个不同的字符？（2）计算机汉字国际码（GB码）包含了6 763个汉字，一个汉字

11、为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,(1)256个,(2)2个,例7 计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.如图所示是一个具有许多执行路径的程序模块.（1）这个程序模块有多少条执行路径；（2）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？,7371条,178次,例8 随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌

12、照组成方法，每一个汽车牌照都必须有3个不重复的英文字母和3个不重复的阿拉伯数字，并且3个字母必须合成一组出现，3个数字也必须合成一组出现.那么这种办法共能给多少辆汽车上牌照？,共能给22 464 000辆汽车上牌照.,用两个计数原理解决计数问题时，最重要的是在开始计算之前要进行仔细分析需要分类还是需要分步。,分类要做到“不重不漏”，分步要做到“步骤完整”,1、要从甲、乙、丙3名工人中选出2名分别上日班和晚班，有多少种不同的选法？,练习：,3、从数字1、2、3、4、5中任选三个数字可以组成多少个无重复数字的三位数？,2、乘积（a1+a2+a3）（b1+b2+b3+b4）（c1+c2+c3+c4+

13、c5）展开后共有多少项？,4、由数字0，1，2，3，4，5可以组成多少个有重复数字的三位数？,5、个班分别从个风景点中选择一处游览，不同选法的种数是还是？,7、集合A=1,2,3,4,B=5,6,7,从A到B的映射有多少个？,6、某中学的一幢5层教学楼共有3处楼梯，问从1楼到5楼共有多少种不同的走法？,8、用5种不同颜色给图中A，B，C，D四个区域涂色，每个区域只涂一种颜色，相邻区域的颜色不同，求共有多少种不同的涂色方法？,9、如图，从甲地到乙地有2条路，从乙地到丁地有3条路；从甲地到丙地有4条路可以走，从丙地到丁地有2条路。从甲地到丁地共有多少种不同地走法？,10、如图,该电路,从A到B共有

14、多少条不同的线路可通电？,A,B,11、集合A=1,2,-3,B=-1,-2,3,4 从A,B 中各取1个元素作为点P(x,y)的坐标（1）可以得到多少个不同的点？（2）这些点中，位于第一象限的有几个？,13、在所有的两位数中，个位数字比十位数字大的两位数有多少个？,12、甲、乙、丙3个班各有三好学生3，5，2名，现准备推选两名来自不同班的三好学生去参加校三好学生代表大会，共有几种不同的推选方法.,14、有架楼梯共6级，每次只允许上一级或两级，求上完这架楼梯共有多少种不同的走法？,15、某艺术组有9人，每人至少会钢琴和小号中的一种乐器，其中7人会钢琴，3人会小号，从中选出会钢琴与会小号的各1人

15、，有多少种不同的选法？,16、将一个四棱锥的每个顶点染上一种颜色，并使同一条棱上的两端点颜色不同，如果只有5种颜色可供使用，求共有多少种不同的染色方法？,用0，1，2，9可以组成多少个8位号码；,用0，1，2，9可以组成多少个有两个重复数字的4位整数,用0，1，2，9可以组成多少个无重复数字的4位奇数；,用0，1，2，9可以组成多少个有重复数字的4位整数；,用0，1，2，9可以组成多少个无重复数字的4位整数；,用0，1，2，9可以组成多少个8位整数；,17、,例5.核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种

16、称为碱基的化学成分所占据，总共有个不同的碱基，分别用A，C，G，U表示，在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由100个碱基组成，那么能有多少种不同的RNA分子？,分析:用100个位置表示由100个碱基组成的长链，每个位置都可以从A、C、G、U中任选一个来占据。,解：100个碱基组成的长链共有100个位置，在每个位置中，从A、C、G、U中任选一个来填入，每个位置有4种填充方法。根据分步计数原理，共有,种不同的RNA分子.,例6.电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因

17、此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问（1）一个字节（8位）最多可以表示多少个不同的字符？（2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,如00000000，10000000，11111111.,例7.计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据

18、。一般的，一个程序模块又许多子模块组成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？,分析：整个模块的任意一条路径都分两步完成：第1步是从开始执行到A点；第2步是从A点执行到结束。而第步可由子模块1或子模块2或子模块3来完成；第二步可由子模块4或子模块5来完成。因此，分析一条指令在整个模块的执行路径需要用到两个计数原理。,再测试各个模块之间的信息交流是否正常，需要测试的次数为：3*2=6。如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就正常。,这样，测试整个模块的次数就变为 172+6=178（次）,2）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块。这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常。总共需要的测试次数为：,18+45+28+38+43=172。,