斐波那契数列的若干解法

无道 2019-06-06 0 条评论 算法分享 阅读252 手机阅读

以下很多参考Acwing:https://www.acwing.com/blog/content/25/

解法1

// 解法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

// 解法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

// 解法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

// 解法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

// 解法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

// 解法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;
}

总结:

其实除了解法5和递归解法,其余解法均差不多是利用数组和循环。

全文完 [
有帮助?打赏
支付宝打赏
微信打赏
]
修改: 2019-06-06 14:24
这篇文章还没有评论呢~
点击刷新/生成验证码
It's me
昵称:无道
坐标:成都
性别:
一个人,一介学生,一个儿子~ 愿你我都被世界温暖以待
迷思爱 公众号

新建了个公众号,会不定期分享一些小玩意,有提升效率的办公软件、有一些黑科技的软件、或教程等等。

爷~,要不关注下~~