斐波拉契數列的計算方法

用非遞歸方法計算斐波那契數列，節省時間，包括疊代法，中間變量儲存法，公式法

面試題9、斐波拉契數列

題目：

輸入整數n，求斐波拉契數列第n個數。

思路：

一、遞歸式算法：

利用f(n) = f(n-1) + f(n-2)的特性來進行遞歸，代碼如下：

代碼：

long long Fib(unsigned int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return Fib(n-1) + Fib(n-2);
}      

缺陷：

當n比較大時遞歸非常慢，因為遞歸過程中存在很多重複計算。

二、改進思路：

應該采用非遞歸算法，儲存之前的計算結果，用空間換時間。

代碼如下：

#include<stdio.h>
#include<stdlib.h>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int num1 = 0;
    int num2 = 1;
    for(int i=2;i<n;i++)
    {
        int tmp = num1 + num2;
        num1 = num2;
        num2 = tmp;
    }
    printf("%d", num2);
}      

相似題目：

1、青蛙跳台階，一次可以跳1或者2格，共n階台階，問有多少種上台階的方法？

思路：從後往前想，f(n) = f(n-1) + f(n-2)，轉換成同樣的題目了。

2、矩形覆寫問題，用21的矩形來覆寫28的矩形，小矩形可以橫着或豎着來覆寫，問有多少種方法去覆寫？

思路：橫着覆寫就變成了f(8) = 1+f(8-2)，豎着變成f(8) = 1 + f(8-1)，是以f(8) = f(8-1) + f(8-2)。

轉載來源：http://www.cnblogs.com/puyangsky/p/5826466.html

題目要求：

　　寫一個函數，輸入n，求斐波拉契數列的第n項。斐波拉契數列的定義如下：

　　

　　參考資料：劍指offer第9題、程式設計之美2.9

題目分析：

　　方法1：遞歸法，效率很低，而且會計算很多重複；

#include <stdio.h>

#define uint64 unsigned __int64 

uint64 Fibonacci(int n);

int main(void)
{
    int n;

    while(1)
    {
        printf("請輸入n值：");
        scanf("%d",&n);

        printf("n = %d,Fibonacci(n) = %I64u\n",n,Fibonacci(n));    
    }    
    return 0;
}
uint64 Fibonacci(int n)
{
    if(n <= 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return (Fibonacci(n-1)+Fibonacci(n-2));
}      

　　方法2：疊代法，通過儲存中間項避免重複計算，時間複雜度O(n);

#include <stdio.h>
#include <assert.h>

int main(void)
{
    int n,i = 0;
    int x,y;

    while(1)
    {
        printf("請輸入n值：");
        scanf("%d",&n);
        assert((n >= 0) && (n <= 92));//用這種方法的n最大為92，否則就溢出了。

        i = 0;
        x = 0;
        y = 1;
        while(i < n)
        {
            y = x+y;
            x = y-x;
            i++;
        }
        if(n <= 0)
            y = x;
        printf("n = %d,Fibonacci(n) = %d\n",n,y);

    }    
    return 0;
}      

　　方法3：公式法，時間複雜度O(1),因為公式中引入了無理數，是以不能保證結果的精度；

#include <stdio.h>
#include <assert.h>
#include <math.h>

double Pow(double x,unsigned int n);

int main(void)
{
    int n;
    int fibo;
    double a,b,c;
    a = sqrt(5.0);
    b = (1+a)/2;
    c = (1-a)/2;
    while(1)
    {
        printf("請輸入n值：");
        scanf("%d",&n);
        assert((n >= 0));
        
        int x = pow(b,n);
        int y = pow(c,n);
        fibo = (int)(a*(Pow(b,n)-Pow(c,n))/5);
        printf("n = %d,fibonacci(n) = %d\n",n,fibo);
    }    
    return 0;
}
double Pow(double x,unsigned int n)
{
    double result = 1;
    while(n)
    {
        if(n & 0x01)
            result *= x;
        x  = x*x;
        n >>= 1;
    }
    return result;
}      

　　方法4：分治政策，可以用矩陣來表示

,則

,(這個式子是通過計算A、A2、A3、、、觀察出來的)其中

，則上面這個式子可以表示為：

則F2 = Y2_11 = A（11表示矩陣的第1行1列元素）.

　　　　　現在剩下的問題就是求An了，可以把n用二進制表示：n = ak*2^k + ak-1*2^k-1 + ... + a1*2 + a0，其中ai = 0 或1 ，i = 0,1,2... k。例如：n = 5 = b’101 = 1*22 + 0*21+1*20。這樣

則，我們知道An最多經過log2n乘法就能夠得到，而不用A*A*A這樣計算n次。

代碼實作：

　

#include <stdio.h>
#include <assert.h>

const int MAXLENGTH = 10;

struct Matrix 
{
    unsigned side;
    __int64 dat[MAXLENGTH*MAXLENGTH];//也可以用行/列來表示(row、line)，會更友善一點。
};

// 方陣的乘法 
void MatrixMult(const Matrix a, const Matrix b, Matrix &m)
{
    unsigned int i,j,k;
    assert(a.side == b.side);
    m.side = a.side;
    for (i=0; i < m.side; ++i)
        for (j=0; j < m.side; ++j)
        {
            m.dat[i*m.side+j] = 0;
            for (k=0; k<m.side; ++k)
                m.dat[i*m.side+j] += a.dat[i*a.side+k]*b.dat[k*b.side+j];
        }
}

__int64 Fibonaci(unsigned n)
{
    if (n==0) 
        return 0;

    --n;    // 計算矩陣prod的n-1次幂

    Matrix res;    
    res.side = 2;
    res.dat[0] = 1; res.dat[1] = 0; 
    res.dat[2] = 0; res.dat[3] = 1;

    Matrix prod;        
    prod.side = 2;
    prod.dat[0] = 1;  prod.dat[1] = 1;
    prod.dat[2] = 1;  prod.dat[3] = 0;

    // 隻需要O(logn)的複雜度就能算出x的n次幂  
    while (n)
    {
        // 如果n的最低二進制位為1，則乘上對應的幂次prod
        if (n&1) MatrixMult(res, prod, res);
        MatrixMult(prod, prod, prod);
        n >>= 1;
    }
    return res.dat[0];
}

int main(void)
{
    int i;

    for(i = 0;i < 20;i++)
    {
        printf("%I64u\n",Fibonaci(i));
    }
    
    return 0;
}      

轉載來源：http://www.cnblogs.com/tractorman/p/4058305.html