枚举算法和数组变量的应用.docVIP

第六讲 枚举算法和数组变量的应用 本讲任务： 1．知道枚举算法的结构特点、设计步骤和优缺点。 2．不同类型的枚举算法应用举例和上机编程。 3、数组变量的引入，数组组成的要素以及数组的功能和特点。 4、用数组处理批量数据的基本方法。 一、枚举算法相关内容 (1)枚举算法的结构特点 ①枚举法的关键就是列举和检验这两个操作，如图3—1所示。 图3-1列举和检验 ②为了保证对所有可能的情况逐一列举和检验，势必要重复地进行这两个操作，直到所有情况都检验完为止。因此一般用循环结构来实现，如图3—2所示。 图3—2循环检验 ③检验就是对某一给定的条件进行判断，根据判断的不同结果执行不同的操作，所以上图中的“检验”部分可以用分支结构来实现，如图3—3所示。 图3-3用分支实现检验 由此可以看出，枚举算法的一般结构是循环结构中嵌套分支结构。其中循环结构用于实现逐一列举，分支结构用于实现检验，列举和检验是循环体中的一部分，当然具体的判断条件和列举内容等应根据实际问题来进行设置。另外一些比较复杂的枚举问题，可能会涉及到循环结构的嵌套。 (2)枚举算法的一般设计步骤 ①确定列举的范围：确定列举的对象的范围，不能随意扩大和缩小列举范围，否则可能会造成多解或漏解后果。 ②明确检验的条件：分析题目，明确检验的对象、检验的条件以及检验后需执行的相关操作；检验的对象可能是循环变量，也可能是其他变量。 ③确定循环控制方式和列举的方式：根据列举的范围，选择合适的方法控制循环；列举的方式是不唯一的，很多时候，可以借助循环变量的变化来进行列举，而有时可能需要通过其他方法来进行列举，如输入等。具体见应用示例中的示例l(求1~2008中，能被37整除的数)。 (3)枚举法的优缺点 枚举法充分利用了计算机快速高效的特点，让计算机进行重复运算，以求得问题的解。由于枚举法是将所有可能的解无一例外地进行检验，因此只要列举正确，枚举法具有非常高的准确性和全面性，然而也正是这个特点决定了枚举法的局限性——效率不高。它的准确性和全面性是以消耗时间为代价获得的。 当然，有些比较复杂的问题可能一时无法找到直接的求解公式，建立有效的数学模型。枚举法的优越性又得以体现。因此，枚举法既有其优越性，又有其局限性。只有认清了这点，我们才能在设计算法时灵活运用，设计出有效、高效的算法。 当然，并不是所有的问题都可以使用枚举算法来寻找答案，仅当问题的所有可能解的个数不太多时，才有可能使用枚举算法，在设计枚举算法时应特别注意时间的消耗问题，当问题可能解的个数较多，所需花费的时间较长时(如需几个月甚至几年乃至更长)，这样的枚举算法是没有实际意义的，换言之枚举法适用于可能解的个数不太多的情况，在可以接受的时间内得到问题的所有解。 (4)几种不同类型的枚举算法 按列举方式可分为以下两种枚举算法。 ①列举的变量和循环变量相关的枚举算法 某些问题中，列举的对象和循环次数之间存在着某种内在的联系，此时可以直接用循环变量表示，或者由循环变量参与运算得到。例如求自然数中前25个偶数中所有能被3整除的数，则流程图如图3—4所示。 其中n是循环变量，用于控制循环，x则用于列举可能的解。每次循环列举一个可能解，列举的x由循环变量运算得到。当然此题的列举方式并不唯一，这里只是以此来说明列举的不同方式。 ②列举的变量和循环变量无关的枚举算法 某些问题中，需列举的对象和循环变量间无内在的联系，此时需使用另外的变量，循环变量则单纯地用于控制循环的次数即列举的个数。例如，将输入的100个数中的所有正数输出，列举的方式为输入一个数，循环变量则控制100次循环。 图3—4枚举算法流程图 按算法结构可分为以下两种枚举算法。 ①单重循环结构的枚举算法 对于一些比较简单的问题，只要用一个变量的变化就能列举出问题的所有可能解，此时用一重循环就能实现列举。如示例l“求l～1000中能被3整除的数”中：只要使用一个变量n，n的初值设为l，终值为1000，单重循环使得变量n每次循环都加1变换，即可从1列举到1000。单重循环的枚举算法的结构较为简单——循环体内套一个分支结构。 ②多重循环嵌套的枚举算法 有些问题，需要列举的情况比较复杂，需要使用两个甚至更多的变量，此时需要使用多重循环的嵌套。例如单据问题：“一张单据上有一个5位数的编号，其千位数和百位数处已变得模糊不清l××47，但是知道这个5位数是57或67的倍数。输出所有满足这些条件的5位数。”若模糊不清的数改为l×4×7，即模糊不清的两个数字的数位是不连续的，那么此题就要用二重循环的嵌套来进行列举。可以用i表示千位上的数字，j表示十位上的数字，i和j的变化范围都是0～9，外循环用