3.4  穷举法和递推问题求解

3.4.1 穷举法

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法有如下三种：

（1）顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

（2）排列列举有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。

（3）组合列举当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。

【例1】求1000以内的“水仙花数”。（注：“水仙花数”是一个三位数，其每一位数的立方和等于该数本身，例如153＝13＋53＋33。）

算法设计：三位数n中的每一位上的数可以表示为：

百位i：i=int（n/100）

十位j：j=int（n/10）-i*10

个位k：k=n Mod 10

程序代码：

Private Sub Form_Click()

Dim i As Integer, j As Integer, k As Integer, n As Integer

For n = 100 To 999

i = Int(n / 100)

j = Int(n / 10) - 10 * i

k = n Mod 10

If n = i ^ 3 + j ^ 3 + k ^ 3 Then Print n;

Next

End Sub

程序运行结果如图1所示。

3.4.2 递推法

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。

【例2】输出菲波拉契数列的前20项。斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

根据菲波拉契数列的定义，数列的前两项是0和1，以后每项均为其前两项的和，即依次为0，1，1，2，3，5，8，13，21……。程序代码如下：

Private Sub Form_Click()

Dim a%, b%, i%

a = 0

b = 1

Print a

Print b

For i = 3 To 24

c = a + b

Print c

a = b

b = c

Next i

End Sub

=============================================================================

============================================================================