CHAPTER 通高中课程标准实验教科书数学选修2-3 字母 数字 得到的号码 图1.1-1是解决计 数问题常用的“树形 AAAAAAAA 图”.你能用树形图列 出所有可能的号码吗? 56789 图1.1-1 我们还可以这样来思考: 由于前6个英文字母中的任意一个都能与9个数字中的任何一个组成一个号码,而且 它们各不相同,因此共有 6×9=54 个不同的号码 究 你能说说这个问题的特征吗? 上述问题中,最重要的特征是“和”字的出现:每个座位由一个英文字母和一个阿拉 伯数字构成,每一个英文字母与不同的数字组成的号码是各不相同的 一般地,有如下原理 分步乘法计数原理完成一件事需要两个步骤0,“做第1步有m 种不同的方法,做第2步有n种不同的方法,那么完成这件事共有 ◎无论第1 步采用哪种方法, N=mXn 都不影响第2步 种不同的方法 方法的选取 例4设某班有男生30名,女生24名.现要从中选出男、女生各一名代表班级参加 比赛,共有多少种不同的选法? 分析:选出一组参赛代表,可以分两个步骤.第1步选男生,第2步选女生 解:第1步,从30名男生中选出1人,有30种不同选择; 第2步,从24名女生中选出1人,有24种不同选择
第一章计数原理 第一章 根据分步乘法计数原理,共有 30×24=720 种不同的选法 如果完成一件事需要三个步骤,做第1步有m种不同的方法,做 第2步有m2种不同的方法,做第3步有m种不同的方法,那么完成这 件事共有多少种不同的方法? 如果完成一件事情需要n个步骤,儆每一步中都有若干种不同方法,那么应当如 何计数呢? 园m 例3书架的第1层放有4本不同的计算机书,第2层放有3本不同的文艺书,第3 层放有2本不同的体育书 (1)从书架中任取1本书,有多少种不同取法? (2)从书架的第1,2,3层各取1本书,有多少种不同取法? 解:(1)从书架上任取1本书,有3类方法:第1类方法是从第1层取1本计算机书 有4种方法;第2类方法是从第2层取1本文艺书,有3种方法;第3类方法是从第3层 取1本体育书,有2种方法.根据分类加法计数原理,不同取法的种数是 N=m+m2+m=4+3+2=9; (2)从书架的第1,2,3层各取1本书,可以分成3个步骤完成:第1步从第1层 取1本计算机书,有4种方法;第2步从第2层取1本文艺书,有3种方法;第3步从 第3层取1本体育书,有2种方法.根据分步乘法计数原理,不同取法的种数是 N=m1×m2Xm=4×3×2=24. 例4要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位 置,问共有多少种不同的挂法? 解:从3幅画中选出2幅分别挂在左、右两边墙上,可以分两个步骤完成:第1步, 从3幅画中选1幅挂在左边墙上,有3种选法;第2步,从剩下的2幅画中选1幅挂在右 边墙上,有2种选法.根据分步乘法计数原理,不同挂法的种数是 N=3×2=6. 6种挂法可以表示如下: 5
CHAPTER 普迺高中课程标准实验教科书数学选修23 左边 右边 得到的挂法 左甲右乙 乙丙甲丙甲乙 左甲右丙 左乙右甲 左乙右丙 左丙右甲 左内右乙 分类加法计数原理和分步乘法计数原理,回答的都是有关做一件事的不同方法的种数 问题.区别在于:分类加法计数原理针对的是“分类”问题,其中各种方法相互独立,用 中任何一种方法都可以做完这件事;分步乘法计数原理针对的是“分步”问题,各个步 骤中的方法互相依存,只有各个步骤都完成才算做完这件事 练习 1.填空: (1)一件工作町以用2种方法完成,有5人只会用第1种方法完成,另有4人只会川第2种方 法完成,从中选出1人来完成这件工作,不同选法的种数是 (2)从A村去B村的道路有3条,从B村去C村的道路有2条,从A村经B村去C村,不同 的路线们条. 2.现有高一年级的学生3名,高二年级的学生5名,高三年级的学生4名 (1)从中任选1人参加接待外宾的活动,有多少种不同的选法? (2)从3个年级的学生中各选1人参加接待外宾的活动,有多少种不同的选法? 3在例1中,如果数学也是A大学的强项专业,则A大学共有6个专业可以选择,B大学共有 1个专业可以选择,那么用分类加法计数原理,得到这名同学可能的专业选择共有 6+4=10(种). 这种算法有什么问题? 例5给程序模块命名,需要用3个字符,其中首字符要求用字母A~G或U~Z 后两个要求用数字1~9.问最多可以给多少个程序命名? 分析:要给一个程序模块命名,可以分三个步骤:第1步,选首字符;第2步,选中 间子符;第3步,选最后一个字符.而首字符又可以分为两类 解:先计算首字符的选法.由分类加法计数原理,首字符共有 7+6=13 种选法 你还能给出不同的 再计算可能的不同程序名称.由分步乘法计数原理,最 解法吗? 多可以有 6
第一章计数原理 第一章 13×9×9=1053 个不同的名称,即最多可以给1053个程序命名. 例6核糖核酸(RNA)分子是在生物细胞中发现的化学成分.一个RNA分子是一个 有着数百个甚至数千个位置的长链,长链中每一个位置上都由一种称为碱基的化学成分所 占据.总共有4种不同的碱基,分别用A,C,G,U表示.在一个RNA分子中,各种碱 基能够以任意次序出现,所以在任意一个位置上的碱基与其他位置上的碱基无关.假设有 一类RNA分子由100个碱基组成,那么能有多少种不同的RNA分子? L 分析:用图1.1-2来表示由100个碱基组成的长链,这时我们共有100个位置,每个 位置都可以从A,C,G,U中任选一个来占据. 第1位第2位第3位 第100位 图1.1-2 解:100个碱基组成的长链共有100个位置,如图1.1-2所示 从左到右依次在每一个位置中,从A,C,G,U中任选一个填入, 100≈1.6 10°,这是一个非 每个位置有4种填充方法根据分步乘法计数原理,长度为100的所常大的数有兴 有可能的不同RNA分子数目有 趣的同学可以自 4=40(个). 己查阅一下RN 的有关资料 100个4 例7电子元件很容易实现电路的通与断、电位的高与低等两种状态,而这也是最容 易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法,即二进 制为了使计算机能够识别字符,需要对字符进行编码,每个字符可以用一个或多个字节来表 示,其中字节是计算机中数据存储的最小计量单位,每个字节由8个二进制位构成.问: (1)一个字节(8位)最多可以表示多少个不同的字符? (2)计算机汉字国标码(GB码)包含了6763个汉字,一个汉字为一个字符,要对这些 汉字进行编码,每个汉字至少要用多少个字节表示? 分析:由于每个字节有8个二进制位,每一位上的值都有0,1两种选择,而且不同 的顺序代表不同的字符,因此可以用分步乘法计数原理求解本题 解:(1)用图1.1-3来表示一个字节. 7
CHAPTER 普通高中课程标准实验教科书数学选修23 第1位第2位第3位 第8位 2种 2种 2种 图1.1-3 个字子节共有8位,每位上有2种选择.根据分步乘法计数原理,一个字节最多可以 2×2×2×2×2×2×2×2=28=256 个不同的字符; (2)由(1)知,用一个字节所能表示的不同字符不够6763个,我们就考虑用2个字节 能够表示多少个字符.前一个字节有256种不同的表示方法,后一个字节也有256种表示 方法.根据分步乘法计数原理,2个字节可以表示 256×256=65536 个不同的子符,这已经大于汉字国标码包含的汉字个数6763.所以要表示这些汉字,每个汉 字至少要用2个节表示 例8计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底 有多少条执行路径(即程序从开始到结束的路线),以便知道需要提供多少个测试数据. 一般地,一个程序模块由许多子模块组成.如图1.1-4,它是一个具有许多执行路径的程 序模块.问:这个程序模块有多少条执行路径? 另外,为了减少测试时间,程序员需要设法减少测试次数.你能帮助程序员设计一个测试 方法,以减少测试次数吗? 开始 子模块1 子模块2 子模块3 18条执行路径 45条执行路径 28条执行路径 子模块4 子模块5 38条执行路径 43条执行路径 结束 图1.1-4