编程小博士(34)：滴水不漏──穷举法破解难题
软件世界
问：小博士，前面你给我讲解了递推法，所以每当我遇到新的问题的时候，我都会尝试找寻规律来解决问题。但我发现有些问题的规律还真难找，比如这样一个题目：公鸡3元每只，母鸡5元每只，小鸡1元3只，一百元钱买一百只鸡，请求出公鸡，母鸡和小鸡的数目。
我想了半天，如果不靠探寻规律，怎么能解决这类问题呢？
小博士：穷举法是是一种看似笨拙的算法，但在解决一些特定的问题时却非常有效，你刚才问的‘百钱买百鸡’的问题就可以用穷举法来解决。穷举法就是要列举所有可能的解决问题的方法，一一验证。下面来看看你提的问题的具体解法。
思路简析
我们做最极端的假设，公鸡数目可能是0～100只，母鸡数目可能也是0～100只，小鸡也是一样，将这三种情况用循环考虑验证符合题目的情况，那就要做1000000种情况分析。这就是穷举法。当然，在解决这个具体问题时我们可以将情况简化一下，以提高运算速度：
假设公鸡数为x只，母鸡数为y只，则小鸡数就是100-x-y只，根据题意也就有了下面的方程式：
3×x+5×y+(100-x-y)÷3=100
从这个方程式中，我们不难看出大体的情况：公鸡最多有33只，最少是没有，即x的范围先可缩小为0～33；母鸡最多20只，最少0只，即y的范围可缩小为0～20；有了公鸡母鸡数，小鸡数自然就是100-x-y只。可能的方案一共有34×21种，在这么多的方案中，可能有一种或几种正好符合相等的条件。
那么穷举法的工作是什么呢？当然就是将上述34×21种方案全部扫描一遍，找出符合“百钱买百鸡”条件的情况，然后将我们要的结果输出。
我们怎样将这34×21种方案罗列出呢？这么多的方案，最好的办法是还是用循环。可用两层循环的嵌套，即将一个关于公鸡数和一个关于母鸡数的循环嵌套起来，就能将所有的方案都遍历一遍。后面的问题就成了怎样判断哪一个方案是我们寻找的符合条件的方案呢？只能根据“百钱买百鸡”，即3×x+5×y+(100-x-y) ÷3=100作为条件，在条件成立时输出x、y的值和100-x-y的值就行了。
程序实现
我们也可以为我们的程序创建一个简单的界面。建立一个标准EXE工程，将它的Caption设为“百钱买百鸡”。我们可以简单的将代码加载在Form_Click()里，即窗体的单击事件。程序运行时，我们只要用鼠标随便单击一下窗体，就能得到结果了。
源程序如下：
Option Explicit
Private Sub Form_Click()
Dim x, y As Integer ‘声明变量
For x = 0 To 33 ‘两层循环解决问题
For y = 0 To 20
If 3 * x + 5 * y + (100 - x - y) / 3 = 100 Then
Print “公鸡，母鸡和小鸡数分别为：”; x, y, 100 - x - y
End If
Next y
Next x
End Sub
(以上程序在VB6.0 Win2000下调试通过)
输出的结果有多组，也正和我们刚开始的所想相符。
小结
这就是列举法，将可能的情况一网打尽；不过在应用过程中，我们最好还是根据具体问题适当做些优化，缩小穷举的范围，以加快运算的速度。
对于某些问题，会出现可能的情况不多，但用程序实现穷举比较困难的情况。这时我们可以尝试自己来做穷举的工作，这期编程魔方的“看实例玩编程”就为大家提供了一个展示才能的舞台。读者可以照文章的思路自己体验一把 “穷举”，也可以提供一个优秀的算法，让电脑“穷举”，为你服务。总之，不但能学习，还可以参与，机会希望大家不要错过！