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 递归法

 // 19_1.cc

 #include <iostream>

 using namespace std;

 size_t fibo(size_t n) {

     if (n < )

         return n;

     else

         return fibo(n - ) + fibo(n - );

 }

 int main() {

     size_t n;

     cout << "please input n:" << endl;

     cin >> n;

     cout << "The Fibonacci is: " << fibo(n) << endl;

     return ;

 }

使用递归，会有大量的重复计算，以计算fibo(8)为例：

2 避免重复计算法

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

 // 19_2.cc

 #include <iostream>

 using namespace std;

 size_t fibo(size_t n) {

     if (n < )

         return n;

     size_t f1 = ;

     size_t f2 = ;

     size_t res;

     for (size_t i = ; i <= n; i++) {

         res = f1 + f2;

         f1 = f2;

         f2 = res;

     }

     return res;

 }

 int main() {

     size_t n;

     cout << "please input n:" << endl;

     cin >> n;

     cout << "The Fibonacci is: " << fibo(n) << endl;

     return ;

 }