分类加法计数原理与分步乘法计数原理优秀课件20.ppt

1、分类计数原理与分步计数原理分类计数原理与分步计数原理思考思考？用一个大写的的英文字母用一个大写的的英文字母或或一个阿拉伯一个阿拉伯数字给教室里的座位编号，总共能够编出多数字给教室里的座位编号，总共能够编出多少种不同的号码？少种不同的号码？26+10=36问题问题 1.从甲地到乙地，可以乘火车，也从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中，火可以乘汽车，还可以乘轮船。一天中，火车有车有4 班班,汽车有汽车有2班，轮船有班，轮船有3班。那么一班。那么一天中乘坐这些交通工具从甲地到乙地共有天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法多少种不同的走法?分析分析:从甲地到乙地有

2、从甲地到乙地有3类方法类方法,第一类方法第一类方法,乘火车，有乘火车，有4种方法种方法;第二类方法第二类方法,乘汽车，有乘汽车，有2种方法种方法;第三类方法第三类方法,乘轮船乘轮船,有有3种方法种方法;所以所以 从甲地到乙地共有从甲地到乙地共有 4+2+3=9 种方法。种方法。完成一件事，有完成一件事，有n类办法类办法.在第在第1类办法中有类办法中有m1种不同的方法，在第种不同的方法，在第2类方法中有类方法中有m2种不同的种不同的方法，方法，在第，在第n类方法中有类方法中有mn种不同的方法，种不同的方法，则完成这件事共有则完成这件事共有 2）首先要根据具体的问题确定一个分类标准，在分）首先要根

3、据具体的问题确定一个分类标准，在分类标准下进行分类，然后对每类方法计数类标准下进行分类，然后对每类方法计数.1）各类办法之间相互独立）各类办法之间相互独立,都能独立的完成这件事，要都能独立的完成这件事，要计算方法种数计算方法种数,只需将各类方法数相加只需将各类方法数相加,因此分类计数原因此分类计数原理又称理又称加法原理加法原理N=m1+m2+mn 种不同的方法种不同的方法1在填写高考志愿表时，一名高中毕业生了解到在填写高考志愿表时，一名高中毕业生了解到A、B两所两所大学各有一些自己感兴趣的强项专业，具体情况如下：大学各有一些自己感兴趣的强项专业，具体情况如下：A大学大学B大学大学生物学生物学化

4、学化学医学医学物理学物理学工程学工程学数学数学会计学会计学信息技术学信息技术学法学法学如果这名同学只能选一个专业，那么他共有多少种选择呢？如果这名同学只能选一个专业，那么他共有多少种选择呢？解：这名同学在解：这名同学在A大学中有大学中有5种专业选择，在种专业选择，在B大学中有大学中有4种专业选择。种专业选择。根据分类计数原理：这名同学可能的专业选择共有根据分类计数原理：这名同学可能的专业选择共有5+49种。种。用前用前6 6个大写英文字母和个大写英文字母和1 19 9九个阿九个阿拉伯数字，以拉伯数字，以A A1 1，A A2 2，B B1 1，B B2 2，的的方式给教室里的座位编号，总共能编

5、出方式给教室里的座位编号，总共能编出多少个不同的号码？多少个不同的号码？思考思考？分析分析:由于前由于前6 6个英文字母中的任意一个都能个英文字母中的任意一个都能与与9 9个数字中的任何一个组成一个号码，而且个数字中的任何一个组成一个号码，而且它们各个不同，因此共有它们各个不同，因此共有6 69 95454个不同的个不同的号码。号码。字母字母数字数字得到的号码得到的号码A A123456789A1A2A3A4A5A6A7A8A9树形图树形图问题问题 2.如图如图,由由A村去村去B村的道路有村的道路有3条，条，由由B村去村去C村的道路有村的道路有2条。从条。从A村经村经B村去村去C村，共有多少种

6、不同的走法村，共有多少种不同的走法?A村村B村村C村村北北南南中中北北南南 分析分析:从从A村经村经 B村去村去C村有村有2步步,第一步第一步,由由A村去村去B村有村有3种方法种方法,第二步第二步,由由B村去村去C村有村有3种方法种方法,所以所以 从从A村经村经 B村去村去C村共有村共有 3 2=6 种种不同的方法。不同的方法。完成一件事，需要分成完成一件事，需要分成n个步骤。做第个步骤。做第1步有步有m1种不同的方法，做第种不同的方法，做第2步有步有m2种不同的方法，种不同的方法，做第做第n步有步有mn种不同的方法，则完成这件事共有种不同的方法，则完成这件事共有 2）首先要根据具体问题的特点

7、确定一个分步的标准，）首先要根据具体问题的特点确定一个分步的标准，然后对每步方法计数然后对每步方法计数.1）各个步骤相互依存）各个步骤相互依存,只有各个步骤都完成了只有各个步骤都完成了,这件事这件事才算完成才算完成,将各个步骤的方法数相乘得到完成这件事的将各个步骤的方法数相乘得到完成这件事的方法总数方法总数,又称又称乘法原理乘法原理N=m1m2 mn种不同的方法种不同的方法 如果完成一件事需要三个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法,做第3步有m3种不同的方法,那么完成这件事共有_种不同的方法.N=m1m2m3做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方

8、法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有_种不同的方法.N=m1m2mn 2、设某班有男生设某班有男生30名，女生名，女生24名。现要从中选出男、名。现要从中选出男、女生各一名代表班级参加比赛，共有多少种不同的女生各一名代表班级参加比赛，共有多少种不同的选法？选法？例例3、浦江县的部分电话号码是浦江县的部分电话号码是05798415,后后面每个数字来自面每个数字来自09这这10个数个数,问可以产生多少个不同问可以产生多少个不同的电话号码的电话号码?变式变式:若要求最后若要求最后4个数字不重复个数字不重复,则又有多少种不同则又有多少种不同的电话号码的电话号码?

9、0579841510 10 10 10=104分析分析:分析分析:=504010 9873、书架上第书架上第1层放有层放有4本不同的计算机书本不同的计算机书,第第 2层放有层放有3本不同的文艺书本不同的文艺书,第第3层放有层放有2本不同的本不同的体育杂志体育杂志.(2)从书架的第从书架的第1、2、3层各取层各取1本书本书,有多少种有多少种 不同取法不同取法?N43+29 N4 3224(1)从书架上任取从书架上任取1本书本书,有多少种不同的取法有多少种不同的取法?4、要从甲、乙、丙要从甲、乙、丙3幅不同的画中选出幅不同的画中选出2幅，幅，分别挂在左右两边墙上的指定位置，问共有多分别挂在左右两边

10、墙上的指定位置，问共有多少种不同的挂法？少种不同的挂法？1、在所有的两位数中，个位数字比十位数、在所有的两位数中，个位数字比十位数字大的两位数有多少个？字大的两位数有多少个？2、8本不同的书，任选本不同的书，任选3本分给本分给3个同学，每个同学，每人人1本，有多少种不同的分法？本，有多少种不同的分法？3、将、将4封信投入封信投入3个不同的邮筒，有多少种不个不同的邮筒，有多少种不同的投法？同的投法？4、已知、已知则方程则方程 可表示不同的圆的可表示不同的圆的个数有多少？个数有多少？3,4,6,1,2,7,8,8,9abr222()()xaybr5、已知二次函数、已知二次函数 若若 则可以得到多少

11、个则可以得到多少个不同的二次函数？其中图象过原点的二次函不同的二次函数？其中图象过原点的二次函数有多少个？图象过原点且顶点在第一象限数有多少个？图象过原点且顶点在第一象限的二次函数又有多少个？的二次函数又有多少个？2.yaxbxc,3,2,0,1,2,3.a b c 分类计数原理与分步计数原理有什么不同？分类计数原理与分步计数原理有什么不同？分类计数原理与分步计数原理都是涉及完成一件事的不分类计数原理与分步计数原理都是涉及完成一件事的不同方法的种数的问题，它们的区别在于：同方法的种数的问题，它们的区别在于：分类计数原理与分类计数原理与“分类分类”有关，各种方法有关，各种方法相互独立相互独立，用

12、用其中任何一种方法都可以完成这件事；其中任何一种方法都可以完成这件事；分步计数原理与分步计数原理与“分步分步”有关，各个步骤有关，各个步骤相互依存相互依存，只只有各个步骤都完成了，这件事才算完成有各个步骤都完成了，这件事才算完成分步乘法分步乘法 分类加法分类加法共同点共同点区别一区别一完成一件事情共有完成一件事情共有n类类方案。方案。完成一件事情完成一件事情,共分共分n个个步骤。步骤。区别二区别二每类中的任一种方法都每类中的任一种方法都能能独立完成独立完成这件事情。这件事情。每步要而且只要拿出一种方法每步要而且只要拿出一种方法就可以完成一件事情。就可以完成一件事情。都是要解决完成一件事情的方法

13、种数的问题。都是要解决完成一件事情的方法种数的问题。分类加法与分步乘法计数原理的区别和联系：分类加法与分步乘法计数原理的区别和联系：加法原理加法原理 乘法原理乘法原理联系联系区别一区别一完成一件事情共有完成一件事情共有n类类办法，关键词是办法，关键词是“分类分类”完成一件事情完成一件事情,共分共分n个个步骤，关键词是步骤，关键词是“分步分步”区别二区别二每类办法都能每类办法都能独立完成独立完成这件事情。这件事情。每一步得到的只是中间结果，每一步得到的只是中间结果，任何一步都任何一步都不能能独立完成不能能独立完成这件事情这件事情，缺少任何一步也，缺少任何一步也不能完成这件事情，只有每不能完成这件

14、事情，只有每个步骤完成了，才能完成这个步骤完成了，才能完成这件事情。件事情。分类计数原理和分步计数原理，回答的都是关于分类计数原理和分步计数原理，回答的都是关于完成一件事情的不同方法的种数的问题。完成一件事情的不同方法的种数的问题。区别三区别三各类办法是互斥的、各类办法是互斥的、并列的、独立的并列的、独立的各步之间是相关联的各步之间是相关联的分类计数与分步计数原理的区别和联系：分类计数与分步计数原理的区别和联系：ABm1m2mn.ABm1m2mn点评点评:乘法原理看成乘法原理看成“串联电路串联电路”加法原理看成加法原理看成“并联电路并联电路”;甲地甲地丙地丙地丁地丁地乙地乙地N1=23=6N2

15、=42=8N=N1+N2=14 2.如图如图,该电该电路路,从从A到到B共共有多少条不有多少条不同的线路可同的线路可通电？通电？AB分类完成分步完成解解:从总体上看由从总体上看由A到到B的通电线路可分二类的通电线路可分二类,第一类第一类,m1=4 条条 第二类第二类,m3=22=4,条条 所以所以,根据加法原理根据加法原理,从从A到到B共有共有 N=4+4=8 条不同的线路可通电条不同的线路可通电.解解:从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类,m1=3 条条 第二类第二类,m2=1 条条 第三类第三类,m3=22=4,条条 所以所以,根据分类原理根据

16、分类原理,从从A到到B共有共有 N=3+1+4=8 条不同的线路可通电。条不同的线路可通电。在解题有时既要分类又要分步。在解题有时既要分类又要分步。:,B,A,1具体情况如下具体情况如下专业专业趣的强项趣的强项两所大学各有自己感兴两所大学各有自己感兴了解到了解到一名高中毕业生一名高中毕业生在填写高考志愿表时在填写高考志愿表时例例工程学工程学物理学物理学医学医学化学化学生物学生物学大学大学A法学法学信息技术学信息技术学会计学会计学数学数学大学大学B?,择择共共有有多多少少种种这这名名同同学学可可能能的的专专业业选选那那么么.,B,A条件条件合分类加法计数原理的合分类加法计数原理的因此符因此符项专

17、业项专业强强于两所大学没有共同的于两所大学没有共同的又由又由而且只能选择一个专业而且只能选择一个专业能选择一所能选择一所两所大学中只两所大学中只由于这名同学在由于这名同学在分析分析.945,.4B,5A.B,A种择共有这名同学可能的专业选原理类加法计数因此根据分是两所大学共有的项专业强又由于没有一个种专业选择方法学中有大在种专业选择方法大学有在一所两所大学中的这名同学可以选择解?.m3,m2,m1,321有多少种不同的方法有多少种不同的方法那么完成这件事共那么完成这件事共种不同方法种不同方法案中有案中有类方类方在第在第种不同的方法种不同的方法种方案中有种方案中有在第在第种不同的方法种不同的方法

18、类方法中有类方法中有在第在第案案成一件事有三类不同方成一件事有三类不同方如果完如果完探究探究?,B,B,A,A,9162121同的号码同的号码总共能编出多少个不总共能编出多少个不教室里的座位编号教室里的座位编号的方式给的方式给以以阿拉伯数字阿拉伯数字九个九个个大写英文字母和个大写英文字母和用前用前思考思考 987654321AAAAAAAAA987654321号码号码得到的得到的字字数数母母字字A.11.1.,.,1026,.所有可能的号码所有可能的号码的方法可以列出的方法可以列出用图用图两个步骤两个步骤这这后确定一个阿拉伯数字后确定一个阿拉伯数字英文字母英文字母过先确定一个过先确定一个得到一

19、个号码必须经得到一个号码必须经字组成字组成伯数伯数和一个作为下标的阿拉和一个作为下标的阿拉母母号码必须由一个英文字号码必须由一个英文字个问题中个问题中而在这而在这码码都可以给出一个座位号都可以给出一个座位号个个一一个阿拉伯数字中的任何个阿拉伯数字中的任何一个或一个或个英文字母中的任何个英文字母中的任何用用个问题中个问题中在前一在前一不同不同这个问题与前一个问题这个问题与前一个问题.11.1可能号码可能号码请你用树形图列出所有请你用树形图列出所有图图树形树形是解决计数间题常用的是解决计数间题常用的图图.5496,96:个不同的号码因此共有相同而且它们各不个号码字中的任何一个组成一个数都能与个英文

20、字母的任意一个由于前我们还可以这样来思考.,:,号码是各不相同的号码是各不相同的数字组成的数字组成的每个英文字母与不同的每个英文字母与不同的字构成字构成母和一个阿拉伯数母和一个阿拉伯数每个座位由一个英文字每个座位由一个英文字字的出现字的出现和和最重要的特征是最重要的特征是上述问题中上述问题中?征吗征吗你能说说这个问题的特你能说说这个问题的特探究探究.nmN,n2,m1,:,种不同的方法种不同的方法件事共有件事共有那么完成这那么完成这种不同方法种不同方法步有步有做第做第种不同方法种不同方法步有步有做第做第要两个步骤要两个步骤件事需件事需成一成一完完分步乘法计数原理分步乘法计数原理有如下原理有如下

21、原理一般地一般地.2,1步方法的选取步方法的选取都不影响第都不影响第步采用哪种方法步采用哪种方法无论第无论第?,.24,302多少种不同的选法多少种不同的选法共有共有表班级参加比赛表班级参加比赛选出男、女生各一名代选出男、女生各一名代现要从中现要从中名名女生女生名名设某班有男生设某班有男生例例.2,1.,步选女生步选女生第第步选男生步选男生第第可分两个步骤可分两个步骤选出一组参赛代表选出一组参赛代表分析分析;30,130,1选法种不同有人名男生中选出从步第解;24,124,2种不同选择有人名女生中选出从步第.7202430,种不同的选取法共有根据分步乘法计数原理?,m3,m2,m1,321同的

22、方法同的方法少种不少种不那么完成这件事共的多那么完成这件事共的多的方法的方法种不同种不同步有步有做第做第种不同的方法种不同的方法步有步有做第做第种不同的方法种不同的方法步有步有做第做第个步骤个步骤如果完成一件事需要三如果完成一件事需要三探究探究?,n计数呢计数呢那么应当如何那么应当如何中都有若干种不同方法中都有若干种不同方法做每步做每步个步骤个步骤如果完成一件事需要如果完成一件事需要?,13,2,12?,11.23,32,413同取法同取法有多少种不有多少种不本书本书层各取层各取从书架的第从书架的第有多少种不同取法有多少种不同取法本书本书从书架中任取从书架中任取不同的体育书不同的体育书本本层放

23、有层放有第第本不同的文艺书本不同的文艺书层放有层放有第第本不同的计算机书本不同的计算机书层放有层放有书架的第书架的第例例;4,111:3,1种方法有本计算机书层取类方法是从第第类方法有从书架上任取一本书解;3,122种方法有本文艺书层取类方法是从第第.2,133种方法有本体育书层取类方法是从第第.9234mmmN,321不同取法的种数是根据分类加法计数原理:3,13,2,1个步骤完成可以分成本书层各取从书架的第2 2;4,111种方法有本计算机书层取步从第第;3,122种方法有本文艺书层取步从第第.2,133种方法有本体育书层取步从第第.24234mmmN,321不同取法的种数是根据分步乘法计

24、数原理?,234有多少种不同的挂法有多少种不同的挂法问共问共墙的指定位置墙的指定位置幅分别挂在左、右两边幅分别挂在左、右两边幅不同的画中选出幅不同的画中选出从甲、乙、丙从甲、乙、丙要要例例:,23可以分两步完成边墙上幅分别挂在左、右两幅画中选取从解;3,13,1方法种有幅挂在左边墙上幅画中选从步第.2,12,2种方法有上幅画挂在右边墙幅画中选从剩下的步第.623N,不同挂法种数是根据分步乘法计数原理:6种挂法可以表示如下种挂法可以表示如下左边左边右边右边得到的挂法得到的挂法左甲右乙左甲右乙甲甲乙乙丙丙左左甲甲右右丙丙甲甲乙乙丙丙左左乙乙右右甲甲左左乙乙右右丙丙甲甲乙乙丙丙左左丙丙右右甲甲左丙右

25、乙左丙右乙.,;,:.,件事件事步骤都完成才算做完这步骤都完成才算做完这只有各个只有各个依存依存各个步骤中的方法互相各个步骤中的方法互相题题问问分步分步的是的是分步乘法计数原理针对分步乘法计数原理针对事事可以做完这件可以做完这件用其中任何一种方法都用其中任何一种方法都立立其中各种方法相互独其中各种方法相互独问题问题分类分类针对是针对是原理原理计数计数分类加法分类加法区别在于区别在于种数问题种数问题法的法的有关做一件事的不同方有关做一件事的不同方回答的都是回答的都是步乘法计数原理步乘法计数原理分类加法计数原理和分分类加法计数原理和分?.91,ZUGA,3,5序命名序命名问最多可以给多少个程问最多

26、可以给多少个程后两个要求用数字后两个要求用数字或或要求用字母要求用字母其中首字符其中首字符个字符个字符需要用需要用给程序模块命名给程序模块命名例例.3;,2;,1:,类类而首字符又可以分为两而首字符又可以分为两符符步选最后一个字步选最后一个字第第选中间字符选中间字符步步第第选首字符选首字符步步第第可以分三个步骤可以分三个步骤要给一个程序模块命名要给一个程序模块命名分析分析.1367,.种选法首字符共有由分类加法计数原理先计算首字符的选法解.1053,10539913,.个程序命名即最多可以给个不同的名称最多可以有理由分步乘法计数原名称再计算可能的不同程序?吗吗你你还还能能给给出出不不同同的的解

27、解法法?RNA,100RNA.,RNA.U,G,C,A,4.,RNA.RNA6分子分子少种不同的少种不同的那么能有多那么能有多个碱基组成个碱基组成分子由分子由有一类有一类假设假设位置上的碱基无关位置上的碱基无关个位置上的碱基与其他个位置上的碱基与其他所以在任意一所以在任意一序出现序出现各种碱基能够以任意次各种碱基能够以任意次中中分子分子在一个在一个表示表示分别用分别用同的碱基同的碱基种不种不总共有总共有分所占据分所占据一种称为碱基的化学成一种称为碱基的化学成由由长链中每一个位置上都长链中每一个位置上都至数千个位置的长链至数千个位置的长链甚甚分子是一个有着数百个分子是一个有着数百个一个一个的化学

28、成分的化学成分现现分子是在生物细胞中发分子是在生物细胞中发核糖核酸核糖核酸例例.U,G,C,A,100,100任选一个来占据任选一个来占据中中每个位置都可以从每个位置都可以从个位置个位置这时我们有这时我们有个碱基组成的长链个碱基组成的长链用下面的图来表示由用下面的图来表示由分析分析位位第第1位位第第2位位第第3位位第第100种种4种种4种种4种种4 .4,U,G,C,A,.,100100充方法种填每个位置有中任选一个填入从置中从左到右依次在每个位如上图所示个位置个碱基组成的长链共有解长度为根据分步乘法计数原理,分子数目有的所有可能的不同RNA100.4444100个 4100个.NAR.,10

29、6.1460100资料资料的有关的有关阅一下阅一下以自己查以自己查的同学可的同学可有兴趣有兴趣数数非常大的非常大的这是一个这是一个?,6763GB2?81:.8,.,10.,7表示表示字至少要用多少个字节字至少要用多少个字节每个汉每个汉要对这些汉字进行编码要对这些汉字进行编码个汉字为一个字符个汉字为一个字符一一个汉字个汉字包含了包含了码码计算机汉字国标码计算机汉字国标码同的字符同的字符最多可以表示多少个不最多可以表示多少个不位位一个字节一个字节问问个二进制位构成个二进制位构成每个字节由每个字节由最小计量单位最小计量单位据存储的据存储的其中字节是计算机中数其中字节是计算机中数多个字节来表示多个字

30、节来表示每个字符可以用一个或每个字符可以用一个或需要对字符进行编码需要对字符进行编码字符字符为了使计算机能够识别为了使计算机能够识别即二进制即二进制种数字的记数法种数字的记数法两两或或了每一位只有了每一位只有因此计算机内部就采用因此计算机内部就采用状态状态两种两种而这也是最容易控制的而这也是最容易控制的的高与低等两种状态的高与低等两种状态的通与断、电位的通与断、电位易实现电路易实现电路容容电子元件很电子元件很例例.,1,0,8数原理求解本题数原理求解本题因此可以用分步乘法计因此可以用分步乘法计字符字符同的同的而且不同的顺序代表不而且不同的顺序代表不两种选择两种选择值都有值都有每一位上的每一位上

31、的个二进制位个二进制位由于每个字节有由于每个字节有分析分析;256222222222,.2,88个不同的字符一个字节最多可以表示法计数原理根据分步乘种选择每位上有位一个字节有来表示一个字节用图解31.1位位第第1位位第第2位位第第3位位第第8种种2种种2种种2种种2 31.1图图 .256,256.2,6763,12种表示方法后一个字节也有种不同的表示方法前一个字节有能够表示多少个字符个字节我们就考虑用个字符不够不同用一个字节所能表示的知由.2,.6763,536652562562,个字节表示每个汉字至少要用所以要表示这些汉字的汉字个数经大于汉字国标码包含这已个不同字符示个字节可以表根据分步乘

32、法计数原理?,?:.,41.1.,.),(.8以减少测试次数吗以减少测试次数吗法法序员设计一个测试方序员设计一个测试方少测试次数你能帮助程少测试次数你能帮助程程序员需要设法减程序员需要设法减时间时间为了减少测试为了减少测试另外另外执行路径执行路径这个程序模块有多少条这个程序模块有多少条问问路径的程序模块路径的程序模块它是一个具有许多执行它是一个具有许多执行如图如图模块组成模块组成一个程序模块由许多子一个程序模块由许多子的的一般一般个测试数据个测试数据以便知道需要提供多少以便知道需要提供多少线线路路即程序从开始到结束的即程序从开始到结束的径径多少条执行路多少条执行路到底有到底有程序员需要知道程序

33、员需要知道要对程序进行测试要对程序进行测试好程序以后需好程序以后需计算机编程人员在编写计算机编程人员在编写例例条执行路径条执行路径子模块子模块181条执行路径条执行路径子模块子模块452条执行路径条执行路径子模块子模块283条执行路径条执行路径子模块子模块435条执行路径条执行路径子模块子模块384结结束束开开始始A.A2;A1:到结束到结束点执行点执行步是从步是从第第点点步是从开始执行到步是从开始执行到第第成成行路径都分两步完行路径都分两步完整个模块的任意一条执整个模块的任意一条执分析分析来来或或子子模模块块或或子子模模块块步步可可由由子子模模块块而而第第3211;完完成成.542来来完完成

34、成或或子子模模块块步步可可由由子子模模块块第第.原理原理计数计数执行路径需要用到两个执行路径需要用到两个一条指令在整个模块的一条指令在整个模块的分析分析因此因此,);(91284518321,条的子路径共有子模块或或子模块子模块由分类加法计数原理解);(81433854条的子路径共有或子模块子模块).(73718191,条有整个模块的执行路径共又由分步乘法计数原理.1724338284518.,5,.,试次数为总共需要测作是否一正常以考察每个子模块的工块个模它可以先分别单独测试这样来测试整个模块了正确的子模块的方式即通过只考察是否执行黑箱模块看成一个程序员总是把每一个子在实际测试中.632,2

35、1,需要测试次数为常之间的信息交流是否正步中的各子模块步中的各个子模块和第试程序第只需要测信息交流是否正常再测试各个模块之间的.1786172,.,次为试整个模块的次数就变测这样作正常那么整个程序模块就工息交流也正常并且各子模块之间的信工作如果每个子模块都正常.7371178,的差距是非常大的与显然?实现减少测试次数的吗你看出了程序员是如何?.3,3,33,.,9少辆汽车上牌照少辆汽车上牌照那么这种办法共能给多那么这种办法共能给多必须合成一组出现必须合成一组出现个数字也个数字也现现个字母必须合成一组出个字母必须合成一组出并且并且字字个不重复的阿拉伯数个不重复的阿拉伯数复的英文字母和复的英文字母

36、和个不重个不重有有每一个汽车牌照都必须每一个汽车牌照都必须成办法成办法种汽车牌照组种汽车牌照组交通管理部门出台了一交通管理部门出台了一扩容扩容汽车牌照号码需要汽车牌照号码需要庭汽车拥有量迅速增长庭汽车拥有量迅速增长某城市家某城市家高高着人们生活水平的提着人们生活水平的提随随例例.6.,2,个步骤个步骤的字母和数字可以分的字母和数字可以分确定一个牌照确定一个牌照在右在右母组合在左和字母组合母组合在左和字母组合即字即字类类牌照可以分为牌照可以分为按照新规定按照新规定分析分析.,2类的字母组合在右另一一类字母组合在左类将汽车牌照分为解:6,字母和数字照的个步骤确定一个汽车牌分字母组合在左时;26,1

37、26,1种选法有放在首位个个字母中选从步第;25,2,125,2种选法有位放在第个个字母中选从剩下的步第;24,3,124,3种选法有位放在第个个字母中选从剩下的步第;10,4,110,4种选法有位放在第个个数字中选从步第;9,5,19,5种选法有位放在第个个数字中选从剩下的步第.8,6,18,6种选法有位放在第个个数字中选从剩下的步第.000232118910242526,个有字母组合在左的牌照共根据分步乘法计数原理.00023211,个有字母组合在右的牌照也同理.224640001123200011232000,辆汽车上牌照共能给所以?题的方法吗题的方法吗法计数原理解决计数问法计数原理解决

38、计数问法计数原理、分步乘法计数原理、分步乘你能归纳一下用分类加你能归纳一下用分类加思考思考?,关系吗关系吗似的似的法计数原理也有这种类法计数原理也有这种类乘法计数原理和分类加乘法计数原理和分类加分步分步加法运算的简化加法运算的简化乘法运算是特定条件下乘法运算是特定条件下思考思考.不不重重不不漏漏分分类类要要做做到到分类后再分别分类后再分别.,得到总数得到总数数原理求和数原理求和最后用分类加法计最后用分类加法计对每一类进行计数对每一类进行计数完完成成了了所所有有.步步骤骤完完整整分分步步要要做做到到.,.,得到总数得到总数每一步方法数相乘每一步方法数相乘把完成把完成原理原理最后根据分步乘法计数最

39、后根据分步乘法计数数数方法方法分步后再计算每一步的分步后再计算每一步的立立相互独相互独当然步与步之间要当然步与步之间要恰好完成任务恰好完成任务步骤步骤.,需要分步需要分步是是要分类还要分类还需需细分析细分析行仔行仔前要进前要进之之计算计算开始开始在在重要的是重要的是最最数问题时数问题时原理解决计原理解决计用两个计数用两个计数有有60种取法。种取法。因此取法种数共有因此取法种数共有40+60=100（种）（种）例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，60个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求法？解：取一个球的方法可以分成两类：解：取一个球

40、的方法可以分成两类：一类是从装白球的袋子里取一个白球一类是从装白球的袋子里取一个白球有有40种取法；种取法；另一类是从装红球的袋子里取一个红球另一类是从装红球的袋子里取一个红球40个个60个个例例2：两个袋子里分别装有两个袋子里分别装有40个红球与个红球与60个白球，个白球，从中取一个白球和一个红球，有多少种取法？从中取一个白球和一个红球，有多少种取法？60个个40个个解：取一个白球和一个红球可以分成两步解：取一个白球和一个红球可以分成两步来完成：来完成：第一步从装白球的袋子里取一个白球，第一步从装白球的袋子里取一个白球，有有60种取法；种取法；因此取一个白球和一个红球的方法共有因此取一个白球

41、和一个红球的方法共有60 40=2400（种）（种）第二步从装红球的袋子里取一个红球，第二步从装红球的袋子里取一个红球，有有40种取法。种取法。例例3：某班级有男三好学生某班级有男三好学生5人人,女三好学生女三好学生4人。人。(1)从中任选一人去领奖从中任选一人去领奖,有多少种不同的选法？有多少种不同的选法？(2)从中任选男、女三好学生各一人去参加座谈会从中任选男、女三好学生各一人去参加座谈会,有有多少种不同的选法？多少种不同的选法？解解:(1)完成从三好学生中任选一人去领奖这件事完成从三好学生中任选一人去领奖这件事,共有共有2类办法类办法,第一类办法第一类办法,从男三好学生中任选一人从男三好

42、学生中任选一人,共有共有 m1=5 种种 不同的方法不同的方法;第二类办法第二类办法,从女三好学生中任选一人从女三好学生中任选一人,共有共有 m2=4 种不种不 同的方法同的方法;所以所以,根据加法原理根据加法原理,得到不同选法种数共有得到不同选法种数共有 N=5+4=9 种。种。例例3：某班级有男三好学生某班级有男三好学生5人人,女三好学生女三好学生4人。人。(1)从中任选一人去领奖从中任选一人去领奖,有多少种不同的选法？有多少种不同的选法？(2)从中任选男、女三好学生各一人去参加座谈会从中任选男、女三好学生各一人去参加座谈会,有有多少种不同的选法？多少种不同的选法？解解:(2)完成从三好学

43、生中任选男、女各一人去参加座谈完成从三好学生中任选男、女各一人去参加座谈会这件事会这件事,需分需分2步完成步完成,第一步第一步,选一名男三好学生选一名男三好学生,有有 m1=5 种方法种方法;第二步第二步,选一名女三好学生选一名女三好学生,有有 m2=4 种方法种方法;所以所以,不同选法种数共有不同选法种数共有 N=5 4=20 种。种。点评点评:解题的关键是从总体上看这件事情是解题的关键是从总体上看这件事情是“分类完成分类完成”,还是还是“分步完成分步完成”，“分类完成分类完成”用用“加法原理加法原理”，“分分步完成步完成”用用“乘法原理乘法原理”。1 1、书架的第、书架的第1 1层放有层放

44、有4 4本不同的计算机书，第本不同的计算机书，第2 2层放有层放有3 3本不同本不同 的文艺书，第的文艺书，第3 3层放有层放有2 2本不同的体育书本不同的体育书（1 1）从书架上任取）从书架上任取1 1本书，有多少种不同的取法？本书，有多少种不同的取法？（2）从书架的第）从书架的第1、2、3层各取层各取1本书，有多少种不同的取法？本书，有多少种不同的取法？4+3+2=9（种）（种）4 3 2=24（种）（种）2、由数字、由数字1，2，3，4，5，6可以组成多少个四位数？可以组成多少个四位数？（各位上的数字不重复）（各位上的数字不重复）6 5 4 3=360（个）（个）3、一种号码锁有、一种号

45、码锁有4个拨号盘，每个拨号盘上有从个拨号盘，每个拨号盘上有从0到到9共共10个个 数字，数字，这这4个拨号盘可以组成多少个四位数字的号码？个拨号盘可以组成多少个四位数字的号码？10 10 10 10=104练习1 有些较复杂的问题往往不是单纯的有些较复杂的问题往往不是单纯的“分类分类”“”“分分步步”可以解决的，而要将可以解决的，而要将“分类分类”“”“分步分步”结合起来结合起来运用一般是先运用一般是先“分类分类”，然后再在每一类中，然后再在每一类中“分分步步”，综合应用分类计数原理和分步计数原理请看综合应用分类计数原理和分步计数原理请看下面的例题：下面的例题：注意注意例例4：某城市电话号码由

46、某城市电话号码由8位组成，其中从左边算起的第位组成，其中从左边算起的第1位只用位只用6或或8，其余，其余7位可以从前位可以从前10个自然数个自然数0，1，2，,9中任意中任意选取，允许数字重复。试问：该城市最多可装电话多少门？选取，允许数字重复。试问：该城市最多可装电话多少门？1 2 3 4 5 6 7 8第第1类类6解：装一门电话需要指定一个解：装一门电话需要指定一个电话号码，由题意电话号码可以电话号码，由题意电话号码可以分成两类：分成两类：第第1类电话号码第类电话号码第1位用位用6，确定其余确定其余7位号码可以分位号码可以分7步完成。步完成。10 10 10 10 10 10 10因此第一

47、类电话号码共有因此第一类电话号码共有10 10 10 10 10 10 10=1071 2 3 4 5 6 7 8第第2类类8同理，第同理，第2类电话号码也有类电话号码也有10 个，个，7因此，该城市所用的电话号码共有因此，该城市所用的电话号码共有10+10=2 10 个个从而最多可装电话从而最多可装电话2 10 门，即两千万门。门，即两千万门。7777 从甲地到乙地有从甲地到乙地有3条路，从乙地到丁地有条路，从乙地到丁地有2条路；条路；从甲地到丙地有从甲地到丙地有3条路，从丙地到丁地有条路，从丙地到丁地有4条路，条路，问：从甲地到丁地有多少种走法？问：从甲地到丁地有多少种走法？甲地乙地丙地丁

48、地解：要完成从甲地到丁地这件事情有解：要完成从甲地到丁地这件事情有两种路线可以走，即可以分为两类：两种路线可以走，即可以分为两类：甲地甲地 乙地乙地 丁地丁地甲地甲地 丙地丙地 丁地丁地第一类又可以分为两步，第一步有第一类又可以分为两步，第一步有3种种方法，第二步有方法，第二步有2种方法，因此第一类种方法，因此第一类走法有走法有3 2=6（种）（种）同理第二类走法有同理第二类走法有3 4=12（种）（种）所以，从甲地到丁地有所以，从甲地到丁地有6+12=18种走法。种走法。1有不同的中文书有不同的中文书9本，不同的英文书本，不同的英文书7本，不同的日文书本，不同的日文书5本从其中取出不是同一国

49、文字的书本从其中取出不是同一国文字的书2本，问有多少种不同本，问有多少种不同的取法？的取法？2集合集合A=1,2,-3,B=-1,-2,3,4 从从A,B 中各取中各取1个元素作个元素作为点为点P(x,y)的坐标的坐标（1）可以得到多少个不同的点？）可以得到多少个不同的点？（2）这些点中，位于第一象限的有几个？）这些点中，位于第一象限的有几个？3某中学的一幢某中学的一幢5层教学楼共有层教学楼共有3处楼梯，问从处楼梯，问从1楼到楼到5楼共楼共有多少种不同的走法？有多少种不同的走法？4.集合集合A=1,2,3,4,B=5,6,7,从从A到到B的映射有多少个？的映射有多少个？讲讲练练讲讲练练9795

50、7514334432422228333381333381能否先排个位？能否先排个位？法法1：先排百位，然后十位，最后个位。：先排百位，然后十位，最后个位。奇奇偶偶解：在艺术组解：在艺术组9 9人中，有且仅有一人既会钢琴又会小号人中，有且仅有一人既会钢琴又会小号（把该人称为（把该人称为“多面手多面手”），只会钢琴的有），只会钢琴的有6 6人，只会人，只会小号的有小号的有2 2人，把会钢琴、小号各人，把会钢琴、小号各1 1人的选法分为两类：人的选法分为两类：第一类：多面手入选，另一人只需从其他第一类：多面手入选，另一人只需从其他8 8人中任人中任选一个，故这类选法共有选一个，故这类选法共有8 8种