分类计数原理与分步计数原理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1.2,分类计数原理,与,分步计数原理,(,二,),1,、分类加法计数原理,：完成一件事，有,n,类办法，在第,1,类办法中有,m,1,种不同的方法,在第,2,类办法中有,m,2,种不同的方法,在第,n,类办法中,有,m,n,种不同的方法,.,那么完成这件事共有 种不同的方法,.,2,、分步乘法计数原理,：,完成一件事，需要分成,n,个步骤，做第,1,步有,m,1,种不同的方法,做第,2,步有,m,2,种不同的方法,，做第,n,步有,m,n,种不同的方法,.,那么完成这件事共有 种不同的方法,.,分类加法计数原理和分步乘法计数原理的,共同点：,不同点：,分类加法计数原理与分类有关，,分步乘法计数原理与分步有关。,回答的都是有关做一件事的不同方法种数的问题,加法原理,乘法原理,联系,区别一,完成一件事情共有,n,类,办法，关键词是“分类”,完成一件事情,共分,n,个,步骤，关键词是“分步”,区别二,每类办法都能,独立完成,这件事情。,它是独立的、一次的、且每次得到的是最后结果，,只须一种方法就可完成这件事,。,每一步得到的只是,中间结果,，,任何一步都,不能能独立完成,这件事情,，缺少任何一步也,不能完成这件事情，,只有每,个步骤完成了，才能完成这,件事情。,分类计数原理和分步计数原理，回答的都是关于,完成一件事情的不同方法的种数的问题。,区别三,各类办法是互相独立的,各步之间是互相关联的,分类计数与分步计数原理的区别和联系：,例,1.,五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多少种？,解：（,1,）,5,名学生中任一名均可报其中的任一项，因此每个学生都有,4,种报名方法，,5,名学生都报了项目才能算完成这一事件故报名方法种数为,44444=,种,.,（,2,）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有,5,种故有,n,=5,=,种,.,例,2,要从甲、乙、丙,3,名工人中选出,2,名分别上白班和晚班，有多少种不同的选法？,解：要排好一个白班和晚班须分两个步骤来完成,:,第,1,步是从甲、乙、丙,3,人中选,1,人上白班,有,3,种选法,:,第,2,步是选,1,人上晚班,但这时只能从剩下的,2,人中选,1,人,有,2,种方法,根据分步计数原理,不同的选法种数是：,32=6.,具体排法,白班 晚班,白班 晚班,甲 乙,甲 丙,乙 甲,丙 乙,丙 甲,乙 丙,例,3,在所有的两位数中，个位数字大于十位数字的两位数共有多少个？,分析,1:,按个位数字是,2,3,4,5,6,7,8,9,分成,8,类，在每一类中满足条件的两位数分别是：,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 (,个,).,变式：从,1,到,200,的自然数中,各个,数位上都不含,8,的自然数有多少个？,分三类,:,第一类：一位数中除,8,以外的数符,合要求，共 个,8,第二类：两位数中十位、个位都,不含,8,的数,有,个,.,98=72,99+1=82,第三类,:,三位数中符合要求的数,共有,个,.,则满足条件的总的自然数有,:,N=8+98+99+1=162,个,.,例,4,某艺术组有,9,人，每人至少会钢琴和小号中的一种乐器，其中有,7,人会钢琴，,3,人会小号，从中选出会钢琴与会小号的各,1,人，有多少种不同的选法？,解：由题意可知，艺术组,9,人中，只会钢琴的有,6,人，只会小号的有,2,人，既会钢琴又会小号的有,1,人,(,可把该人称为多面手,),因此，选出会钢琴与会小号的各,1,人可分两类：,第一类：不选多面手，分,2,步：第一步从只会钢琴的,6,人中选,1,人，有,6,种选法；第二步从只会小号的,2,人中选,1,人，有,2,种选法，因此，共有,62=12(,种,).,第二类：选多面手，分,2,步：第一步从多面手中选，有,1,种选法；第二步从非多面手中选，有,8,种选法，因此，共有,18=8(,种,).,故,共有,12+8=20(,种,).,注：先分类，后分步,.,特殊元素优先考虑法,.,例,5,用红、黄、蓝不同颜色旗各,3,面，每次升一面、两面、三面在某一旗杆上纵向排列，共可以组成多少种不同的信号？,解：不同的信号可分为三类：,第一类：升一面旗，又可分三类，有,1+1+1=3,种,第二类：升两面旗，可分两步，有,33=9,种,第三类：升三面旗，可分三步，有,333=27,种,故共有,3+9+27=39(,种,),评注：先分类，再在每一类中分类或分步,.,例,6,如图，要给地图,A,、,B,、,C,、,D,四个区域分别涂上,3,种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？,（染色问题）,解,:,按地图,A,、,B,、,C,、,D,四个区域依次分四步完成,第一步,m,1,= 3,种,第二步,m,2,= 2,种,第三步,m,3,= 1,种,第四步,m,4,= 1,种,根据乘法原理,得到不同的涂色方案种数共有,: N = 3 2 11 = 6,种,.,例,6,如图，要给地图,A,、,B,、,C,、,D,四个区域分别涂上,3,种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,思考,:,若有,4,种或,5,种颜色可供选择,结果分别如何？,提示,:,涂色种数分别是,:,4322 = 48,种；,5433 = 180,种；,4,3,例,7,(1),将,3,封信投入,4,个不同的信箱，,共有,种不同的投法。,例,7,（,2,）由,4,名学生争夺,3,个比赛,项目的冠军，冠军获得者共有多少种,可能？,住店法,:,解决,“,允许重复排列问题,”,要注意区分两类,元素：一类元素可以重复，另一类不能重复,.,把不能重,复的元素看作,“,客,”,能重复的元素看作,“,店,”,再利用分步计数原理直接求解的方法称为,“,住店法,”,.,变式：,（,1,）,3,名学生走进有,4,个大门,的商店，共有,种不同的走法。,（,2,）,3,个不同的球放入,4,个不同的布袋内，共有,种不同的放法。,（,3,）四名学生分配到三个车间劳动,实习，共有,分配方案。,课堂练习,1,、将,5,封信投入,3,个邮筒，则有,种不同投法,(,用数字作答,),2,、已知集合 从,A,、,B,中各取一个元素作为点的坐标，在第一、二象限中的不同点的个数是,( ),A . 8 B . 12 C . 14 D . 16,243,C,拓展性练习,1,、书架上原来并排放着,5,本不同的书，现要插入三本不同的书，那么不同插法的种数是,( ),A . 336 B . 120 C . 24 D . 16,2,、将,3,种作物种植在如图的,5,块试验田里，每块种植一种作物，且相邻的试验田不能种植同一作物，不同的种植方法共有,种,.,A,42,3,、已知集合,A=a,1,a,2,a,3,a,4,集合,B=b,1,b,2,其中,a,i,b,j,均为实数,(1),从集合,A,到集合,B,能构成多少个不同的映射？,(2),能构成多少个以集合,A,为定义域,以集合,B,为值域的不同函数,?,16,14,课堂小结,较复杂的分步问题，后面的步骤可能要受前面步骤的制约；,解决一个较复杂问题,可能要综合分类与分步，一般是先分类，再在每一类中考虑分类与分步；,对于有“特殊元素”的问题，分类和分步时一般可从特殊元素出发考虑，即“特殊优先原则”；,科学、规范、有序的思维方法的培养从正确书写解题过程开始！,作业布置,:,1.,同室,4,人各写,1,张贺年卡,先集中起来,然后每人从中各拿,1,张别人送出的贺年卡,则,4,张贺年卡不同的分配方式有（ ）,A,6,种,B,9,种,C,11,种,D,23,种,B,探究与拓展,方法一,:,树型图,甲,乙,丙,丁,2,1 3 4,4 4 1,3 1 3,3,1 4 4,4 2 1,2 1 2,4,1 3 3,2 1 2,3 2 1,四名同学分别为,:,甲、乙、丙、丁，,所写贺卡依次为,1,，,2,，,3,，,4,方法二,:,采用,”,分步,”,处理法,第一步,:,甲先拿，按规定甲可拿,2,，,3,，,4,当中的 一张，有,3,种方法。,第二步：让与甲取走的卡片相对应的人来拿， 有,3,种拿法,.(,例如甲拿的是,2,则乙有,3,种拿法,.),第三步,:,让剩余的两个人拿,都均有,1,种拿法,.,四名同学分别为,:,甲、乙、丙、丁，,所写贺卡依次为,1,，,2,，,3,，,4,总的方法数,N=3x3x1x1=9,2.,自然数,630,有多少个正约数？,分析：,630,23,2,57,其正约,数的结构式为,其中,可取,0,，,1,；,可取,0,，,1,，,2,；,可取,0,，,1,；,可取,0,，,1,；,即在,、,、,、,所形成的取值,集合中，各取一个元素填入上式，,就得,630,的一个约数。由乘法原理，,得,N= 2322=24.,3.,如图示,从,A,地到,B,地有,3,条不同的道路,从,B,地到,C,地有,4,条不同的道路,从,A,地不经,B,地直接到,C,地有,2,条不同的道路,.,求：,(1),从,A,地到,C,地共有多少种不同的走法？,(2),从,A,地到,C,地再回到,A,地有多少种不同的走法,？,(3),从,A,地到,C,地再到,A,地,但回来时要走与去时,不同,的道路,有多少种不同的走法？,(4),从,A,地到,C,地再到,A,地,但回来时要走与去时,完全不同,的道路,有多少种不同的走法？,C,B,A,解法分析,(1),从,A,地到,C,地的走法可分为两类,:,一类经过,B,另一类不经过,B,则不同的走法总数为：,3,4,+,2=14,种；,(2),从,A,地到,C,地再回到,A,地不同的走法,可分为两大步：,第一步,去,第二步,回,则不同的走法总数为,:,1414=196,种,(3),该事件的过程与,(2),一样可分为两大步,但不同的是第二步即回来的走法比去时的走法少一种,则不同的走法总数为,1413=182,种,(4),该事件同样分去与回两大步，但需对去时的各类走法分别讨论,:,若去使用第一类走法,则回来时用第二类走法或用第一类中的部分走法即第一类中的两步各去掉,1,种走法,则走法数为：,34(2+32)=96,种,若去使用第二类走法,则回来时用第一类走法或用第二类中的另一种走法,则走法数为,2(43+1)=26,种,故共有的走法总数为：,96+26=122,种,练习,1,、在所有的两位数中，个位数字比十位数字大的两位数有多少个？,2,、,8,本不同的书，任选,3,本分给,3,个同学，每人,1,本，有多少种不同的分法？,3,、将,4,封信投入,3,个不同的邮筒，有多少种不同的投法？,4,、已知,则方程 可表示不同的圆的个数有多少？,课堂练习,5,、已知二次函数 若,则可以得到多少个不同的二次函数？其中图象过原点的二次函数有多少个？图象过原点且顶点在第一象限的二次函数又有多少个？,6.,给程序模块命名，需要用,3,个字符，其中首个字符要求用字母,AG,或,UZ,，,后两个要求用数字,1,9,，问最多可以给多少个程序命名？,分析：,要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。,解：,首字符共有,7+6,13,种不同的选法，,答：,最多可以给,1053,个程序命名。,中间字符和末位字符各有,9,种不同的选法,根据分步计数原理，最多可以有,1399,1053,种不同的选法,课堂练习,7,.,核糖核酸（,RNA,）分子是在生物细胞中发现的化学成分，一个,RNA,分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据，总共有个不同的碱基，分别用,A,，,C,，,G,，,U,表示，在一个,RNA,分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类,RNA,分子由,100,个碱基组成，那么能有多少种不同的,RNA,分子？,课堂练习,8.,电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有,0,或,1,两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问,（,1,）一个字节（,8,位）最多可以表示多少个不同的字符？,（,2,）计算机汉字国标码（,GB,码）包含了,6763,个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,第,1,位,第,2,位,第,3,位,第,8,位,2,种,2,种,2,种,2,种,如,00000000,，,10000000,，,11111111.,课堂练习,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,9.,计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组,成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，,以减少测试次数吗？,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,分析：,整个模块的任意一条路径都分两步完成,：第,1,步是从开始执行到,A,点；第,2,步是从,A,点执行到结束。而第步可由子模块,1,或子模块,2,或子模块,3,来完成；第二步可由子模块,4,或子模块,5,来完成。因此，分析一条指令在整个模块的执行路径需要用到两个计数原理。,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,再测试各个模块之间的信息交流是否正常，需要测试的次数为：,3*2=6,。,如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就正常。,这样，测试整个,模块的次数就变为,172+6=178,（次）,2,）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块。这样，他可以先分别单独测试,5,个模块，以考察每个子模块的工作是否正常。总共需要的测试次数为：,18+45+28+38+43=172,。,10.,随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个字母必须合成一组出现，个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照,?,课堂练习,课堂练习,11,、乘积,展开后共有几项？,12,、某商场有,6,个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？,3,.,如图,该电路,从,A,到,B,共有多少条不同的线路可通电？,A,B,课堂练习,所以,根据分类原理,从,A,到,B,共有,N = 3 + 1 + 4 = 8,条不同的线路可通电。,在解题有时既要分类又要分步。,解,:,从总体上看由,A,到,B,的通电线路可分三类,第一类, m,1,= 3,条,第二类, m,2,= 1,条,第三类, m,3,= 22 = 4,条,