第一章计数原理 第一章 分析:整个模块的任意一条执行路径都分两步完成:第1步是从开始执行到A点;第 2步是从A点执行到结束.而第1步可由子模块1或子模块2或子模块3来完成;第2步 可由子模块4或子模块5来完成.因此,分析一条指令在整个模块的执行路径需要用到两 个计数原理 解:由分类加法计数原理,子模块1或子模块2或子模块3中的子路径共有 18+45+28=91(条); 子模块4或子模块5中的子路径共有 38+43=81(条) 又由分步乘法计数原理,整个模块的执行路径共有 91×81=7371(条) 在实际测试中,程序员总是把每一个子模块看成一个黑箱,即通过只考察是否执行了 正确的子模块的方式来测试整个模块.这样,他可以先分别单独测试5个模块,以考察每 个子模块的工作是否正常.总共需要的测试次数为 18+45+28+38+43=172. 再测试各个模块之间的信息交流是否正常,只需要测试程序第1步中的各个子模块和第2 步中的各个子模块之间的信息交流是否正常,需要的测试次数为 3×2=6. 如果每个子模块都工作正常,并且各个子模块之间的信息交流也正常,那么整个程序模块 就工作正常.这样,测试整个模块的次数就变为 172+6=178(次) 显然,178与7371的差距是非常大的 你看出了程序员是如何实现减少测试次数的吗? 例9随着人们生活水平的提高,某城市家庭汽车拥有量迅速增长,汽车牌照号码需 要扩容.交通管理部门出台了一种汽车牌照组成办法,每一个汽车牌照都必须有3个不重 复的英文字母和3个不重复的阿拉伯数字,并且3个字母必须合成一组出现,3个数字也 必须合成一组出现.那么这种办法共能给多少辆汽车上牌照? 分析:按照新规定,牌照可以分为2类,即字母组合在左和字母组合在右.确定一个牌照 的字母和数字可以分6个步骤 解:将汽车牌照分为2类,一类的字母组合在左,另一类的字母组合在右. 字母组合在左时,分6个步骤确定一个牌照的字母和数字: 第1步,从26个字母中选1个,放在首位,有26种选法; 第2步,从剩下的25个字母中选1个,放在第2位,有25种选法; 第3步,从剩下的24个字母中选1个,放在第3位,有24种选法; 第4步,从10个数字中选1个,放在第4位,有10种选法; 第5步,从剩下的9个数字中选1个,放在第5位,有9种选法; 第6步,从剩下的8个字母中选1个,放在第6位,有8种选法 9
CHAPTER 菩迺高中课程标准实验教科书数学逃修23 根据分步乘法计数原理,字母组合在左的牌照共有 26×25×24×10×9×8=11232000(个) 同理,字母组合在右的牌照也有11232000个 所以,共能给 11232000+11232000=22464000 辆汽车上牌照 考 你能归纳一下用分类加法计数原理、分步乘法计数原理解决计数问题 的方法吗? 用两个计数原理解决计数问题时,最重要的是在开始计算之前要进行仔细分析需 要分类还是需要分步 分类要做到“不重不漏¨.分类后再分别对每一类进行计数,最后用分类加法计数原 理求和,得到总数 分步要做到¨步骤完整¨—完成了所有步骤,恰好完成任务.当然步与步之间要相 互独立.分步后再计算每一步的方法数,最后根据分步乘法计数原理,把完成每一步的方 法数相乘,得到总数. 思 乘法运算是特定条件下加法运算的简化,分步乘法计数原理和分类加 法计数原理也有这种类似的关系吗? 练习 1.乘积(a1+a2+a)(b1+b2+b)(c1+c2+c3+c+c)展开后共有多少项? 2.某电话局管辖范围内的电话号码由八位数字组成,其中前四位的数字是不变的,后四位数字都 是0到9之间的一个数字,那么这个电话局不同的电话号码最多有多少个? 3.从5名同学中选出正、副组长各1名,有多少种不同的选法? 1.某商场有6个门,如果某人从其中的任意一个门进入商场,并且要求从其他的门出去,共有多 )少种不同的进出商场的方式?
第一章计数原理 第一章 发 子集的个数有多少 问题n元集合A={a1,a2,…,an}的子集有多少个? 为了解决这个问题,一个可行的思路是先研究一下某些具体集合,如S={a1,a }的子集个数,从中获得启发,然后再对一般的情况进行研究 由于S中的元素只有3个,因此我们可以用列举法列出 它的所有子集: ,{a1},{a2},{a3},{a1,a2},{a,aa},{a2,a3},S. 虽然列举法较“笨” 但它是计数的基本方法.你 因此,一个含有3个元素的集合共有8个子集 如果一个集合所含元素较少,可以用列举法确定其子集的|集的一下4元集、5元 可以列举 个数.但如果集合中的元素较多,用这种方法确定子集个数就 不太方便了.另外,从上迷描述中较难发现3与8之间的 关系 为了发现规律,我们需要采取另外的方法.一个自然的想法是,应当设法用上两个计 数原理 显然,元素a(i=1,2,3)与各子集的关系只有两种:a,属于子集或a,不属于子集. 这样,我们可以考虑用考察S中的每一个元素属不属于某个子集的方法来得到一个子集, 因为S中有3个元素,所以要得到集合S的一个子集S1,可以分三个步驟: 第1步,考察元素a1是否在S1中,有2种可能(a1∈S1, a1∈S1); 由此,你是否对把 第2步,考察元素a2是否在S中,有2种可能(a2∈S1, 空集及原集合自身作为 a2∈S1) 子集的规定有进一步的 第3步,考察元素a是否在S1中,有2种可能(a3∈S1 ●理解? a3∈S1) 只要完成上述三个步骤,那么集合S1中元素就完全确定了. 根据分步乘法计数原理,对于由3个元素组成的集合,共有 2×2×2=23=8 个不同的子集 从上述过程我们看到了3与8之间的关系:3是23中的指数,而8是2的运算结果 般的,我们有 n元集合A={a1,a2,…,an}的不同子集有2个 证明:要得到集合A的一个子集S1,可以分n个步骤
CHAPTER 通高中课程标堆实验教科书数芓选修23 第1步,考察元素a是否在S1中,有2种可能(a1∈S1,a∈S1); 第2步,考察元素a2是否在S1中,有2种可能(a2∈S1,a2∈S1); 第k步,考察元素山是否在S1中,有2种可能(a∈S1,a∈S1); 第川步,考察元素an是否在S1中,有2种可能(an∈S1,an∈S) 只要完成上迷〃个步骤,那么集合S中元素就完全确定了.根据分步乘法计数原理, 对于由个元素组成的集合,共有 2×2×…×2=2 个2 个不同的子集 思 考 你还能用另外的方法证明上述结论吗? 习题1.1 A组 1.一个商店销售某种型号的电视机,其中本地的产品有4种,外地的产 品有7种,要买1台这种型号的电视机,有多少种不同的选法? 2.如图,从甲地到乙地有2条路,从乙地到丁地有3条路;从甲地到丙 , 地有4条路,从丙地到丁地有2条路.从甲地到丁地共有多少条不同 的路线? 3用1,5.9,13中的任意一个数作分子,4,8,12,16中任意一个数 (第2题) 作分母,可构成多少个不同的分数?可构成多少个不同的真分数? 44.如图,一条电路从A处到B处接通时,可有多少条不同的线路? (1)在平面直角坐标系内,横坐标与纵坐标均在A={0,1 2.3,4,5}内取值的不同点共有多少个? (2)在平面直角坐标系内,斜率在集合B=(1,3,5,7)内取 B 值,y轴上的截距在集合C={2,4,6,8}内取值的不同直线 共有多少条? (第4题) 一上上二山山占上山山k品品品如品hh
第一章计数原理 第一章 B组 1.一种号码锁有4个拨号盘,每个拨号盘上有从0到9共10个数字,现最后一个拨号盘出现了 故障,只能在0到5这六个数字中拨号,问这4个拨号盘可组成多少个四位数字号码? 2.(1)4名同学分别报名参加学校的足球队、篮球队、乒乓球队,每人限报其中的一个运动队, 不同报法的种数是3“还是4? (2)3个班分别从5个风景点中选择一处游览,不同选法的种数是35还是5? 过山试dd山山山山山山山 ■13组