分类计数原理与分步计数原理ppt课件

1、分类加法计数原理：完成一件事，有n类办法，在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法在第n类办法中有mn种不同的方法.那么完成这件事共有种不同的方法.,2、分步乘法计数原理：完成一件事，需要分成n个步骤，做第1步有m1种不同的方法,做第2步有m2种不同的方法，做第n步有mn种不同的方法.那么完成这件事共有种不同的方法.,回答的都是有关做一件事的不同方法种数的问题,联系,区别一,完成一件事情共有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四个区域依次分四步完成,第一步,m1=3种,第二步,m2=2种,第三步,m3=1种,第四步,m4=1种,根据乘法原理,得到不同的涂色方案种数共有:N=3211=6种.,例6如图，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,思考:若有4种或5种颜色可供选择,结果分别如何？,提示:涂色种数分别是:4322=48种；5433=180种；,43,例7(1)将3封信投入4个不同的信箱，共有种不同的投法。,例7（2）由4名学生争夺3个比赛项目的冠军，冠军获得者共有多少种可能？,住店法:解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复，另一类不能重复.把不能重复的元素看作“客”,能重复的元素看作“店”,再利用分步计数原理直接求解的方法称为“住店法”.,变式：（1）3名学生走进有4个大门的商店，共有种不同的走法。（2）3个不同的球放入4个不同的布袋内，共有种不同的放法。（3）四名学生分配到三个车间劳动实习，共有分配方案。,课堂练习,243,C,拓展性练习,1、书架上原来并排放着5本不同的书，现要插入三本不同的书，那么不同插法的种数是(),A.336B.120C.24D.16,2、将3种作物种植在如图的5块试验田里，每块种植一种作物，且相邻的试验田不能种植同一作物，不同的种植方法共有种.,A,42,3、已知集合A=a1,a2,a3,a4,集合B=b1,b2,其中ai,bj均为实数,(1)从集合A到集合B能构成多少个不同的映射？(2)能构成多少个以集合A为定义域,以集合B为值域的不同函数?,16,14,课堂小结,较复杂的分步问题，后面的步骤可能要受前面步骤的制约；解决一个较复杂问题,可能要综合分类与分步，一般是先分类，再在每一类中考虑分类与分步；对于有“特殊元素”的问题，分类和分步时一般可从特殊元素出发考虑，即“特殊优先原则”；科学、规范、有序的思维方法的培养从正确书写解题过程开始！,作业布置:,1.同室4人各写1张贺年卡,先集中起来,然后每人从中各拿1张别人送出的贺年卡,则4张贺年卡不同的分配方式有（）A6种B9种C11种D23种,B,探究与拓展,方法一:树型图,甲乙丙丁,2,134,441,313,3,144,421,212,4,133,212,321,四名同学分别为:甲、乙、丙、丁，所写贺卡依次为1，2，3，4,方法二:采用”分步”处理法第一步:甲先拿，按规定甲可拿2，3，4当中的一张，有3种方法。第二步：让与甲取走的卡片相对应的人来拿，有3种拿法.(例如甲拿的是2,则乙有3种拿法.)第三步:让剩余的两个人拿,都均有1种拿法.,四名同学分别为:甲、乙、丙、丁，所写贺卡依次为1，2，3，4,总的方法数N=3x3x1x1=9,2.自然数630有多少个正约数？,分析：63023257,其正约数的结构式为,其中可取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地,但回来时要走与去时完全不同的道路,有多少种不同的走法？,解法分析(1)从A地到C地的走法可分为两类:一类经过B,另一类不经过B,则不同的走法总数为：34+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，后两个要求用数字19，问最多可以给多少个程序命名？,分析：要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。,解：首字符共有7+613种不同的选法，,答：最多可以给1053个程序命名。,中间字符和末位字符各有9种不同的选法,根据分步计数原理，最多可以有13991053种不同的选法,课堂练习,7.核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据，总共有个不同的碱基，分别用A，C，G，U表示，在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由100个碱基组成，那么能有多少种不同的RNA分子？,课堂练习,8.电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问（1）一个字节（8位）最多可以表示多少个不同的字符？（2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,如00000000，10000000，11111111.,课堂练习,9.计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？,分析：整个模块的任意一条路径都分两步完成：第1步是从开始执行到A点；第2步是从A点执行到结束。而第步可由子模块1或子模块2或子模块3来完成；第二步可由子模块4或子模块5来完成。因此，分析一条指令在整个模块的执行路径需要用到两个计数原理。,再测试各个模块之间的信息交流是否正常，需要测试的次数为：3*2=6。如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就正常。,这样，测试整个模块的次数就变为172+6=178（次）,2）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块。这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常。总共需要的测试次数为：,18+45+28+38+43=172。,10.随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个