IT公司100题-19-求Fibonacci数列

问题描述：

定义Fibonacci数列的定义如下：

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

给定n，求Fibonacci数列的第n项。

分析：

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)为例：

2 避免重复计算法

从下往上递推，避免重复计算。

 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 }