九度编程挑战：斐波那契数列的高效算法解析

题目来源：http://ac.jobdu.com/problem.php?pid=1387

#include 
#include 
#include 

using namespace std;

typedef long long LL;

LL Fab(int n)
{
    LL a[2] = {0, 1}, i;
    if(n <2)
        return a[n];
    for(i = 2; i <= n; ++i)
        a[i%2] = a[(i-1)%2] + a[(i-2)%2];
    return a[n%2];
}

int main()
{
    int n;
    while(~scanf("%d", &n))
        printf("%lld\n", Fab(n));
    return 0;
}

解法二：

学过高数的同学，我们都知道斐波那契数列的递推公式可以写成如下形式：

如此，我们只要求出等式右边矩阵的n-1幂，就可以求出f(n)。

求矩阵的n-1次幂，可以借助快速幂来求解。

#include 
#include 
#include 

typedef long long LL;

struct Matrix
{
    LL iMatrix[2][2];
};

Matrix iPer, iCell;

void Inite()
{
    for(int i = 0; i <2; ++i)
    {
        for(int j = 0; j <2; ++j)
        {
            iPer.iMatrix[i][j] = (i == j);
            iCell.iMatrix[i][j] = 1;
        }
    }
    iCell.iMatrix[1][1] = 0;
}

Matrix Multi_Matrix(Matrix a, Matrix b)
{
    Matrix c;
    for(int i = 0; i <2; ++i)
    {
        for(int j = 0; j <2; ++j)
        {
            c.iMatrix[i][j] = 0;
            for(int k = 0; k <2; ++k)
                c.iMatrix[i][j] += a.iMatrix[i][k] * b.iMatrix[k][j];
        }
    }
    return c;
}

Matrix Quick_Mod(int k)
{
    if(k == 1)
        return iCell;
    Matrix c = iPer;
    Matrix b = iCell;
    while(k)
    {
        if(k & 1)
        {
            c = Multi_Matrix(c, b);
            k--;
        }
        b = Multi_Matrix(b, b);
        k >>= 1;
    }
    return c;
}

int main()
{
    int n;
    Matrix c;
    Inite();
    while(~scanf("%d", &n))
    {
        if(n == 0)
        {
            printf("0\n");
            continue;
        }
        c = Quick_Mod(n-1);
        printf("%lld\n", c.iMatrix[0][0]);
    }
    return 0;
}