- 185.00 KB
- 2021-06-21 发布
- 1、本文档由用户上传,淘文库整理发布,可阅读全部内容。
- 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,请立即联系网站客服。
- 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细阅读内容确认后进行付费下载。
- 网站客服QQ:403074932
分类加法计数原理与分步乘法计数原理
2
分类计数原理
:
完成一件事
,
有
n
类方式
,
在第
1
类方式中有
m
1
种不同的方法
,
在第
2
类方式中有
m
2
种不同的方法
,
…
,
在第
n
类方式中有
m
n
种不同的方法
,
那么完成这件事共有
N=m
1
+m
2
+
…
+m
n
种不同的方法
分步计数原理
:
完成一件事
,
需要分成
n
个步骤
,
做第一步有
m
1
种不同的方法
,
做第
2
步有
m
2
种不同的方法
,
…
,
做第
n
步有
m
n
种不同的方法
,
那么完成这件事共有
N=m
1
×m
2
×
…
×m
n
种不同的方法
分类加法计数原理是一次性能够完成任务
,
各种方法之间没有顺序
;
而分布乘法计数原理 是不能一次性能够完成任务
,
需要分多步才能完成
,
各步之间是有顺序的
.
巩固复习
1.
两个计数原理
:
2.
两者的区别
:
典例分析
:
例
1
电子元件很容易实现电路的通与断、电位的高与低等两种状态,而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有
0
或
1
两种数字的记数法,即二进制。为了使计算机能够识别字符,需要对字符进行编码,每个字符可以用一个或多个字节来表示,其中字节是计算机中数据存储的最小计量单位,每个字节由
8
个二进制位构成。问:
(
1
)一个字节(
8
位)最多可以表示多少个不同的字符?
(
2
)计算机汉字国标码(
GB
码)包含了
6763
个汉字,一个汉字为一个字符,要对这些汉字进行编码,每个汉字至少要用多少个字节表示?
例
2
计算机编程人员在编写好程序以后需要对程序进行测试
.
程序员需要知道到底有多少条执行路径
(
即程序从开始到结束的路线
),
以便知道需要提供多少个测试数据
.
一般地
,
一个程序模块由许多字模块组成
.
如图
,
它是一个具有许多执行路径的程序模块
.
问
:
这个程序模块有多少条执行路径
?
另外
,
为了减少测试时间
,
程序员需要设法减少测试次数
.
你能帮助程序员设计一个测试方法
,
以减少测试次数吗
?
开始
字模块
1
字模块
2
字模块
3
18
条执行路径
45
条执行路径
28
条执行路径
字模块
4
字 模块
5
38
条执行路径
43
条执行路径
结束
例
3
随着人们生活水平的提高
,
某城市家庭汽车拥有量迅速增长
,
汽车牌照号码需要扩容
.
交通管理部门出台了一种汽车牌照组成办法
,
每一个汽车牌照都必须有
3
个不重复的英文字母和
3
个不重复的阿拉伯数字
,
并且
3
个字母必须合成一组出现
,3
个数字也必须合成一组出现
.
那么这种办法共能给多少两汽车上牌照
?
排数字问题
例
4
用
0,1,2,3,4,5
这六个数字
,
(1)
可以组成多少个各位数字不允许重复的三位的奇数
?
(2)
可以组成多少个各位数字不重复的小于
1000
的自然数
?
(3)
可以组成多少个大于
3000,
小于
5421
且各位数字不允许重复的四位数
?
升华发展
变式
:
1.
将数字
1,2,3,4,
填入标号为
1,2,3,4
的四个方格里
,
每格填一个数字
,
则每个格子的标号与所填的数字均不同的填法有
_____
种
2.
自然数
2520
有多少个正约数?
映射个数问题
:
例
5
设
A={a,b,c,d,e,f},B={x,y,z},
从
A
到
B
共有多少种不同的映射
?
变式
:
(1)6
个人分到
3
个车间
,
共有多少种分发
?
(2)6
个人分工栽
3
棵树
,
每人只栽
1
棵
,
共有多少种不同方案
?
染色问题
:
例
6
有
n
种不同颜色为下列两块广告牌着色
,
要求在
①②
③
④
四个区域中相邻
(
有公共边界
)
区域中不用同一种颜色
.
(1)
若
n=6,
为
(1)
着色时共有多少种方法
?
(2)
若为
(2)
着色时共有
120
种不同方法
,
求
n
①
③
①
④
③
④
② ②
(1) (2)
综合问题
:
例7 若直线方程
ax+by=0
中的
a,b
可以从
0,1,2,3,4
这五个数字中任取两个不同的数字
,
则方程所表示的不同的直线共有多少条
?
1
、要从甲、乙、丙三名工人中选出两名分别上日班和晚班,有多少种不同的选法?
2
、某艺术组有
9
人,每人至少会钢琴和小号中的一种乐器,其中
7
人会钢琴,
3
人会小号,从中选出会钢琴和会小号的各一人,有多少种不同的选法?
3
、用红、黄、蓝不同颜色的旗各三面,每次升一面、两面、三面在某一旗杆上纵向排列,共可以组成多少种不同的信号?
三.课堂练习:
4
、(
1
)
8
张卡片上写着
0,1,2,
…
,7
共
8
个数字,取其中的三张卡片排放在一起,可组成多少个不同的三位数?
(
2
)
4
张卡片的正、反面分别写有
0
与
1
、
2
与
3
、
4
与
5
、
6
与
7
,将其中的
3
张卡片排放在一起,共有多少个不同的三位数?
5
、书架上原来并排放着
5
本不同的书,现要插入三本不同的书,那么不同的插法有多少种?
四
.
课堂小节
用两个计数原理解决计数问题时
,
最重要的是开始计算之前要进行分析
——
需要分类还是分步
.
分类要做到“不重不漏”,分类后再分别对每一类进行计数,最后用分类加法原理求和,得到总数。
分步要做到“步骤完整”
——
完成了所有的步骤,恰好完成任务,步与步之间要相互独立。分步后再计算每一步的方法数,最后根据分布乘法计数原理,把完成每一步的方法相乘,得到总数。
五、作业
1
、同步作业本
2
、课本
P12 A
、
B
两组。
再见
good bye