时间戳

首页 > 解决方案 > 调试代码以写入 n 个斐波那契数的平方和的最后一位

c++ - 调试代码以写入 n 个斐波那契数的平方和的最后一位

问题描述

我使用约定 F_0 = 0、F_1 = 1 等等，其中 F_n 是斐波那契数。我编写了用于查找 n 个斐波那契数的平方和的最后一位的代码。它给出了 n<60 的正确答案。n = 60 起它给出了错误的答案。有人可以帮忙吗？

#include<iostream>

using namespace std;

long long fib_last_sq (long long);     // finds the last digit of the square of F_n
long long sum_fibonacci_sq(long long); // finds sum of last digits of sq of fibonacci numbers
long long PISANO_PERIOD = 60; // pisano period for F_n%10

int main()
{
    long long n=0;
    cin >> n;
    cout << sum_fibonacci_sq(n);
}

long long fib_last_sq (long long n)
{
    if (n<=1)
    {
        return n;
    }

    n = n%PISANO_PERIOD;
    long long prev = 0;
    long long curr = 1;
    for (int i=0; i<n-1; i++)
    {
        long long temp = curr % 10;
        curr = (prev % 10 + curr % 10)%10;
        prev = temp;
    }
    return curr*curr % 10;
}
long long sum_fibonacci_sq(long long n)
{
    if (n==0)
    {
        return 0;
    }
    else if (n==1)
    {
        return 1;
    }
    else
    {
        long long sum = 0;
        for (int i=0; i<n; i++)
        {
            sum += fib_last_sq(i+1);
            sum = sum % 10;
        }
        return sum;
    }
}

标签： c++fibonacci

解决方案

考虑计算斐波那契数平方的最后一位的函数：

long long fib_last_sq (long long n)
{
    if (n<=1)
    {
        return n;
        //     ^   If n == 0, 0 is returned, here.
    }

    n = n % PISANO_PERIOD;
    // If n is a multiple of 60, now n becomes 0...

    long long prev = 0;
    long long curr = 1;
    //        ^^^^^^^^
    for (int i=0; i<n-1; i++)
    //            ^^^^^           ... So that this loop is skipped...
    {
        // ...
    }
    return curr*curr % 10;
    //     ^^^^^^^^^              ... and 1 is returned, instead of 0.
}

您已经知道皮萨诺时期，但是将这 60 个数字打印成两行，我们可以看到一个模式：

0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9
0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1

平方模 10 的周期是 30，它们是

0 1 1 4 9 5 4 9 1 6 5 1 6 9 9 0 9 9 6 1 5 6 1 9 4 5 9 4 1 1

最后，总和的最后一位

0 1 2 6 5 0 4 3 4 0 5 6 2 1 0 0 9 8 4 5 0 6 7 6 0 5 4 8 9 0

完整的算法（假设 c++20 是一个选项）可以写成如下

#include <array>
#include <numeric>
#include <iostream>

namespace details {

constexpr inline size_t period{ 30 };

constexpr auto make_lut()
{
    std::array<int, period> lut{0, 1};
    for (size_t i{2}; i < lut.size(); ++i) {
        lut[i] = (lut[i - 1] + lut[i - 2]) % 10;
    }
    std::partial_sum(lut.begin(), lut.end(), lut.begin(),
        [](int acc, int value){ return (acc + value * value) % 10; }
    );
    return lut;
}

}

int last_digit_of_sum_of_squares_of_fibonacci(long long n)
{
    if (n < 0)
        return 0;
    static constexpr auto lut = details::make_lut();
    return lut[n % details::period];
}

int main()
{
    long long n;
    while ( std::cin >> n)
        std::cout << last_digit_of_sum_of_squares_of_fibonacci(n) << '\n';
}

在这里可以测试。

推荐阅读