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

1、分类加法计数原理 与分步乘法计数原理,用大写的英文字母AZ或数字09给教室的座位编号，能编出多少种不同的号码？,分析: 给座位编号有2类方法,第一类方法, 用英文字母，有26种号码;,第二类方法, 用阿拉伯数字，有10种号码;,所以 有 26 + 10 = 36 种不同号码.,从甲地到乙地，可以乘火车，也可以乘汽车。一天中，火车有4 班，汽车有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?,分析: 从甲地到乙地有2类方法,第一类方法, 乘火车，有4种方法;,第二类方法, 乘汽车，有2种方法;,所以 从甲地到乙地共有 4 + 2 = 6 种方法.,能说说以上两个问题的特征吗？

2、,两类中的方法不相同,分类加法计数原理,完成一件事有两类不同方案,在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法.那么完成这件事共有 N=m+n 种不同的方法,每个座位可以用一个英文字母或一个阿拉伯数字编号，因为字母与数字的不同，编出的号码也不同。,上述问题中，最重要的特征是“或”字的出现：,5,4,+,=9,例1 在填写高考志愿表时,一名高中毕业生了解到, A,B两所大学各有一些自己感兴趣的强项专业,具体如下:,分析:两大学只能选一所一专业,且没有共同的强项专业,这名同学可能的专业选择共有多少种?,这名同学可能的专业选择共有9种,若还有C大学,其中强项专业为：新闻学,金融学,

3、人力资源学.那么,这名同学可能的专业选择共有多少种？,C大学 新闻学 金融学 人力资源学,+,3,=12,这名同学可能的专业选择共有12种,N=m1+m2+mn,完成一件事有三类不同方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，在第3类方案中有m3种不同的方法。那么完成这件事共有 N=m1+m2+m3 种不同的方法.,做一件事情，完成它可以有n类办法,在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那么完成这件事共有 . 种不同的方法,正确理解分类加法计数原理：,分类加法计数原理针对的是“分类”问题，,完成一件事

4、要分为若干类，,各类的方法相互独立，,各类中的各种方法也相对独立，,用任何一类中的任何一种方法都可以单独完成这件事.,用前6个大写英文字母和19个阿拉伯数字,以 A1, A2, , B1 , B2 的方式给教室的座位编号.,A1 A2 A3 A4 A5 A6 A7 A8 A9,9种,9种,6 9 =54,有多少不同的号码?,如图,由A村去B村的道路有3条，由B村去C村的道路有2条。从A村经B村去C村，共有多少种不同的走法?,分析: 从A村经 B村去C村有 2 步,第一步, 由A村去B村有 3 种方法,第二步, 由B村去C村有 2 种方法,所以从A村经 B村去C村共有 3 2 = 6 种不同的方

5、法,指出上述问题的特征？,分步乘法计数原理,完成一件事需要两个步骤,做第1步有m种不同的方法,做第2步有n种不同的方法,那么完成这件事共有 N=mn 种不同的方法.,每个座位是由一个英文字母和一个阿拉伯数字组成，不同字母和不同数字组成的号码是各不相同的。,上述问题中：最重要的特征是“和”字的出现：,无论第一步采用哪种方法，都不影响第二步方法的选取.,男,女,30,24,=720,老师,3,=2160,例2 设某班有男生30名,女生24名.现要从中选出男、女各一名代表班级参加比赛,共有多少种不同的选法?,分两步进行选取,根据分步乘法原理,第一步：从30名男生中选取1名，有30种选法；,第二步：从

6、24名女生中选取1名，有24种选法；,若再要从语,数,英三科科任老师中选出一名代表参加比赛,那又共有多少种选法?,如果完成一件事需要三个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法,做第3步有m3种不同的方法,那么完成这件事共有 _ 种不同的方法.,N=m1m2m3,N=m1m2mn,做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有 _ 种不同的方法.,正确理解分步乘法计数原理：,分步计数原理针对的是“分步”问题，,完成一件事要分为若干步，,各个步骤相互依存，,完成任何其中的一步都不能完成该

7、件事，,只有当各个步骤都完成后，才算完成这件事.,N=4+3+2=9,N=432=24,例3 书架第1层放有4本不同的计算机书,第2层放有3本不同的文艺书,第3层放有2本不同的体育书.,(1)从书架中取1本书,有多少种不同取法?,有3类方法,根据分类加法计数原理,分3步完成,根据分步乘法计数原理,(2)从书架第1,2,3层各取1本书,有多少种不同取法?,解题关键：从总体上看做这件事情是“分类完成”,还是“分步完成”.再根据其对应的计数原理计算.,哪些类？,哪些步？,分类加法计数原理与分步乘法计数原理异同点,相同点：都是完成一件事的不同方法种数的问题,不同点：分类加法计数原理针对的是“分类”问题

8、,“类”：完成一件事要分为若干类，各类的方法相互独立，各类中的各种方法也相对独立，用任何一类中的任何一种方法都可以单独完成这件事，是独立完成；,“步”：完成一件事要分为若干步，各个步骤相互依存，完成任何其中的一步都不能完成该件事，只有当各个步骤都完成后，才算完成这件事，是合作完成.,左边,右边,甲,乙,丙,3,2,第一步,第二步,例4 要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置,问共有多少种不同的挂法?,分两步完成,练习,在所有的两位数中,个位数字大于十位数字的两位数共有多少个？,分析1:,按个位数字是2,3,4,5,6,7,8,9分成8类,在每一类中满足条件的两位

9、数分别是:,1个,2个,3个,4个,5个,6个,7 个,8 个.,根据加法原理共有 1+2+3+4+5+6+7+ 8 =36 (个).,分析2:,按十位数字是1,2,3,4,5,6,7,8分成8类，,在每一类中满足条件的两位数分别是:,8个,7个,6个,5个,4个,3个,2个,1个.,根据加法原理共有 8+7+6+5+4+3+2+1 = 36 (个),分析3:,第一步个位9种选法，第二步十位8种选法，除2,练习 一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7, 8,9十个数字组成；可以设置多少种三位数的密码(各位上的数字允许重复)? 首位数字不为0的密码数是多少? 首位数字是0的密

10、码数又是多少?,分析: 按密码位数,从左到右依次设置第一位、第二位、第三位, 需分为三步完成;,第一步, m1 = 10;,第二步, m2 = 10;,第三步, m3 = 10.,根据乘法原理, 共可以设置,共可设置 N = 101010 = 103 种三位数的密码。,首位数字是0的密码数是N = 11010 = 102 种,首位数字不为0的密码数是N =91010 = 9102 种,例5 给程序模块命名，需要用3个字符，其中首字符要求用字母AG或UZ，后两个要求用数字19,问最多可以给多少个程序命名？,分析：可以分步解决,解：第1步：选首字符，共有7613种选法,第2步：选中间字符，共有9种

11、选法,第3步，选最后一个字符，共有9种选法,根据分步计数原理，最多可以有13991053个不同的名称,有些较复杂的问题往往不是单纯的“分类”“分步”可以解决的，而要将“分类”“分步”结合起来运用一般是先“分类”，然后再在每一类中“分步”，,4100个,例6 核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据.总共有4种不同的碱基，分别用A，C，G，U表示.在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关.假设有一类RNA分子由100个碱基组成，

12、那么能有多少个不同的RNA分子？,分析：用图来表示由100个碱基组成的长链，这时我们共有100个位置，每个位置都可以从A , C , G , U 中任选一个来占据,每个位置有 4 种填充方法根据分步乘法计数原理，长度为 100 的所有可能的不同 RNA 分子数目有：,解：100个碱基组成的长链共有 100个位置，,如图所示从左到右依次在每一个位置中，从 A , C , G , U 中任选一个填入，,例7 电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制.为了使计算机能够识别字符，需要对字符进行

13、编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位,每个字节由8个二进制位构成.问： 一个字节（8位）最多可以表示多少个不同的字符？ 计算机汉字国际码（GB码）包含了6 763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,；,而且不同的顺序代表不同的字符，因此可以用分步乘法计数原理求解.,22222222= 28 =256 个不同的字符,解：用图来表示一个字节一个字节共有 8 位，每位上有 2 种选择根据分步乘法计数原理，一个字节最多可以表示,分析：由于每个字节有 8 个二进制位，,每一位上的值都有 0,1两种选择，,这已经

14、大于汉字国标码包含的汉字个数 6 763.所以要表示这些汉字，每个汉字至少要用 2 个字节表示.,由知,用一个字节所能表示的不同字符不够 6 763 个,我们就考虑用2 个字节能够表示多少个字符,前一个字节有 256 种不同的表示方法，后一个字节也有 256 种表示方法,根据分步乘法计数原理，2个字节可以表示 256256 = 65536个 不同的字符，,例8 计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.如图所示是一个具有许多执行路径的程序模块. （1）这

15、个程序模块有多少条执行路径； （2）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？,例9 随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌照组成方法，每一个汽车牌照都必须有3个不重复的英文字母和3个不重复的阿拉伯数字，并且3个字母必须合成一组出现，3个数字也必须合成一组出现.那么这种办法共能给多少辆汽车上牌照？,分析：按照新规定，牌照可以分为 2类，即字母组合在左和字母组合在右确定一个牌照的字母和数字可以分6个步骤,解：将汽车牌照分为 2 类，一类的字母组合在左，另一类的字母组合在右字母组

16、合在左时，分6个步骤确定一个牌照的字母和数字：,第1步, 从26个字母中选1个,放在首位,有26种选法;,第2步,从剩下的25个字母中选 1个,放在第2位,有25种选法;,第3步,从剩下的24个字母中选 1个,放在第3位,有24种选法;,第4步,从10个数字中选1个,放在第 4 位,有10种选法;,第5步,从剩下的 9个数字中选1个,放在第5位,有9种选法;,第6步,从剩下的 8个字母中选1个,放在第6位,有8种选法;,根据分步乘法计数原理，字母组合在左的牌照共有:,26 25241098=11 232 000 个.,同理，字母组合在右的牌照也有11232 000 个,所以，共能给11232

17、000 + 11232 000 = 22464 000(个)辆汽车上牌照.,用两个计数原理解决计数问题时，最重要的是在开始计算之前要进行仔细分析,需要分类还是需要分步,分类要做到“不重不漏”,分类后再分别对每一类进行计数，,最后用分类加法计数原理求和，得到总数,分步要做到“步骤完整”,完成了所有步骤，恰好完成任务，,当然步与步之间要相互独立,分步后再计算每一步的方法数，,最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数,2 乘积(a1+a2+a3 )(b1+b2+b3+b4 )(c1+c2+c3+c4+c5) 展开后共有多少项？,练习：,1 要从甲、乙、丙3名工人中选出2名分别上日

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

19、可以走，从丙地到丁地有2条路。从甲地到丁地共有多少种不同地走法？,10 如图,该电路,从A到B共有多少条不同的线路可通电？,解: 从总体上看由A到B的通电线路可分二类,第一类, m1 = 4 条,第二类, m3 = 22 = 4 条,所以, 根据加法原理, 从A到B共有,N = 4 + 4 = 8 条不同的线路可通电.,。,练习 如图为一电路图，从A到B共有_条不同的线路可通电,共有3+1+2 2=8种通电方法。,加法原理看成“并联电路”;,乘法原理看成“串联电路”,11 集合A=1,2,-3,B=-1,-2,3,4 从A,B 中各取1个元素作为点P(x,y) 的坐标 （1）可以得到多少个不同

20、的点？ （2）这些点中，位于第一象限的有几个？,12 在所有的两位数中，个位数字比十位数字大的两位数有多少个？,13 有架楼梯共6级，每次只允许上一级或两级，求上完这架楼梯共有多少种不同的走法？,14 某艺术组有9人，每人至少会钢琴和小号中的一种乐器，其中7人会钢琴，3人会小号，从中选出会钢琴与会小号的各1人，有多少种不同的选法？,344324,22228,15 将一个四棱锥的每个顶点染上一种颜色，并使同一条棱上的两端点颜色不同，如果只有5种颜色可供使用，求共有多少种不同的染色方法？,解: 按地图A、B、C、D四个区域依次分四步完成, 第一步, m1 = 3 种, 第二步, m2 = 2 种,

21、 第三步, m3 = 1 种, 第四步, m4 = 1 种, 所以根据乘法原理, 得到 不同的涂色方案种数共有,练习：如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?,N = 3 2 11 = 6 种。,问: 若用2色、4色、5色等,结果又怎样呢?,5433 = 180 种。,答:它们的涂色方案种数分别是 0,4322 = 48,练习 如图,一蚂蚁沿着长方体的棱,从一个顶点爬到相对的另一个顶点的最近路线共有多少条?,解:如图,从总体上看,如,蚂蚁从顶点A爬到顶点C1有三类方法,从局部上看每类又需两步

22、完成,所以,第一类, m1 = 12 = 2 条,第二类, m2 = 12 = 2 条,第三类, m3 = 12 = 2 条,所以, 根据加法原理, 从顶点A到顶点C1最近路线共有,N = 2 + 2 + 2 = 6 条。,加法原理和乘法原理的共同点是什么？不同点什么？,联系,区别一,完成一件事情共有n类 办法，关键词是“分类”,完成一件事情,共分n个 步骤，关键词是“分步”,区别二,每类办法都能独立完成这件事情.,每一步得到的只是中间结果，任何一步都不能独立完成这件事情，缺少任何一步也不能完成这件事情，只有每个步骤完成了，才能完成这件事情.,分类计数原理和分步计数原理，回答的都是关于完成一件事情的不同方法的种数的问题,区别三,各类办法是互斥的、并列的、独立的,各步