我正在编写代码来获取非常大的斐波那契数的最后一位，例如 fib(239) 等。我正在使用字符串来存储数字，从头到尾抓取各个字符，然后将它们转换为 int而不是将值存储回另一个字符串。我无法测试我所写的内容，因为我的程序在 std::cin >> n; 行之后突然关闭。 这是我到目前为止所拥有的。

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using namespace std; 

char get_fibonacci_last_digit_naive(int n) {
cout << "in func";
if (n <= 1)
    return (char)n;

string previous= "0";
string current= "1";

for (int i = 0; i < n - 1; ++i) {
    //long long tmp_previous = previous;
    string tmp_previous= previous; 

    previous = current;

    //current = tmp_previous + current; // could also use previous instead of current
    // for with the current length of the longest of the two strings
    //iterates from the end of the string to the front
    for (int j=current.length(); j>=0; --j) {
        // grab consectutive positions in the strings & convert them to integers
        int t;
        if (tmp_previous.at(j) == '\0') 
            // tmp_previous is empty use 0 instead
            t=0;  
        else
            t = stoi((string&)(tmp_previous.at(j))); 
        int c = stoi((string&)(current.at(j)));
        // add the integers together
        int valueAtJ= t+c;
        // store the value into the equivalent position in current
        current.at(j) = (char)(valueAtJ); 
    }
    cout << current << ":current value"; 
}

return current[current.length()-1];
}

int main() {
int n;
std::cin >> n;

//char& c = get_fibonacci_last_digit_naive(n);  // reference to a local variable returned WARNING
// http://stackoverflow.com/questions/4643713/c-returning-reference-to-local-variable
cout << "before call";
char c = get_fibonacci_last_digit_naive(n);
std::cout << c << '\n';

return 0;
}

输出始终相同。无论我为 n 输入什么，输出总是相同的。这是我用来运行代码及其输出的行。

$ g++ -pipe -O2 -std=c++14 fibonacci_last_digit.cpp -lm

$ ./a.exe
10

10后有一个换行符，10是我输入的n。 我感谢任何帮助。节日快乐!

最佳答案

我发布此消息是因为您对问题的理解似乎让位于尝试部署的解决方案的选择。这是 XY Problem 的示例，解决方案方法的选择及其实现的问题或障碍混淆了您试图解决的实际问题。

您正在尝试计算第 N 个 Fibonacci number 的最后一位数字，其中 N 可能是合群的。斐波那契数列的基本理解告诉你

fib(0) = 0 
fib(1) = 1 
fib(n) = fib(n-1) + fib(n-2), for all n larger than 1.

解决 fib(N) 的值的迭代解决方案是:

unsigned fib(unsigned n)
{
    if (n <= 1)
        return n;

    unsigned previous = 0;
    unsigned current = 1;
    for (int i=1; i<n; ++i)
    {
        unsigned value = previous + current;
        previous = current;
        current = value;
    }
    return current;
}

一切都很好，但是一旦 N 导致我们选择的数据类型的存储能力溢出(在上面的例子中，unsigned大多数 32 位平台将在仅仅 47 次迭代后溢出)。

但是我们不需要每次迭代的实际 fib 值。我们只需要每次迭代的最后一位。好吧，以 10 为底的最后一位很容易从任何无符号值中获得。对于我们的示例，只需将其替换为:

current = value;

用这个:

current = value % 10;

给我们一个近乎相同的算法，但在每次迭代中只“记住”最后一位数字:

unsigned fib_last_digit(unsigned n)
{
    if (n <= 1)
        return n;

    unsigned previous = 0;
    unsigned current = 1;
    for (int i=1; i<n; ++i)
    {
        unsigned value = previous + current;
        previous = current;
        current = value % 10; // HERE
    }
    return current;
}

现在 current 始终保存先前总和的最后一位数字，无论该先前总和是否超过 10 与我们无关。一旦我们有了下一次迭代就可以用它来计算两个单个正数的总和，不能超过 18，同样，我们只需要 from that 的最后一位 next 迭代，等等。这一直持续到我们迭代请求的次数为止，完成后，最终答案将出现。

验证

我们知道前 20 个左右的斐波那契数看起来像这样，通过 fib 运行:

0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:13
8:21
9:34
10:55
11:89
12:144
13:233
14:377
15:610
16:987
17:1597
18:2584
19:4181
20:6765

以下是我们通过 fib_last_digit 运行算法时得到的结果:

0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:3
8:1
9:4
10:5
11:9
12:4
13:3
14:7
15:0
16:7
17:7
18:4
19:1
20:5

这应该会让您萌生信心，这很可能就是您要寻找的算法，并且您可以完全放弃字符串操作。

关于C++程序在cin之后突然结束，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41337227/