穷竭搜索算法

[duoan]

---

穷竭搜索

穷竭搜索是将所有的可能性都罗列出来，在其中寻找答案的方法

递归函数

在一个函数中再次调用函数自身的行为叫做递归，这样的函数被成为递归函数。

阶乘

$n!=n*(n-1)!$

我们可以简单的实现如下函数：

int fact(int n){
  if ( n == 0 ) return 1;
  return n * fact(n - 1);
}

需要强调的是在递归函数中，一定需要一个停止条件。如上面的函数中，当n = 0 时 fact 并不是继续调用自身，而是直接返回1。如果没有这一个条件存在，函数就会无限地递归下去，程序直接失控崩溃。

Title : fact递归过程
fact(10)->fact(9):
fact(9)->fact(8):
fact(8)-> ... :
 ... -> fact(0):

斐波那契额数列

$ a{n}=a{n-1}+a{n-2} (n>1) $ $a{0}=0 、a_{1} = 1$

根据之前的递归函数的写法和原则，我们知道斐波那契额数列的递归终止条件就是初项的条件。所以直接将数列的定义写成函数就可以了。

int fib(int n) {
  if(n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

但是，在使用时你会发现，即使我们计算一个fib（40）这样的较小的结果，也是要花费相当长的时间。这就是因为这个函数本身使用了递归，调用时会像下图一样按照指数级别扩展。

Title : fib(10)递归过程
fib(10)->fib(9):
fib(10)->fib(8):
fib(9)->fib(8):
fib(9)->fib(7):
fib(8)->fib(7):
fib(8)->fib(6):
fib(7)->fib(6):
fib(7)-> ... :

在斐波那契数列中，如果fib(n)的n是一定的，无论多少次调用都会得到相同的结果。因此如果计算一次之后，用数列将结果存起来，便可优化之后的计算。上图中fib(10)被调用的时候同样的n被计算了很多次，因此从这个角度出发算法就有很大的可优化空间。这样的方法是出于记忆搜索或者动态规划的想法。

int memo[ MAX_N + 1]

int fib(n) {
  if(n <= 1) return n;
  if(memo[n] != 0) return memo[n];
  return memo[n] = fib(n - 1) + fib(n - 2); 
}