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

Question

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

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

你能帮我看看我的代码有什么问题吗？或者这个算法是不是错了。

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

#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

Answer 1

您需要更改算法。

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

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

注意 89+44 得到 133，它以 33 结尾，就像 89+144 得到 233，它也以 33 结尾。

将两者结合后，您将需要一个循环，计数器会显示 82364572389，并执行简单的 additions/modulos。它应该在几分钟内结束，顶部。

到达那里后，您可以开始考虑进一步的优化（有）。不过上面两个应该够了。

另外，根据评论，重新阅读问题：

calc_fib(n) - calc_fib(m-1)

是错误的，因为它可能会产生负数。而最后一位数字必须为正数。您可能需要考虑这个差异 diff，然后执行：

diff = (diff + 10) % 10;

让它变得积极。

最后，为什么是 9？为什么 return (fib[n]%10-1); 中的 -1 ？这似乎将所有内容都抵消了一个，但是减法中的两个 -1 都抵消了。

Answer 2

在for循环内继续求和，如下：

#include <iostream>
using namespace std;

int main() {
    unsigned int i, j, n, v, sum;

    cout << "Fibonacci numbers from 1 to 10000: " << endl;

    cout << '1' << endl;
    cout << '1' << endl;
    cout << '2' << endl;
    for (i = j = v = 1, n = 2, sum = 4; n + j < 10000; sum += v) {
        v = n + j; i = j; j = n; n = v;
        cout << v << endl;
    }

    cout << "Sum of Fibonacci numbers from 1 to 10000: " << sum << endl;

    return 0;
}

已添加 LINK 测试代码 [http://codepad.org/8CHIepXe]

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

Last Digit in Sum of Fibonacci Series (m,n)

c++

fibonacci