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

《分类计数原理与分步计数原理PPT课件》由会员分享，可在线阅读，更多相关《分类计数原理与分步计数原理PPT课件（54页珍藏版）》请在金锄头文库上搜索。

1、.,1,.,2,1、分类加法计数原理：完成一件事，有n类办法，在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法在第n类办法中有mn种不同的方法.那么完成这件事共有 种不同的方法.,2、分步乘法计数原理：完成一件事，需要分成n个步骤，做第1步有m1种不同的方法,做第2步有m2种不同的方法，做第n步有mn种不同的方法.那么完成这件事共有 种不同的方法.,回答的都是有关做一件事的不同方法种数的问题,.,3,联系,区别一,完成一件事情共有n类 办法，关键词是“分类”,完成一件事情,共分n个 步骤，关键词是“分步”,区别二,每类办法都能独立完成这件事情。它是独立的、一次的、且每次得到的

2、是最后结果，只须一种方法就可完成这件事。,每一步得到的只是中间结果， 任何一步都不能能独立完成 这件事情，缺少任何一步也 不能完成这件事情，只有每 个步骤完成了，才能完成这 件事情。,分类计数原理和分步计数原理，回答的都是关于 完成一件事情的不同方法的种数的问题。,区别三,各类办法是互相独立的,各步之间是互相关联的,分类计数与分步计数原理的区别和联系：,.,4,例1. 五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多少种？,解：（1）5名学生中任一名均可报其中的任一项，因此每个学生都有4种报名方法，5名学生都报了项目才能算完成这

3、一事件故报名方法种数为44444= 种 .,（2）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有5种故有n=5= 种 .,.,5,例2 要从甲、乙、丙3名工人中选出2名分别上白班和晚班，有多少种不同的选法？,解：要排好一个白班和晚班须分两个步骤来完成:第1步是从甲、乙、丙3人中选1人上白班,有3种选法:第2步是选1人上晚班,但这时只能从剩下的2人中选1人,有2种方法,根据分步计数原理,不同的选法种数是：32=6.,具体排法,白班 晚班,白班 晚班,甲 乙,甲 丙,乙 甲,丙 乙,丙 甲,乙 丙,.,6,例3 在所有的两位数中，个位数字大于十位数字的两位数

4、共有多少个？,分析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 (个).,.,7,变式：从1到200的自然数中,各个 数位上都不含8的自然数有多少个？,分三类:第一类：一位数中除8以外的数符 合要求，共 个,8,第二类：两

5、位数中十位、个位都 不含8的数,有 个.,98=72,99+1=82,第三类:三位数中符合要求的数,共有 个.,则满足条件的总的自然数有: N=8+98+99+1=162个.,.,8,例4某艺术组有9人，每人至少会钢琴和小号中的一种乐器，其中有7人会钢琴，3人会小号，从中选出会钢琴与会小号的各1人，有多少种不同的选法？,解：由题意可知，艺术组9人中，只会钢琴的有6人，只会小号的有2人，既会钢琴又会小号的有1人(可把该人称为多面手)因此，选出会钢琴与会小号的各1人可分两类：,第一类：不选多面手，分2步：第一步从只会钢琴的6人中选1人，有6种选法；第二步从只会小号的2人中选1人，有2种选法，因此，

6、共有62=12(种).,第二类：选多面手，分2步：第一步从多面手中选，有1种选法；第二步从非多面手中选，有8种选法，因此，共有18=8(种).,故共有12+8=20(种).,注：先分类，后分步.,特殊元素优先考虑法.,.,9,例5 用红、黄、蓝不同颜色旗各3面，每次升一面、两面、三面在某一旗杆上纵向排列，共可以组成多少种不同的信号？,解：不同的信号可分为三类： 第一类：升一面旗，又可分三类，有1+1+1=3种 第二类：升两面旗，可分两步，有33=9种 第三类：升三面旗，可分三步，有333=27种 故共有 3+9+27=39(种),评注：先分类，再在每一类中分类或分步.,.,10,例6 如图，要

7、给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？,（染色问题）,.,11,.,12,解: 按地图A、B、C、D四个区域依次分四步完成, 第一步, m1 = 3 种, 第二步, m2 = 2 种, 第三步, m3 = 1 种, 第四步, m4 = 1 种, 根据乘法原理, 得到不同的涂色方案种数共有: N = 3 2 11 = 6 种.,例6 如图，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,思考:若有4种或5种颜

8、色可供选择,结果分别如何？,提示:涂色种数分别是 : 4322 = 48种； 5433 = 180种；,.,13,43,例7 (1)将3封信投入4个不同的信箱， 共有 种不同的投法。,.,14,例7 （2）由4名学生争夺3个比赛 项目的冠军，冠军获得者共有多少种 可能？,住店法: 解决“允许重复排列问题”要注意区分两类 元素：一类元素可以重复，另一类不能重复.把不能重 复的元素看作“客”,能重复的元素看作“店”, 再利用分步计数原理直接求解的方法称为“住店法”.,.,15,变式：（1）3名学生走进有4个大门 的商店，共有 种不同的走法。 （2）3个不同的球放入4个不同的布袋内，共有 种不同的放

9、法。 （3）四名学生分配到三个车间劳动 实习，共有 分配方案。,.,16,课堂练习,243,C,.,17,拓展性练习,1、书架上原来并排放着5本不同的书，现要插入三本不同的书，那么不同插法的种数是( ),A . 336 B . 120 C . 24 D . 16,2、将3种作物种植在如图的5块试验田里，每块种植一种作物，且相邻的试验田不能种植同一作物，不同的种植方法共有 种.,A,42,3、已知集合A=a1,a2,a3,a4,集合B=b1,b2,其中ai ,bj 均为实数, (1)从集合A到集合B能构成多少个不同的映射？ (2)能构成多少个以集合A为定义域,以集合B为值域的不同函数?,16,1

10、4,.,18,课堂小结,较复杂的分步问题，后面的步骤可能要受前面步骤的制约； 解决一个较复杂问题,可能要综合分类与分步，一般是先分类，再在每一类中考虑分类与分步； 对于有“特殊元素”的问题，分类和分步时一般可从特殊元素出发考虑，即“特殊优先原则”； 科学、规范、有序的思维方法的培养从正确书写解题过程开始！,.,19,作业布置:,1.同室4人各写1张贺年卡,先集中起来,然后每人从中各拿1张别人送出的贺年卡,则4张贺年卡不同的分配方式有（ ） A6种 B9种 C11种D23种,B,探究与拓展,.,20,方法一:树型图,甲 乙 丙 丁,2,1 3 4,4 4 1,3 1 3,3,1 4 4,4 2

11、1,2 1 2,4,1 3 3,2 1 2,3 2 1,四名同学分别为:甲、乙、丙、丁， 所写贺卡依次为1，2，3，4,.,21,方法二:采用”分步”处理法 第一步:甲先拿，按规定甲可拿2，3，4当中的 一张，有3种方法。 第二步：让与甲取走的卡片相对应的人来拿， 有3种拿法.(例如甲拿的是2,则乙有3种拿法.) 第三步:让剩余的两个人拿,都均有 1种拿法.,四名同学分别为:甲、乙、丙、丁， 所写贺卡依次为1，2，3，4,总的方法数 N=3x3x1x1=9,.,22,2.自然数630有多少个正约数？,分析：63023257,其正约 数的结构式为,其中可取0，1；可取0，1，2； 可取0，1；可

12、取0，1；,即在、所形成的取值 集合中，各取一个元素填入上式， 就得630的一个约数。由乘法原理， 得N= 2322=24.,.,23,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地,但回来时要走与去时完全不同的道路,有多少种不同的走法？,.,24,解法分析 (1)从A地到C地的走法可分为两类:一类经过B,另一类不经过B,则不

13、同的走法总数为：34+2=14种； (2)从A地到C地再回到A地不同的走法可分为两大步： 第一步去,第二步回,则不同的走法总数为:1414=196种 (3)该事件的过程与(2)一样可分为两大步,但不同的是第二步即回来的走法比去时的走法少一种,则不同的走法总数为1413=182种,(4)该事件同样分去与回两大步，但需对去时的各类走法分别讨论:若去使用第一类走法,则回来时用第二类走法或用第一类中的部分走法即第一类中的两步各去掉1种走法,则走法数为： 34(2+32)=96种 若去使用第二类走法,则回来时用第一类走法或用第二类中的另一种走法,则走法数为2(43+1)=26种 故共有的走法总数为：96

14、+26=122种,.,25,练习,1、在所有的两位数中，个位数字比十位数字大的两位数有多少个？,2、8本不同的书，任选3本分给3个同学，每人1本，有多少种不同的分法？ 3、将4封信投入3个不同的邮筒，有多少种不同的投法？ 4、已知 则方程 可表示不同的圆的个数有多少？,.,26,课堂练习,5、已知二次函数 若 则可以得到多少个不同的二次函数？其中图象过原点的二次函数有多少个？图象过原点且顶点在第一象限的二次函数又有多少个？,.,27,6.给程序模块命名，需要用3个字符，其中首个字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少个程序命名？,分析：要给一个程序模块命名，可以分三个步

15、骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。,解：首字符共有7+613种不同的选法，,答：最多可以给1053个程序命名。,中间字符和末位字符各有9种不同的选法,根据分步计数原理，最多可以有13991053种不同的选法,课堂练习,.,28,7.核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据，总共有个不同的碱基，分别用A，C，G，U表示，在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由100个碱基组成，

16、那么能有多少种不同的RNA分子？,课堂练习,.,29,8.电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问 （1）一个字节（8位）最多可以表示多少个不同的字符？ （2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,如00000000，10000000， 11111111.,课堂练习,.,30,9.计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条