斐波那契数列

斐波那契数列（意大利语: Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*），用文字来说，就是斐波那契数列列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。特别指出：0不是第一项，而是第零项。

#include
int fun(int n)      //n代表第几项。特别指出：0是第0项，不是第1项。
{
    if (n <= 1)
        return n;
    else
        return fun(n-1) + fun(n-2);
}

改进1：求Fibonacc数列第n项时虽然要用到前面两项的值，但它们仅作为临时计算的中间值，不作为结果输出，因此无保留的必要，完全可以转化为迭代法求解：

 1 unsigned int Fibonacci(int n){
 2     int n;
 3     unsigned long a = 0, b = 1, c;
 4     if(n == 1){
 5         return 0;
 6     }else{
 7         for(int i = 0; i < n; i ++){
 8             c = a + b;
 9             a = b;
10             b = c;
11         }
12      return c;
13     }
14 }

改进2：同上

 1 long long Fibonacci(unsigned n){
 2     int result[2] = {0, 1};
 3     if(n < 2){ 
 4         return result[n];
 5     }
 6     long long fibNMinusOne = 1;
 7     long long fibNMinusTwo = 0;
 8     long long fibN = 0;
 9     for(unsigned int i = 2; i <= n; i ++){
10         finN = fibNMinusOne + finNMinusTwo;
11         
12        fibNMinusTwo = fibNMinusOne;
13        fibNMinusOne = fibN;
14     }
15     return fibN;
16 }