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)应该可以解决这个问题。