谈谈用枚举算法解决问题的编程思路与步骤方法
一．问题
上海市普通高中在信息科技学科中开展《算法与程序设计》教学，教材中有一章名为“算法实例”的内容，其中有一节介绍“枚举算法”。教材中关于枚举算法的描述：有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些符合要求的。这种方法叫做枚举算法（enumerative algorithm）。
枚举法就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，我们采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。
生活和工作中，人们经常会不经意间运用“枚举算法”的基本原理，进行问题的解决。比如，让你用一串钥匙，去开一把锁，但是不知道具体是用哪一把钥匙，你就会一把一把地挨个地逐个尝试，最终打开锁为止。又如，要对1000个零件，进行合格检验，等等。
 
二．用枚举算法的思想编写程序的思路与步骤
枚举算法，归纳为八个字：一一列举，逐个检验。在实际使用中，一一列举；采用循环来实现，逐个检验：采用选择来实现。
下面，通过一个问题的解决来说明这一类问题的解决过程的方法与步骤；
例1：在1—2013这些自然数中，出所有是37倍数的自然数。
这个问题就可以采用枚举算法来解决：
1)．一一列举；采用循环来实现；
循环需要确定范围：本循环控制变量假设用i，起始值是1，终止值是2013。
2)．逐个检验：采用选择来实现；
选择需要列出判断的关系表达式：i Mod 37 = 0
这样，就可以写出整个求解的VB代码：
Dim i As Integer
For i = 1 To 2013
   If i Mod 37 = 0 Then
      Print i
   End If
Next i
说白了，用枚举算法解决问题，其实是利用计算机的高速度这一个优势，就好比上题完全可以使用一张纸和一支笔，采用人工的方法完成问题的解，从1开始，一一试除以37，这样计算2013次，也可以到问题的答案。
在教学中，问题的求解往往是针对数学上的问题，下面举一些相关的例子，来巩固与提高采用枚举算法进行程序设计的技能。
 
三．枚举算法举例：
1：一张单据上有一个5位数的编号，万位数是1，千位数是4，百位数是7，个位数、十位数已经模糊不清。该5位数是57或67的倍数，输出所有满足这些条件的5位数的个数。（147□□）
1)．一一列举；采用循环来实现；
循环需要确定范围：本循环控制变量假设用i，起始值是0，终止值是99。
2)．逐个检验：采用选择来实现；
选择需要列出判断的关系表达式：
(14700 + i) Mod 57 = 0 Or (14700 + i) Mod 67 = 0
这样，就可以写出整个求解的VB代码：
Dim n As Integer
Dim i As Integer
n = 0
For i = 0 To 99
   If (14700 + i) Mod 57 = 0 Or (14700 + i) Mod 67 = 0 Then
      n = n + 1
      Print (14700 + i)
   End If
Next i
Print n
 
2：水仙花数（若三位数x=100a+10b+c，满足a^3+b^3+c^3=x，则x为水仙花数）
1) 三位数的范围：i = 100 -- 999
2) 条件表达式：为了使用题目中的条件，需要把一个三位数i，拆分成三个一位数字，然后才可以进行条件a^3+b^3+c^3 = i。
 
**************************************************************************
注意：由于需要把一个多位自然数拆分成若干个一位数字，即分离出每一个数位上的数字，这里介绍常用的方法；
在小学阶段刚开始学习除法，我记得老师是这么在黑板上写的；
8 ÷5 = 1 ……3
老师告诉我们，8是被除数，5是除数，1是商，3是余数。
在VB中，提供了可以获得在这样的除式运算中的运算符号（\、Mod）：
8 \ 5 得到的结果是商1
8 Mod 5得到的结果是余数3
例如：26 \ 6 = 4，26 Mod 6 = 2
**************************************************************************
 
这样，就可以写出整个求解的VB代码：
Dim i As Integer
Dim a As Integer    ‘存放百位数字
Dim b As Integer    ‘存放十位数字
Dim c As Integer    ‘存放个位数字
什么是编程举个例子
For i = 100 To 999     ‘循环实现一一列举
   ‘拆分出百、十、个位数字
   a = i \ 100           ‘假设i为123，a = 123 \ 100 = 1
   b = i \ 10 Mod 10     ‘b = i \ 10 Mod 10 = 123 \ 10 Mod 10 = 12 Mod 10 = 2
   c = i Mod 10         ‘c = i Mod 10 = 123 Mod 10 = 3
   ‘这样就可以利用题目中的条件进行判断
If i = a ^ 3 + b ^ 3 + c ^3 Then
      Print i
   End If
Next i
 
3．求方程5X + 4Y = 2 的整数解。
我们知道，采用消元法解方程组的基本规则是，有几个未知数，就要有几个方程。而本题只有一个方程，却要解2个未知数，数学中把这一类方程叫做不定方程。理论上，不定方程有无数个解。道理很简单，上述这个方程，如果在实数内求解，只要任意假设一个X（或者Y），代入方程，就可以解得Y（或者X），例如，假设X=1，那么Y=－0.75，如果要在整数范围内求解，把上述等式变形为：
当X = 2时，Y = -2
当X = 6时，Y = -7
当X = 10时，Y = -12
……
而用程序设计的方法，采用枚举算法解本题，方法还是如上所说：
1）一一列举：用循环，现在要采用双重循环：
外循环用X = -50 – 50，内循环用Y = -100 – 100，当然，从循环的道理来讲，内外循环互换位置，结果一样。
2）逐个检验：用选择，条件为：5X + 4Y = 2
这样可以，求得所有满足题意的整数解，现在题目又拐了个弯，要求满足5X + 4Y = 2，确使得X + Y的和为最大的解，那当然要采用一些额外的方法，进行最大值的计算。最大值计算，无非是我们学过的打擂台的思路。
这样，就可以写出整个求解的VB代码：
Dim x As Integer
Dim y As Integer
Dim MaxX As Integer
Dim MaxY As Integer
Dim Max As Integer
Max = -9999
For x = -50 To 50
   For y = -100 To 100
      If 5 * x + 4 * y = 2 Then
         If x + y > Max Then
            Max = x + y
            MaxX = x
            MaxY = y
         End If
      End If
   Next y
Next x
Print "X="; MaxX, "Y="; MaxY, Max
 
4．抓交通肇事犯：一辆卡车违反交通规则，撞人后逃跑。现场有三人目击事件，但是没有记住车号，只记下车号的一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位不同；丙是一位数学家，他说：四位的车号刚好是一个整数的平方。请根据以上的线索求出车号?编程实现之?
我想到这里，应该已经熟悉用枚举算法解决问题的思路与方法了，把分析略了：就给出代码吧！
Dim i As Single
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
 
For i = 0 To 9999
   a = i \ 1000                '得到千位数字
   b = i \ 100 Mod 10          '得到百位数字
   c = i \ 10 Mod 10           '得到十位数字
   d = i Mod 10                '得到个位数字
   If a = b And c = d And a <> c And Int(Sqr(i)) ^ 2 = i Then
      Print i, Sqr(i)
   End If
Next i
 
说明：以上代码，已经通过VB 6 调试运行通过。
2013年6月13日

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。