时间戳

首页 > 解决方案 > 斐波那契数列和的最后一位 (m,n)

c++ - 斐波那契数列和的最后一位 (m,n)

问题描述

我对找到从索引 m 到索引 n 的斐波那契数列的项总和的最后一位存有疑问（考虑起始项的索引为 0）。

我有很多不同的方法来解决这个问题。但是对于 ex m=2,n=82364572389 等，也需要通过很长的案例。但是当我尝试使用这个算法时，我的一些测试用例通过了，但有些没有。

S 你能帮我看看我的代码有什么问题还是这个算法有问题。

还有如何用更好的方法来解决这个问题。

#include <iostream>
using namespace std;

long long calc_fib(long long n) {

    n = (n+2)%60;
    int fib[n+1];
    fib[0]=0;
    fib[1]=1;
    int res = 1;
    for(int i = 2; i<=n;i++){
        fib[i] = (fib[i-1]%10 + fib[i-2]%10)%10;
        // res = res + fib[i];
    }
    // cout<<fib[n]<<"\n";
    if(fib[n] == 0){
        return 9;
    }
    return (fib[n]%10-1);
}

int main() {

long long n = 0,m;

std::cin >> m;

    std::cin >> n;

    std::cout << calc_fib(n)-calc_fib(m-1) << '\n';
    return 0;
}

测试用例

Test Case: 5 10
Correct Output: 6
My Output: -4

Test Case: 1 10000000
Correct Output: 5
My Output: 5

标签： c++fibonacci

解决方案

你需要改变你的算法。

第一件事：不要递归计算值。就运行时而言，这非常昂贵。从 f(0) 开始，然后是 f(1)，然后使用最后存储的两个值计算 f(2)。继续这样。仅存储最后两个值。

第二：意识到完全存储 f(n) 是没有意义的。您可以只保留单位和十位（十位不是必需的，但有助于调试）。这看起来像：1、1、2、3、5、8、13、21、34、55、89、44、33

请注意，89+44 给出 133，它以 33 结尾，就像 89+144 给出 233，它也以 33 结尾。

将两者结合起来后，您将需要一个循环，计数器会说 82364572389，并执行简单的加法/模运算。它应该在几分钟内结束，顶部。

在那里，您可以开始考虑进一步的优化（有）。但是上面两个应该就够了。

另外，从评论中，并重新阅读问题：

calc_fib(n) - calc_fib(m-1)

是错误的，因为它可能会产生负数。而最后一位数字必须是正数。您可能需要采用这种差异diff，并执行以下操作：

diff = (diff + 10) % 10;

使其积极。

最后，为什么是 9 ？为什么 -1 in return (fib[n]%10-1);？这似乎抵消了一切，但减法中的 -1 都抵消了。

推荐阅读