1 递归法
1 // 19_1.cc 2 #include <iostream> 3 using namespace std; 4 5 size_t fibo(size_t n) { 6 if (n < 2) 7 return n; 8 else 9 return fibo(n - 1) + fibo(n - 2); 10 } 11 12 int main() { 13 size_t n; 14 cout << "please input n:" << endl; 15 cin >> n; 16 cout << "The Fibonacci is: " << fibo(n) << endl; 17 return 0; 18 }
使用递归，会有大量的重复计算，以计算fibo(8)为例：
从下往上递推，避免重复计算。
1 // 19_2.cc 2 #include <iostream> 3 using namespace std; 4 5 size_t fibo(size_t n) { 6 if (n < 2) 7 return n; 8 9 size_t f1 = 0; 10 size_t f2 = 1; 11 size_t res; 12 for (size_t i = 2; i <= n; i++) { 13 res = f1 + f2; 14 f1 = f2; 15 f2 = res; 16 } 17 return res; 18 } 19 20 int main() { 21 size_t n; 22 cout << "please input n:" << endl; 23 cin >> n; 24 cout << "The Fibonacci is: " << fibo(n) << endl; 25 return 0; 26 }
IT公司100题-19-求Fibonacci数列,布布扣,bubuko.com
原文：http://www.cnblogs.com/dracohan/p/3904932.html