第六讲 枚举算法和数组变量的应用.doc

第六讲 枚举算法和数组变量的应用本讲任务：1知道枚举算法的结构特点、设计步骤和优缺点。2不同类型的枚举算法应用举例和上机编程。3、数组变量的引入，数组组成的要素以及数组的功能和特点。4、用数组处理批量数据的基本方法。一、枚举算法相关内容(1)枚举算法的结构特点枚举法的关键就是列举和检验这两个操作，如图31所示。图3-1列举和检验为了保证对所有可能的情况逐一列举和检验，势必要重复地进行这两个操作，直到所有情况都检验完为止。因此一般用循环结构来实现，如图32所示。图32循环检验操作1操作2检验就是对某一给定的条件进行判断，根据判断的不同结果执行不同的操作，所以上图中的“检验”部分可以用分支结构来实现，如图33所示。图3-3用分支实现检验由此可以看出，枚举算法的一般结构是循环结构中嵌套分支结构。其中循环结构用于实现逐一列举，分支结构用于实现检验，列举和检验是循环体中的一部分，当然具体的判断条件和列举内容等应根据实际问题来进行设置。另外一些比较复杂的枚举问题，可能会涉及到循环结构的嵌套。(2)枚举算法的一般设计步骤确定列举的范围：确定列举的对象的范围，不能随意扩大和缩小列举范围，否则可能会造成多解或漏解后果。明确检验的条件：分析题目，明确检验的对象、检验的条件以及检验后需执行的相关操作；检验的对象可能是循环变量，也可能是其他变量。确定循环控制方式和列举的方式：根据列举的范围，选择合适的方法控制循环；列举的方式是不唯一的，很多时候，可以借助循环变量的变化来进行列举，而有时可能需要通过其他方法来进行列举，如输入等。具体见应用示例中的示例l(求12008中，能被37整除的数)。(3)枚举法的优缺点枚举法充分利用了计算机快速高效的特点，让计算机进行重复运算，以求得问题的解。由于枚举法是将所有可能的解无一例外地进行检验，因此只要列举正确，枚举法具有非常高的准确性和全面性，然而也正是这个特点决定了枚举法的局限性效率不高。它的准确性和全面性是以消耗时间为代价获得的。当然，有些比较复杂的问题可能一时无法找到直接的求解公式，建立有效的数学模型。枚举法的优越性又得以体现。因此，枚举法既有其优越性，又有其局限性。只有认清了这点，我们才能在设计算法时灵活运用，设计出有效、高效的算法。当然，并不是所有的问题都可以使用枚举算法来寻找答案，仅当问题的所有可能解的个数不太多时，才有可能使用枚举算法，在设计枚举算法时应特别注意时间的消耗问题，当问题可能解的个数较多，所需花费的时间较长时(如需几个月甚至几年乃至更长)，这样的枚举算法是没有实际意义的，换言之枚举法适用于可能解的个数不太多的情况，在可以接受的时间内得到问题的所有解。(4)几种不同类型的枚举算法按列举方式可分为以下两种枚举算法。列举的变量和循环变量相关的枚举算法某些问题中，列举的对象和循环次数之间存在着某种内在的联系，此时可以直接用循环变量表示，或者由循环变量参与运算得到。例如求自然数中前25个偶数中所有能被3整除的数，则流程图如图34所示。其中n是循环变量，用于控制循环，x则用于列举可能的解。每次循环列举一个可能解，列举的x由循环变量运算得到。当然此题的列举方式并不唯一，这里只是以此来说明列举的不同方式。列举的变量和循环变量无关的枚举算法某些问题中，需列举的对象和循环变量间无内在的联系，此时需使用另外的变量，循环变量则单纯地用于控制循环的次数即列举的个数。例如，将输入的100个数中的所有正数输出，列举的方式为输入一个数，循环变量则控制100次循环。 图34枚举算法流程图按算法结构可分为以下两种枚举算法。单重循环结构的枚举算法对于一些比较简单的问题，只要用一个变量的变化就能列举出问题的所有可能解，此时用一重循环就能实现列举。如示例l“求l1000中能被3整除的数”中：只要使用一个变量n，n的初值设为l，终值为1000，单重循环使得变量n每次循环都加1变换，即可从1列举到1000。单重循环的枚举算法的结构较为简单循环体内套一个分支结构。多重循环嵌套的枚举算法有些问题，需要列举的情况比较复杂，需要使用两个甚至更多的变量，此时需要使用多重循环的嵌套。例如单据问题：“一张单据上有一个5位数的编号，其千位数和百位数处已变得模糊不清l47，但是知道这个5位数是57或67的倍数。输出所有满足这些条件的5位数。”若模糊不清的数改为l47，即模糊不清的两个数字的数位是不连续的，那么此题就要用二重循环的嵌套来进行列举。可以用i表示千位上的数字，j表示十位上的数字，i和j的变化范围都是09，外循环用于实现i的变化，内循环用于实现j的变化。所以在设计枚举算法时特别要注意列举的正确性，确保不重复、不遗漏。(算法流程图及程序代码见附录。)例3、一份单据中被涂抹的数字的推算1问题一张单据上有一个5位数字组成的编号，其干位数和百位数处已经变得模糊不清，如图所示。但是知道这个5位数是57或67的倍数。现要求设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。图27单据问题示例2算法先把这个编号看成是一个5位的正整数，该数的万位数为1，十位数是4，个位数是7，但不知道千位数和百位数是什么数字。如果在这个5位数的千位和百位上，分别填上两个十进制数(09)，则可生成一个可能解n，然后判断n是否是一个真正解，即n是否能被57或67整除。若n是真正解，则输出n的值，并在计数器c中加上1，表示找到了一个真正解。使用枚举算法解决问题时，我们必须逐一地给出所有可能解并对它们进行检验，既不能遗漏任何一个可能解，也不应该重复地产生和检验可能解。本问题中，可以按这样的方法逐一产生可能的解：在这个5位数的干位和百位这两个位置上，依次填入00、01、02、97、98、99这100个不同的数字，从而产生出全部可能解：10047、10147、10247、19847、19947。如果在计算过程中使用重复处理模式，让变量j依次取099这100个不同的值，同时对于j的每个确定的值乘以100并加上10047，这样就能形成一个可能解。对于每一个这样的可能解n，只要判断它是否能被57或67整除，就能确定它是否是一个真正解了。 图28寻找单据上的5位数的算法图28是用流程图描述的寻找单据上的所有合格的5位数的算法。在算法中使用的变量：c：计数器，用于记录算法执行过程中已找到的真正解的个数。j：本变量的作用如下：(1)在重复处理过程中，记录已经进行的重复次数，并用它来控制重复的次数；(2)依次产生应填在千位和百位上的数值(099)。REM ex5_3bCLS c = 0 FOR i= 1 TO 9 FOR j = 1 TO 9 n = 10407 + i * 1000+j*10 IF (n MOD 57 = 0) OR (n MOD 67 = 0) THEN c = c + 1 PRINT n END IF NEXT j NEXT i PRINT There are of ; c; kinds the answer.ENDn：存储一个可能解。REM ex5_3aCLS c = 0 FOR j = 1 TO 99 n = 10047 + j * 100 IF (n MOD 57 = 0) OR (n MOD 67 = 0) THEN c = c + 1 PRINT n END IF NEXT j PRINT There are of ; c; kinds the answer.END若模糊不清的数改为l47，即模糊不清的两个数字的数位是不连续的，那么此题就要用二重循环的嵌套来进行列举。例4、当一个直角三角形的三条边的边长都是整数时，这样的直角三角形称为整数边长的直角三角形。整数边长的直角三角形一直是一个有趣的话题。例如，若一个直角三角形中一条直角边的长度固定为8，且斜边长度不超过100，要求找出所有满足这种要求的整数边长的直角三角形，图29所示的就是满足上述条件的所有直角三角形。图29问题示例当一条直角边的长度为15且斜边不超过200时，所有满足条件的直角三角形有如下四个(如图210所示)。现在，在一个直角三角形中，三条边a、b、c的长度都是整数，若一条直角边a的长度已知，斜边c的长度不超过给定的整数值maxc，试设计算法，找出满足条件的所有直角三角形。 图210问题示例REM ex5_4CLS m = 0 INPUT a,maxc=; a, maxc FOR b = 1 TO maxc FOR c = a TO maxc IF a * a + b * b = c * c THEN m = m + 1 PRINT m; : ; a, b, c END IF NEXT c NEXT b PRINT m=; mEND知识链接rem ex5_5cls i=1 do while i1000 i=i+1 j=2 do while ji if i mod j0 then j=j+1 else exit do end if loop IF j = i THEN m = m + 1 PRINT i; END IF loopend勾股问题的研究在我国具有悠久的历史，取得过辉煌的成绩。如果将一个直角三角形竖起来，横着的一条直角边称为“勾”，竖着的一条直角边称为“股”，斜边称为“弦”。当一个直角三角形的三条边的边长都是整数时，这样的三角形称为整数边长的直角三角形，代表边长的三个正整数称为一组勾股数。例如，3、4、5就是一组勾股数。例5、1000以内素数的推算1问题素数，也叫质数。判断一个数是否为素数，可以使用素数的定义。通常我们称自然数n是一个素数，是指只有1和n本身才能整除它(1不是素数，2是最小的素数)，即一个素数除了它本身以外，不可能分解为其他自然数的乘积。试采用枚举算法找出1000以内的所有素数。2算法从21000依次判断它是否是素数，这里要用到两重循环。外层循环：设置一个变量i从11000。这层循环的作用就是枚举11000的数，依次判断它们是否是素数。内层循环：设置一个变量j，从2开始，最大到i一1。如果i能被j整除，则说明i不是素数，跳出循环。如果从2i一1都不能整除i，则说明i是素数，输出i。图211所示是描述输出1000以内素数算法的流程图。 图211输出1000以内素数算法的流程图结束Nom0:x1y=40Yes开始输出m,x,yx max THEN max = a(i) END IF IF a(i) max THEN max = a(i) maxi = i END IF IF a(i) min THEN min = a(i) mini = i END IF NEXT i PRINT FOR i = n TO 1 STEP -1 PRINT a; i; =; a(i); IF i = 4 THEN PRINT NEXT i PRINT PRINT PRINT max=; max; PRINT