一．问题

上海市普通高中在信息科技学科中开展《算法与程序设计》教学，教材中有一章名为“算法实例”的内容，其中有一节介绍“枚举算法”。教材中关于枚举算法的描述：有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些符合要求的。这种方法叫做枚举算法（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日