第2节-枚举、解析算法及其程序实现(A).pptVIP

第四单元　算法的程序实现 第2节　枚举、解析算法及其程序实现 A．枚举算法及其程序实现 1．枚举算法 枚举算法又称为穷举法，其基本思想是根据问题的本身性质，一一列出该问题所有可能的情况，并根据条件逐个做出判断，从中挑选出符合条件的解。 枚举就是将问题的可能解一个一个地列举，逐一判断，即使中途找到符合解也要继续找下去，将所有可能都找完才结束。 2．枚举算法的特点 (1)不能遗漏任何一个真正解，这是问题本身所要求的； (2)设计算法时要尽可能小的范围内罗列出所有可能的情况，不能遗漏，也不能重复。 (3)在使用VB程序解决枚举算法问题时，主要是由循环语句(如用For语句，通过循环语句在一定的范围内，以一定的方式罗列所有的可能解)和选择语句(如用If语句对一个可能解是否是问题的真正解进行判断和选择)的适当组合来完成的。 3．枚举算法的程序实现 高中阶段，对于较为复杂的枚举算法问题，一般通过双重循环来实现。双重循环在使用时，每个循环必须有一个唯一的变量名作为循环变量；在Next语句结束循环时，必须是内层的循环语句先结束，不得出现互相交叉，如下循环结构中，语句“Next j”与语句“Next i”顺序不能调换。 该程序段运行时，外循环①中变量i每取一个值，都要执行一次完整的内循环(即内循环②都要循环一次)。 【例1】　一张单据上有一个5位数的编号，其百位数和十位数处模糊不清(如图a所示)，但已知该5位数是37或67的倍数。设计算法，找出所有满足这些条件的5位数，并统计这些5位数的个数。 算法分析： (1)设计过程：在这个5位数的百位和十位上分别填上两个十进制数字，它就生成了一个可能解n，然后判断n是否是一个真正解，即n能否被37或67整除。若n是真正解，则输出n的值，并在计数器c中加1，表示找到一个真正解。 图a (2)枚举过程：在5位数的百位和十位上依次填入00、01、02、…、97、98、99，这100个不同的数，从而产生出全部可能解：25006、25016、25026、…、25986、25996。在计算过程中使用循环处理模式，让变量i依次取0到99这100个不同的值，同时对于i的每个确定的值乘以10并加上25006，形成一个可能解n。对于每个可能解n，只要判断它是否能被37或67整除，就能确定它是否是一个真正解了。 算法对应流程图如图b所示，其中各变量含义为： i：循环变量，①用来控制循环是否继续进行，并在循环处理过程中用来记录已经进行的循环的次数；②依次产生应填在百位和十位上的数值。 c：计数器，用于记录算法执行过程中已经找到的真正解的个数。 n：存储一个可能解。 图b 根据上述分析，并结合流程图，请在划线处填入合适代码。 Private Sub Command1_Click() 　Dim i As Integer 　Dim c As Integer, n As Integer 　c ＝ 0 　For i ＝ ____①____ 　　n ＝ 25006 ＋ ____②____ 　　If n Mod 37 ＝ 0 ____③____ n Mod 67 ＝ 0 Then 　　　c ＝ c ＋ 1 　　　List1.AddItem ____④____ 　　End If 　Next i 　Text1.Text ＝ Str(c) End Sub 【例1解题】　根据流程图，i取值范围为0～99，故①处答案为0 To 99；产生可能数据为25006、25016、25026、……、25986、25996，故②处答案为i*10；根据筛选条件“n是37或是67的倍数”可知③处答案为Or；列表框List1中输出符合要求的n的值，因此④处答案为Str(n)。 【答案1】　①________ ②________ ③________ ④________ 0 To 99 i*10 Or Str(n) 【例2】　包装1200个玩具，要求是： (1)包装的规格分别是：小盒(每盒5个)和大盒(每盒12个)。 (2)每种规格的盒数可任意，但每盒都必须装满。 设计一个算法，输出所有“总的盒数不超过n(包含n)”的包装方案，并输出包装方案的个数。 算法分析： (1)设1200个玩具分别装入x个小盒和y个大盒，它们必须满足等式5x＋12y＝1200。 (2)考虑x、y值可能的变化范围：x为0～240，y为0～100。 (3)采用了双重循环来枚举，外层的For循环当x取值为0时，内层的For循环完整执行一次，即y取值为0～100之间的整数，然后判断这些y与x的组合是否满足两个条件5x＋12y＝1200且x＋y≤n，若满足，则在列表框List1中输出x、y的值，并使方案个数＋1，一次内循环结束后，外循环变量x增加1