《计数原理》PPT课件

1.1计数原理
第一课时
.
1
问题的背景：
在日常生活、生产中存在着大量的计数问 题，比如完成一件事情的方法的种数或者 某类事物出现的所有的可能的结果等等。
在数目不多的情况下，我们可以通过列举 的方法，把各种可能的结果一一列举出来， 可以求出相应的种数。
但当这个数很大时，列举的方法就很难实 施了。所以我们关心的是如何能不通过一 个一个地数而确定出这个数。
计算机汉字国标码（GB码）包含了6763个汉字， 一个汉字为一个字符，要对这些汉字进行编码， 每个汉字至少要用多少个字节表示？
你知道为什么26个英文字母与阿拉伯数字都是用1个字
节表示了吗？
.
17
练习：集合的子集的个数问题：
问题1：集合S＝{a1}的子集有几个？ 问题2：集合S＝{a1，a2}的子集有几个？ 问题3：集合S＝{a1，a2，a3}的子集有 几个？
.
6
例1、在填写高考志愿表时，一名高中毕业生 了解到，A,B两所大学各有一些自己感兴趣的 强项专业，具体情况如下：
A大学 生物学 化学
B大学 数学 会计学
问题中描述 的“一件事”
是什么
医学
信息技术学
物理学
法学
工程学
从中只能选择一个专业，. 有多少种选法？ 7
例2、设某班有男生30名，女生24名。现要从 中选出男、女生各一名代表班级参加比赛，共 有多少种不同的选法？
.
2
问题1：用一个大写的英文字母或一位阿拉伯 数字给教室里的座位编号，总共能够编出多 少种不同的号码？
问题2：用前6个大写英文字母和1～9九个阿 拉伯数字，以A1,A2,……B1,B2……的方式 给教室的座位编号，共能编出多少个不同的 号码？
你能说说上述两个问题的区别在哪里？
.
3
问题3:从甲地到乙地，可以乘火车，或乘汽 车，一天中火车有3班，汽车有2班，那么一 天中，乘坐这些交通工具从甲地到乙地共有 多少种方法？
要完成的“一件事” 是什么
.
8
思考：两个计数原理有什么相同点？什么不同点？
相同点：是有关做一件事的不同方法种数的问题 区别： 1、分类计数原理针对的是“分类”，其中各种方
法相互独立，用其中任何一种方法都可以做完这 件事。 2、分步计数原理针对的是“分步”，各个步骤中 的方法互相依存，只有各个步骤都完成才算做完 这件事。
例5、给程序模块命名，需要用3个字符，其中 首字符要求用字母A~G或U~Z，后两个要求用 数字1～9.问最多可以给多少个程序命名？
.
11
例6、核糖核酸（RNA）分子是在生 物细胞中发现的化学成分，一个RNA 分子是一个有着数百个甚至数千个位 置的长链，长链中每一个位置上都由 一种称为碱基的化学成分所占据。总 共有4种不同的碱基，分别用A，C， G，U表示。在一个RNA分子中，各 种碱基能够以任意次序出现，所以在 任意一个位置上的碱基与其他位置上 的碱基无关。假设有一类RNA分子由 100个碱基组成，那么能有多少中不 同的RNA分子？
分步乘法计数原理：完成一件事情需要n个步骤，做第1步有m1种不同 的方法，做第2步有m2种不同的方法，……，做第n步有mn种不同的方 法，那么完成这件事共有
N＝m1×m2×……×mn 种不同的方法。
.
16
例7、电子元件很容易实现电路的通与断、电位的高 与低等两种状态，而这也是最容易控制的两种状 态。因此计算机内部就采用了每一位只有0或1两 种数字的计数法，即二进位制。为了使计算机能 够识别字符，需要对字符进行编号，每个字符可 以用一个或多个字节来表示，其中字节是计算机 中数据存储的最小计量单位，每个字节由8个二进 制位构成，问：一个字节（8位）最多可以表示多 少个不同的字符？
练习：P12 A 1 、2、3、4、5 B1
.
13
小结：两个计数原理都是要完成某“一件事情” 完成这件事要分类，则用分类加法计数原理；完 成这件事要分步，则用分步乘法计数原理。
分类——要不重不漏 分步——步骤要完整
.
14
1、1两个计数原理
第二课时
.
15
复习回顾：
分类加法计数原理：如果完成一个任务有n类不同方案，在第1类方案 中有m1种不同的方法，在第2类方案中m2种不同的方法，……，在第n 类方案中有mn中不同的方法。那么完成这件事共有 N＝m1＋m2＋……＋mn 种不同的方法。
.
9
例3、书架的第一层放有4本不同的计算机书， 第二层放有3本不同的文艺书，第三层放有2 本不同的体育书。
（1）从书架中任取1本书，有多少种不同的 取法？
（2）从书架的第一、二、三层各取1本书， 有多少种不同的取法？
(3)从书架上任取不同科目的两本书，有多 少种不同的取法？
.
10
例4、要从甲、乙、丙3幅不同的画中选出2幅、 分别挂在左、右两边墙上的指定位置，问共有多 少种不同的挂法？
问题4:从甲地到乙地，要从甲地先乘火车到丙地， 再于次日从丙地乘汽车到乙地，一天中，火车有 3班，汽车有2班，那么两天中，从甲地到乙地共 有多少种不同的走法？
.
4
在计数中何时用“加”？何时用“乘”？ 能否谈谈你的看法。
探究：如果完成一件事有n类不同的方案，
每一类中都有若干种不同的方法，那么应该
如何计数呢？
.
5
探究：如果完成一件事情需要n个步骤，做每一步都 有若干种不同的方法，那么应当如何计数呢？
22、、不 法 做 个 有 m分分×n同，第步种n步步n的在骤种步方乘乘步第，不有法法法骤二做同，m计 计， 步 第的n那数 数做 有 一种方么原 原第 步m方法完理 理一 有法2。种成： ：步m，不这完完有那种同件成成m么方的事一一1完法种方共件件成，不法有事事这做同，需有N件第的…＝n要事二方个…两共步 有N=m1m2……mn种不同的方法。
1、分类加法计数原理：完成一件事有n两类类
不同的方案，在第一类方案中m1种种不不同同的 的方方法法，，在在第第二二类类方方案中案有中n有种m不2种同不的同方的法， 方那法么，完…成…这第件n事类共方有案N中=m有+mn种n种不不同同的的方方 法，。那么完成这件事共有
N=m1+m2+……+mn种不同的方法。
推广：n元集合S＝{a1，a2，a3，……， an}的子集有几个以后需要对程序进行测试。程 序员需要知道到底有多少执行路径（即程序从开始到结束的路线）， 以便知道需要提供多少个测试数据、一般地，一个程序模块由许多 子模块组成。它是一个具有许多路径的程序模块。问：这个程序模 块有多少条执行路径。