学步园

f(n) = f(n -1) + f(n-2)

f(0) = 0;

f(1) = 1;

通常问题是求最快的计算方法：1、循环；2求通项公式；3其他

相关问题：上楼有两种上法，每次上一级或每次上量级，问如果楼梯有n级总共有多少种上楼方法

考察上到第n曾楼梯的方法有两种，一种是从n-1层上来，还有一种是从n-2层上来，因此到n层的方法是f(n) = f(n-1) + f(n-2)

下面给出递归和循环的程序：

#include <stdio.h>
#include <boost/scoped_ptr.hpp>
#include <sys/time.h>
unsigned int Fibonacci(int value) {
  if (value == 0) {
    return 0;
  } else if (value == 1) {
    return 1;
  } else {
    return Fibonacci(value -1) + Fibonacci(value - 2);
  }
}
unsigned int Fibonacci_1(unsigned int value) {
  if (value < 0) {
    return -1;
  }
  boost::scoped_ptr<unsigned int> fibonacci_buffer(new unsigned int[value + 1]);
  unsigned int* fibonacci = fibonacci_buffer.get();
  fibonacci[0] = 0;
  fibonacci[1] = 1;
  for (int i = 2; i <= value; ++i) {
    fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
  }
  return fibonacci[value];
}
int GetTime() {
  timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000 + tv.tv_usec;
}
int main(int argc, char** argv) {
  int start;
  start = GetTime();
  printf("algorithm1 recursive %d\n",Fibonacci(45));
  printf("time elapse:%d\n", GetTime() - start);
  start = GetTime();
  printf("algorithm2 loop %d\n", Fibonacci_1(45));
  printf("time elapse:%d\n", GetTime() - start);
}

--------------------------------result-------------------------
./a.out 
algorithm1 recursive 1134903170
time elapse:24385020
algorithm2 loop 1134903170
time elapse:56

从实验结果看，循环的效率要远远高于递归的效率。

参考文献：

编程之美2.9

百度百科http://baike.baidu.com/view/816.htm