资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1.2,分类计数原理,与,分步计数原理,(,二,),1,、分类加法计数原理,：完成一件事，有,n,类办法，在第,1,类办法中有,m,1,种不同的方法,在第,2,类办法中有,m,2,种不同的方法,在第,n,类办法中,有,m,n,种不同的方法,.,那么完成这件事共有 种不同的方法,.,2,、分步乘法计数原理,：,完成一件事，需要分成,n,个步骤，做第,1,步有,m,1,种不同的方法,做第,2,步有,m,2,种不同的方法,，做第,n,步有,m,n,种不同的方法,.,那么完成这件事共有 种不同的方法,.,分类加法计数原理和分步乘法计数原理的,共同点：,不同点：,分类加法计数原理与分类有关，,分步乘法计数原理与分步有关。,回答的都是有关做一件事的不同方法种数的问题,加法原理,乘法原理,联系,区别一,完成一件事情共有,n,类,办法，关键词是“分类”,完成一件事情,共分,n,个,步骤，关键词是“分步”,区别二,每类办法都能,独立完成,这件事情。,每一步得到的只是中间结果，,任何一步都,不能能独立完成,这件事情,，缺少任何一步也,不能完成这件事情，只有每,个步骤完成了，才能完成这,件事情。,分类计数原理和分步计数原理，回答的都是关于,完成一件事情的不同方法的种数的问题。,区别三,各类办法是互斥的、,并列的、独立的,各步之间是相关联的,分类计数与分步计数原理的区别和联系：,例,1.,五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，冠军获得者有多少种不同可能性（没有并列冠军）？,解：（,1,）,5,名学生中任一名均可报其中的任一项，因此每个学生都有,4,种报名方法，,5,名学生都报了项目才能算完成这一事件故报名方法种数为,44444=,种,.,（,2,）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此,冠军获得者,有,5,种可能性，故有,n,=5,=,种,.,例,2.,给程序模块命名，需要用,3,个字符，其中首个字符要求用字母,AG,或,UZ,，,后两个要求用数字,1,9,，问最多可以给多少个程序命名？,分析：,要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。,解：,首字符共有,7+6,13,种不同的选法，,答：,最多可以给,1053,个程序命名。,中间字符和末位字符各有,9,种不同的选法,根据分步计数原理，最多可以有,1399,1053,种不同的选法,例,4.,电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有,0,或,1,两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问,（,1,）一个字节（,8,位）最多可以表示多少个不同的字符？,（,2,）计算机汉字国标码（,GB,码）包含了,6763,个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,第,1,位,第,2,位,第,3,位,第,8,位,2,种,2,种,2,种,2,种,如,00000000,，,10000000,，,11111111.,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,例,5.,计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,分析：,整个模块的任意一条路径都分两步完成,：,第,1,步,是从开始执行到,A,点；,第,2,步,是从,A,点执行到结束,。,而第一步可由子模块,1,或子模块,2,或子模块,3,来完成；第二步可由子模块,4,或子模块,5,来完成。因此，分析一条指令在整个模块的执行路径需要用到两个计数原理。,开始,子模块,1,18,条执行路径,子模块,3,28,条执行路径,子模块,2,45,条执行路径,子模块,5,43,条执行路径,子模块,4,38,条执行路径,结束,A,再测试各个模块之间的信息交流是否正常，需要测试的次数为：,3*2=6,。,如果每个子模块都正常工作，并且各个子模块之间的信息交流也正常，那么整个程序模块就正常。,这样，测试整个,模块的次数就变为,172+6=178,（次）,2,）在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块。这样，他可以先分别单独测试,5,个模块，以考察每个子模块的工作是否正常。总共需要的测试次数为：,18+45+28+38+43=172,。,例,6.,随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个字母必须合成一组出现，个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照,?,课堂练习,1,、乘积,展开后共有几项？,2,、某商场有,6,个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？,
展开阅读全文