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

1、2021/8/2611.1.2分类计数原理分类计数原理与分步计数原理分步计数原理(二二)2021/8/2621、分类加法计数原理、分类加法计数原理：完成一件事，有：完成一件事，有n类办法，在类办法，在第第1类办法中有类办法中有m1种不同的方法种不同的方法,在第在第2类办法中有类办法中有m2种不同的方法种不同的方法在第在第n类办法中类办法中有有m mn n种不同的方法种不同的方法. .那么完成这件事共有那么完成这件事共有 种不同的方种不同的方法法. .12nNmmm2 2、分步乘法计数原理、分步乘法计数原理：完成一件事，需要分成完成一件事，需要分成n n个步个步骤，做第骤，做第1 1步有步有m

2、m1 1种不同的方法种不同的方法, ,做第做第2 2步有步有m m2 2种不同的种不同的方法方法，做第，做第n n步有步有m mn n种不同的方法种不同的方法. .那么完成这件那么完成这件事共有事共有 种不同的方法种不同的方法. .12nNmmm分类加法计数原理和分步乘法计数原理的分类加法计数原理和分步乘法计数原理的共同点：共同点：不同点：不同点：分类加法计数原理与分类有关，分类加法计数原理与分类有关，分步乘法计数原理与分步有关。分步乘法计数原理与分步有关。回答的都是有关做一件事的不同方法种数的问题回答的都是有关做一件事的不同方法种数的问题2021/8/263 加法原理加法原理 乘法原理乘法原

3、理联系联系区别一区别一完成一件事情共有完成一件事情共有n类类办法，关键词是办法，关键词是“分类分类”完成一件事情完成一件事情,共分共分n个个步骤，关键词是步骤，关键词是“分步分步”区别二区别二每类办法都能每类办法都能独立完独立完成成这件事情。这件事情。它是独立它是独立的、一次的、且每次得到的、一次的、且每次得到的是最后结果，的是最后结果，只须一种只须一种方法就可完成这件事方法就可完成这件事。每一步得到的只是每一步得到的只是中间结果中间结果，任何一步都任何一步都不能能独立完成不能能独立完成这件事情这件事情，缺少任何一步也，缺少任何一步也不能完成这件事情，不能完成这件事情，只有每只有每个步骤完成了

4、，才能完成这个步骤完成了，才能完成这件事情。件事情。分类计数原理和分步计数原理，回答的都是关于分类计数原理和分步计数原理，回答的都是关于完成一件事情的不同方法的种数的问题。完成一件事情的不同方法的种数的问题。区别三区别三各类办法是互相独各类办法是互相独立的立的各步之间是互相关联的各步之间是互相关联的分类计数与分步计数原理的区别和联系：分类计数与分步计数原理的区别和联系：2021/8/264例例1. 1. 五名学生报名参加四项体育比赛，每人五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多夺这

5、四项比赛的冠军，获得冠军的可能性有多少种？少种？ 解：（解：（1）5名学生中任一名均可报其中的任一项，因此每名学生中任一名均可报其中的任一项，因此每个学生都有个学生都有4种报名方法，种报名方法，5名学生都报了项目才能算完成名学生都报了项目才能算完成这一事件故报名方法种数为这一事件故报名方法种数为44444= 种种 .54（2）每个项目只有一个冠军，每一名学生都可能获得）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有其中的一项获军，因此每个项目获冠军的可能性有5种种故有故有n=5= 种种 .452021/8/265白班白班 晚班晚班白班白班 晚班晚班202

6、1/8/2662021/8/267变式：从变式：从1到到200的自然数中的自然数中,各个各个数位上都不含数位上都不含8的自然数有多少个？的自然数有多少个？分三类分三类:第一类：一位数中除第一类：一位数中除8以外的数符以外的数符 合要求，共合要求，共 个个第二类：两位数中十位、个位都第二类：两位数中十位、个位都不含不含8的数的数,有有 个个.第三类第三类:三位数中符合要求三位数中符合要求的数的数,共有共有 个个.则满足条件的总的自然数有则满足条件的总的自然数有:2021/8/2682021/8/2692021/8/26102021/8/26112021/8/26122021/8/261343 (

7、1)将将3封信投入封信投入4个不同的信箱，个不同的信箱，共有共有 种不同的投法。种不同的投法。2021/8/2614 （2）由）由4名学生争夺名学生争夺3个比赛个比赛项目的冠军，冠军获得者共有多少种项目的冠军，冠军获得者共有多少种可能？可能？34N2021/8/2615变式：变式：（1）3名学生走进有名学生走进有4个大门个大门的商店，共有的商店，共有 种不同的走法。种不同的走法。 （2）3个不同的球放入个不同的球放入4个不同的布袋个不同的布袋内，共有内，共有 种不同的放法。种不同的放法。 （3）四名学生分配到三个车间劳动）四名学生分配到三个车间劳动 实习，共有实习，共有 分配方案。分配方案。2

8、021/8/26161、将、将5封信投入封信投入3个邮筒，则有个邮筒，则有 种不同投种不同投法法2、已知集合、已知集合 从从A、B中各取一个元素作为点的坐标，在第一、二象限中的不中各取一个元素作为点的坐标，在第一、二象限中的不同点的个数是同点的个数是( )12 3 435 6AB ， ， ， ， ， ，A . 8 B . 12 C . 14 D . 16243C2021/8/2617A . 336 B . 120 C . 24 D . 16A4216142021/8/26182021/8/26191.同室同室4人各写人各写1张贺年卡张贺年卡,先集中起来先集中起来,然后每然后每人从中各拿人从中各

9、拿1张别人送出的贺年卡张别人送出的贺年卡,则则4张贺年张贺年卡不同的分配方式有（卡不同的分配方式有（ ） A6种种 B9种种 C11种种 D23种种B2021/8/2620甲甲乙乙丙丙丁丁21 3 44 4 13 1 331 4 44 2 12 1 241 3 32 1 23 2 1四名同学分别为四名同学分别为:甲、乙、丙、丁，甲、乙、丙、丁，所写贺卡依次为所写贺卡依次为1，2，3，42021/8/2621第一步第一步:甲先拿，按规定甲可拿甲先拿，按规定甲可拿2，3，4当中的当中的 一张，有一张，有3种方法。种方法。 第二步：让与甲取走的卡片相对应的人来拿，第二步：让与甲取走的卡片相对应的人来

10、拿， 有有3种拿法种拿法.(例如甲拿的是例如甲拿的是2,则乙有则乙有3种拿法种拿法.) 第三步第三步:让剩余的两个人拿让剩余的两个人拿,都均有都均有 1种拿法种拿法.四名同学分别为四名同学分别为:甲、乙、丙、丁，甲、乙、丙、丁，所写贺卡依次为所写贺卡依次为1，2，3，4总的方法数总的方法数 2021/8/26222.自然数自然数630有多少个正约数？有多少个正约数？分析：分析：,其正约其正约数的结构式为数的结构式为6302357即在、所形成的取值所形成的取值集合中，各取一个元素填入上式，集合中，各取一个元素填入上式，就得就得630的一个约数。由乘法原理，的一个约数。由乘法原理， 得得2021/

11、8/2623CBA2021/8/26242021/8/26251、在所有的两位数中，个位数字比十位数、在所有的两位数中，个位数字比十位数字大的两位数有多少个？字大的两位数有多少个？2、8本不同的书，任选本不同的书，任选3本分给本分给3个同学，每个同学，每人人1本，有多少种不同的分法？本，有多少种不同的分法？3、将、将4封信投入封信投入3个不同的邮筒，有多少种不个不同的邮筒，有多少种不同的投法？同的投法？4、已知、已知则方程则方程 可表示不同的圆的可表示不同的圆的个数有多少？个数有多少？3,4,6,1,2,7,8,8,9abr222()()xaybr2021/8/26265、已知二次函数、已知二

12、次函数 若若 则可以得到多少个则可以得到多少个不同的二次函数？其中图象过原点的二次函不同的二次函数？其中图象过原点的二次函数有多少个？图象过原点且顶点在第一象限数有多少个？图象过原点且顶点在第一象限的二次函数又有多少个？的二次函数又有多少个？2.yaxbxc, , 3, 2,0,1,2,3.a b c 2021/8/26276.给程序模块命名，需要用给程序模块命名，需要用3个字符，其中首个字符个字符，其中首个字符要求用字母要求用字母AG或或UZ，后两个要求用数字，后两个要求用数字19，问最多可以给多少个程序命名？问最多可以给多少个程序命名？分析：分析：要给一个程序模块命名，可以分三个步骤：第一

13、步，要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。选首字符；第二步，先中间字符；第三步，选末位字符。解：解：首字符共有首字符共有7+613种不同的选法，种不同的选法，答：答：最多可以给最多可以给10531053个程序命名。个程序命名。中间字符和末位字符各有中间字符和末位字符各有9种不同的选法种不同的选法根据分步计数原理，最多可以有根据分步计数原理，最多可以有13991053种不同的选法种不同的选法2021/8/26287.核糖核酸（核糖核酸（RNA）分子是在生物细胞中发现的化学成）分子是在生物细胞中发现的化学成分，一个分，一个RNA分子是一个有

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

15、元件很容易实现电路的通与断、电位的高与底等两种状电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有了每一位只有0或或1两种数字的计数法，即二进制，为了使计算两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问单位，每个字节由个二进制位构成，问

16、（1）一个字节（）一个字节（8位）最多可以表示多少个不同的字符？位）最多可以表示多少个不同的字符？（2）计算机汉字国标码（）计算机汉字国标码（GB码）包含了码）包含了6763个汉字，一个汉个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？少个字节表示？第1位第2位第3位第8位2种2种2种2种如如00000000，10000000，11111111.2021/8/2630开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A9.计算机编程人员在编

17、写计算机编程人员在编写好程序以后要对程序进行好程序以后要对程序进行测试。程序员需要知道到测试。程序员需要知道到底有多少条执行路（即程底有多少条执行路（即程序从开始到结束的线），序从开始到结束的线），以便知道需要提供多少个以便知道需要提供多少个测试数据。一般的，一个测试数据。一般的，一个程序模块又许多子模块组程序模块又许多子模块组成，它的一个具有许多执成，它的一个具有许多执行路径的程序模块。问：行路径的程序模块。问：这个程序模块有多少条执这个程序模块有多少条执行路径？另外为了减少测行路径？另外为了减少测试时间，程序员需要设法试时间，程序员需要设法减少测试次数，你能帮助减少测试次数，你能帮助程序员

18、设计一个测试方式，程序员设计一个测试方式，以减少测试次数吗？以减少测试次数吗？2021/8/2631开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A分析：分析：整个模块的任整个模块的任意一条路径都分两步意一条路径都分两步完成完成：第：第1步是从开步是从开始执行到始执行到A点；第点；第2步步是从是从A点执行到结束。点执行到结束。而第步可由子模块而第步可由子模块1或子模块或子模块2或子模块或子模块3来完成；第二步可由来完成；第二步可由子模块子模块4或子模块或子模块5来来完成。因此，分析一完成。因此，分析一条指令在整个模块的条指

19、令在整个模块的执行路径需要用到两执行路径需要用到两个计数原理。个计数原理。2021/8/2632开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A再测试各个模块之间的信再测试各个模块之间的信息交流是否正常，需要测息交流是否正常，需要测试的次数为：试的次数为：3*2=6。如果每个子模块都正常工如果每个子模块都正常工作，并且各个子模块之间作，并且各个子模块之间的信息交流也正常，那么的信息交流也正常，那么整个程序模块就正常。整个程序模块就正常。这样，测试整个这样，测试整个模块的次数就变为模块的次数就变为 172+6=178（次）（

20、次）2）在实际测试中，程序）在实际测试中，程序员总是把每一个子模块看员总是把每一个子模块看成一个黑箱，即通过只考成一个黑箱，即通过只考察是否执行了正确的子模察是否执行了正确的子模块的方式来测试整个模块。块的方式来测试整个模块。这样，他可以先分别单独这样，他可以先分别单独测试测试5个模块，以考察每个模块，以考察每个子模块的工作是否正常。个子模块的工作是否正常。总共需要的测试次数为：总共需要的测试次数为：18+45+28+38+43=172。2021/8/263310.随着人们生活水平的提高，某城市家庭汽车拥有量迅速增随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个字母必须合成一组出现，和个不重复的阿拉伯数字，并且个字母必须合成一组出现，个数字也必须合成一组出现，那么这种办法共能给多少辆汽个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照车上牌照?2021/8/263411、乘积、乘积 展开后共有几项？