c - 迭代斐波那契算法在 fib(47) 之后给出了错误的结果

Question

我正在使用下面复制的迭代 fib 算法。我在 Rosetta 代码上找到了这个算法，它给了我正确的答案，直到 fib(46)。之后它的值是错误的。有谁知道为什么会这样吗？

long long fibb(int n)
{
    int fnow = 0, fnext = 1, tempf;
    while(--n > 0) {
        tempf = fnow + fnext;
        fnow = fnext;
        fnext = tempf;
    }
    return fnext;   
}

输出:

Fib(46) = 1836311903            <---- Correct
Fib(47) = 18446744092385799393   <---- Wrong (Correct Answer is: 2971215073)

Answer 1

请注意，您在代码中使用的是 int 类型的临时变量，而不是 long long int 类型。这意味着，如果您要处理足够大的斐波那契数，您的代码中将会出现整数溢出。特别是，第 47 个斐波那契数是 2,971,215,073，它太大，无法容纳有符号的 32 位整数，因此会发生溢出。

将临时变量更改为 long long int 类型(或者更好的是 uint64_t)应该可以解决此问题。