Fibonacci数列

问题介绍

斐波那契数列是这样的一组数列：

这个数列从第三项起，每一项都等于前两项之和。

现在输入一个正整数n,输出数列中的第n个数。

解决方法

分治法

int Fibonacci(int n)
{
   if(n < 2) return n;  //如果n为0，则直接返回0，如果n为1，则直接返回1
   else return  Fibonacci(n - 1) + Fibonacci (n - 2);  //如果n为大于1，返回前两项的结果之和
}

递归的缺点非常明显，求解过程中有相当多次的重复运算，时间复杂度高，效率十分低下，比如，在计算Fibonacci (7) = Fibonacci(6) + Fibonacci(5)和Fibonacci(6) = Fibonacci(5) + Fibonacci(4)时，共需要计算Fibonacci(5)两次，推广到整个计算过程，有大量的时间被浪费。

动态规划法

int Fibonacci(int n)
{
   if(n < 2) return n;  //如果n为0，则直接返回0，如果n为1，则直接返回1
   else 
          {
             int array[n+1];
             array[0] = 0 ;
             array[1] = 1 ;
             for (int i = 2; i < n+1; i++) 
             {
                array[i] = array[i-1] + array[i-2];    //直接利用数组里的数值进行计算
             }  //for
            return array[n-1];
          }   //else
 }

用一个数组来保存数列，是典型的以空间换时间的做法，缩短了大量计算时间，大大提高了算法的计算效率。