斐波那契数列的若干解法

// 解法1：递归 
/**
这是最容易想到的，但求解大数也是最有问题的。
存在大量重复计算。
一秒内大约能算到第三四十项。 
**/ 

int f1(int n) {
    const int MOD = 1000000007;
    if (n == 0)
    {
        return 0;
    }

    if (n == 1 | n == 2)
    {
        return 1;
    } else {

        return (f1(n - 1) + f1(n - 2))% MOD;
    }

}

// 解法2：
/**
因为我们求的是第n项，
所以也没必要把所有项求出来，
直接利用循环，把第n项求出来即可。

**/ 


int f2(int n)
{
    const int MOD = 1000000007;
    // 得先把0排除
    if (n == 0) 
    {
        return 0;
    }
    int x,y,z;
    x = y = z = 1;
    for (int i=3;i<=n;i++)
    {
        z = (x+y)%MOD;
        x = y;
        y = z;
    }
    return z;
}


int main()
{
    int n;
    cin >> n;
    // 测试。所以，当输入-1结束。 
    while(n != -1)
    {
        int result = f1(n);
        cout << result << endl;
        cin >> n;
    }
    return 0;
}

// 解法3：记忆化搜索。
/**
开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 nn 个状态，计算每个状态的复杂度是 O(1)O(1)，所以时间复杂度是 O(n)O(n)。
一秒内算 n=107n=107 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 n=105n=105 级别。


**/

const int N = 100000, MOD = 1000000007;
int a[N];
int f3(int n) {
    if (n == 0) return 0;
    if (a[n]) return a[n];
    if (n <= 1) return 1;
    a[n] = f3(n - 1) + f3(n-2);
    a[n] %= MOD;
    return a[n];
}
int main() {
    int n;
    cin >> n;
    // 测试。所以，当输入-1结束。
    while(n != -1) {
//      int result = f1(n);
//      int result = f2(n);
        int result = f3(n);
        cout << result << endl;
        cin >> n;
    }
    return 0;
}

// 解法4：递推。
/**
开一个大数组，记录每个数的值。用循环递推计算。
总共计算 nn 个状态，所以时间复杂度是 O(n)O(n)。
但需要开一个长度是 nn 的数组，内存将成为瓶颈，当 n=10^8时
需要的内存是381M。 
**/

const int N = 100000000, MOD = 1000000007;
int a[N];
int f4(int n) {
    if (n == 0) return 0;
    a[1] = a[2] = 1;// 这里得注意以下，数组下标从0开始，我们抛弃0，从1开始 
    for (int i=3; i<=n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
        a[i] %= MOD;
    }

    return a[n];
}
int main() {
    int n;
    cin >> n;
    // 测试。所以，当输入-1结束。
    while(n != -1) {
//      int result = f1(n);
//      int result = f2(n);
//      int result = f3(n);
        int result = f4(n);
        cout << result << endl;
        cin >> n;
    }
    return 0;
}

// 解法5：矩阵运算 + 快速幂。
/**
至今，未理解到。这里先只保存一下代码：

**/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

void mul(int a[][2], int b[][2], int c[][2])
{
    int temp[][2] = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                long long x = temp[i][j] + (long long)a[i][k] * b[k][j];
                temp[i][j] = x % MOD;
            }
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            c[i][j] = temp[i][j];
}


int f_final(long long n)
{
    int x[2] = {1, 1};

    int a[2][2] = {{1, 1}, {1, 0}};

    int res[][2] = {{1, 0}, {0, 1}};
    int t[][2] = {{1, 1}, {1, 0}};
    long long k = n - 1;
    while (k)
    {
        if (k&1) mul(res, t, res);
        mul(t, t, t);
        k >>= 1;
    }

    int c[2] = {0, 0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
        {
            long long r = c[i] + (long long)x[j] * res[i][j];
            c[i] = r % MOD;
        }

    return c[0];
}


int main()
{
    long long n ;

    cin >> n;
    cout << f_final(n) << endl;

    return 0;
}

// 解法6：利用数组。 
/**
看代码吧，技术不到位，不好解释。 

**/

int f6(int n)
{
    // 定义临时数组
    if (n < 1) {
        return 0;
    }
    long double tmp;
    long double *a = new long double[n + 1];
    a[1] = a[2] = 1;
    for (int i = 3; i <= n; ++i) {
        a[i] = a[i - 1] + a[i - 2];
    }
    tmp = a[n];
    delete[]a;
    return tmp;
}
int main()
{
    long long n ;

    cin >> n;
    cout << f6(n) << endl;

    return 0;
}