资源简介

(共14张PPT)
第五章 计数原理
5.1.3 课时2 基本计数原理的综合应用
1.会综合应用分类加法计数原理和分步乘法计数原理解决问题.
分类加法计数原理 分步乘法计数原理
相同点 区别
注意
都是用来计算“完成一件事”的不同方法种数的问题
类类独立，不重不漏
步步相依，步骤完整
分类完成，类类相加
分步完成，步步相乘
任何一类中的任何一种方法都能独立完成这件事
只有依次完成每一个步骤，才能完成这件事（每步中的每一种方法不能独立完成这件事）
例1：计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路(即程序从开始到结束的路线)，以便知道需要提供多少个测试数据. 一般地，一个程序模块由许多子模块组成，如图，这是一个具有许多执行路径的程序模块.
（1）这个程序模块有多少条执行路径？
（2）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？
开始
子模块1
18条执行路径
子模块3
28条执行路径
子模块2
45条执行路径
子模块5
43条执行路径
子模块4
38条执行路径
结束
A
分析：整个模块的任意一条执行路径都分两步完成：
第1步是从开始执行到A点；第2步是从A点执行到结束.
第1步可由子模块1、子模块2、子模块3中任何一个来完成；
第2步可由子模块4、子模块5中任何一个来完成.
因此，分析一条指令在整个模块的执行路径需要用到两个计数原理.
开始
子模块1
18条执行路径
子模块3
28条执行路径
子模块2
45条执行路径
子模块5
43条执行路径
子模块4
38条执行路径
结束
A
解：（1）由分类加法计数原理，子模块1、子模块2、
子模块3中的子路径条数共为18 + 45 + 28 = 91条；
子模块4、子模块5中的子路径条数共为38 + 43 = 81条；
由分步乘法计数原理，整个模块的执行路径条数共为 91×81 = 7371条.
（2）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块；
这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常；
总共需要的测试次数为 18 + 45 + 28 + 38 + 43 = 172.
再测试各个模块之间的信息交流是否正常，需要测试的次数为：3×2 = 6.
如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常.
这样，测试整个模块的次数就变为 172 + 6 = 178（次）.
例2：通常，我国民用汽车号牌的编码由两部分组成：第一部分为由汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代码，第二部分为由阿拉伯数字和英文字母组成的序号. 其中，序号的编码规则为：
（1）由 10 个阿拉伯数字和除 O、I 之外的 24 个英文字母组成；
（2）最多只能有 2 个英文字母.
如果某地级市发牌机关采用 5 位序号编码，
那么这个发牌机关最多能发放多少张汽车号牌？
解：由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.
根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母.
（1）当没有字母时，序号的每一位都是数字.
确定一个序号可以分5个步骤，每一步都可以从10个数字中选1个，各有10种选法.
根据分步乘法计数原理，这类号牌张数为：10×10×10×10×10 = 10000.
（2）当有1个字母时，这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位，这类序号可以分为五个子类.
当第1位是字母时，分5个步骤确定一个序号中的字母和数字：
第1步，从24个字母中选1个放在第1位，有24种选法；
第2~5步都是从10个数字中选1个放在相应的位置，各有10种选法.
根据分步乘法计数原理，号牌张数为24×10×10×10×10 = 240000.
同样，其余四个子类号牌也各有240000张.
根据分类加法计数原理，这类号牌张数一共为240000 + 240000 + 240000 + 240000 + 240000 = 1200000.
（3）当有2个字母时，根据这2个字母在序号中的位置，可以将这类序号分为
十个子类：(1，2)，(1，3)，(1，4)，(1，5)；(2，3)，(2，4)，(2，5)；(3，4)，
(3，4)；(4，5)；
当第1位和第2位是字母时，分5个步骤确定一个序号中的字母和数字：
第1~2步都是从24个字母中选1个分别放在第1位、第2位，各有24种选法；
第3~5步都是从10个数字中选1个放在相应的位置，各有10种选法；
根据分步乘法计数原理，号牌张数为 24×24×10×10×10 =576000；
同样，其余九个子类号牌也各有576000张，则这类号牌张数一共为576000x10=5760000张.
综合（1）（2）（3），根据分类加法计数原理，这个发牌机关最多能发放的汽车号牌张数为100000 + 1200000 + 5760000 = 7060000.
1. 三个比赛项目，六人报名参加.
（1）每人参加一项有多少种不同的方法？
（2）每项１人，且每人至多参加一项，有多少种不同的方法？
（3）每项１人，每人参加的项数不限，有多少种不同的方法？
2.如图所示，一环形花坛分成 A，B，C，D 四块，现有四种不同的花供选种，要求在每块里只能种一种花，且相邻的两块需要种不同的花，则种法的种数共有 (　　) 种.
A．96 B．84 C．60 D．48
解：依次种A，B，C，D 4块，当C与A种同一种花时，有4×3×1×3 = 36(种)种法；当C与A所种的花不同时，有4×3×2×2 = 48(种)种法．由分类加法计数原理知，不同的种法种数为36 + 48 = 84.
B
用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点：（1）要完成的“一件事”是什么；（2）需要分类还是需要分步.
分类要做到“不重不漏”；分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数.
分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务；分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数.(共11张PPT)
第五章 计数原理
5.1.3 课时1 基本计数原理的简单应用
1.进一步理解分类加法计数原理和分步乘法计数原理的区别.
2.会正确应用这两个计数原理计数.
1.分类加法计数原理：
完成一件事有两类不同方案，在第 1 类方案中有 m 种不同方法，在第 2 类方案中有 n 种不同方法，那么完成这件事共有 N = m + n 种不同方法.
2.分步乘法计数原理：
完成一件事需要两个步骤，做第 1 步有 m 种不同方法，做第 2 步有 n 种不同方法，那么完成这件事共有 N = m×n 种不同方法.
问题：现有高一年级的学生3名，高二年级的学生5名，高三年级的学生4名，问：（1）从中任选 1 人参加接待外宾的活动，有多少种不同的选法？
（2）从3个年级学生中各选1人参加接待外宾活动，有多少种不同的选法？
分析：（1）“要完成的一件事”是什么？（从3个年级的学生中任选1人）
如何完成？（分类）
解：第1类：选一名高一年级的学生，m1 = 3种；
第2类：选一名高二年级的学生，m2 = 5种；
第3类：选一名高三年级的学生，m3 = 4种；
N = m1 + m2 + m3 = 3 + 5 + 4 = 12
问题：现有高一年级的学生3名，高二年级的学生5名，高三年级的学生4名，问：（1）从中任选 1 人参加接待外宾的活动，有多少种不同的选法？
（2）从3个年级学生中各选1人参加接待外宾活动，有多少种不同的选法？
分析：（2）“要完成的一件事”是什么？（从3个年级的学生中各选1人）
如何完成？（分步）
解：第1步：选一名高一年级的学生，m1 = 3种；
第2步：选一名高二年级的学生，m2 = 5种；
第3步：选一名高三年级的学生，m3 = 4种；
N = m1 × m2 × m3 = 3 × 5 × 4 = 60
例1：要从甲、乙、丙 3 幅不同的画中选出 2 幅，分别挂在左、右两边墙上的指定位置，共有多少种不同的挂法？
解：第1步：从3幅画中选1幅挂在左边墙上，有3种选法；
第2步：从剩下的2幅画中选1幅挂在右边墙上，有2种选法；
所以共有 N = 3×2 = 6 种挂法.
分析：1. 要完成的一件事：选出 2 幅画，分别挂在左、右两边墙上；
2. 如何完成：分步；
左边
右边
甲
乙
丙
乙
丙
甲
丙
甲
乙
你还能给出不同的解法吗？
例2：给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U～Z，后两个字符要求用数字1~9，最多可以给多少个程序模块命名？
分析：要完成的一件事：给程序模块命名；如何完成：分步；
解：第1步：选首字符，m1 = 7 + 6 = 13 种；
第2步：选中间字符，m2 = 9 种；
第3步：选最后一个字符，m3 = 9 种；
N = m1×m2×m3 = 13×9×9 = 1053
注意：后面两个字符可以重复 !
既有分类加法计数原理又有分步乘法计数原理，两者要综合应用
例3：电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制。为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成.
（1）一个字节（8位）最多可以表示多少个不同的字符
第1位
第2位
2种
第3位
第8位
......
2种
2种
2种
N = 28 = 256
分析：要完成的一件事：确定一个字节各二进制上的数字；如何完成：分步；
（2）计算机汉字国标码包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示
分析：
第1位
第2位
2种
第3位
第8位
......
2种
2种
2种
256×256 = 65536
第1位
第2位
2种
第3位
第8位
......
2种
2种
2种
解：由于题目要求是奇数，那么对于此三位数可以分成两种情况；奇偶奇，偶奇奇；
如果是第一种奇偶奇的情况，可以从个位开始分析(3种情况)，之后十位(2种情况)，最后百位(2种情况)，共12种；
如果是第二种情况偶奇奇：个位(3种情况)，十位(2种情况)，百位(不能是0，一种情况)，共6种，因此总共有12 + 6 = 18(种)情况．
故选B.
　B
1. 从0，2中选一个数字，从1，3，5中选两个数字，组成无重复数字的三位数，其中奇数的个数为(　　)
A．24 B．18 C．12 D．6
用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点：一、要完成的“一件事”是什么;二、需要分类还是分步.
分类要做到“不重不漏”，分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数.
分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务，分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数.

展开更多......

收起↑