迭代斐波那契算法在 fib(47) 之后给我一个错误的结果
Iterative Fibonacci algorithm giving me a wrong result after fib(47)
我正在使用我在下面复制的迭代 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)
请注意，您在代码中使用的是 int 类型的临时变量，而不是 long long int 类型。这意味着，如果您到达处理足够大的斐波那契数的地步，您的代码将出现整数溢出。特别是，第 47 个斐波那契数是 2,971,215,073，它太大而无法放入带符号的 32 位整数中，因此会溢出。
将您的临时变量更改为类型 long long int（或者，更好的是 uint64_t）应该可以解决此问题。
你必须对 fnow, fnext, and tempf 使用 long long，试试：
long long int fnow = 0, fnext = 1, tempf;
将变量设为 long long 而不是 int。 'int' 取决于机器可能是 64、32、16 或 8 位。
如果您想自己指定整数的大小并制作可移植代码，请使用 uint8_t、uint16_t 等或 int8_t、int16_t等。 'u' 代表无符号。这是 stdint.h 库的一部分！
我正在使用我在下面复制的迭代 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)
请注意，您在代码中使用的是 int 类型的临时变量，而不是 long long int 类型。这意味着，如果您到达处理足够大的斐波那契数的地步，您的代码将出现整数溢出。特别是，第 47 个斐波那契数是 2,971,215,073，它太大而无法放入带符号的 32 位整数中，因此会溢出。
将您的临时变量更改为类型 long long int（或者，更好的是 uint64_t）应该可以解决此问题。
你必须对 fnow, fnext, and tempf 使用 long long，试试：
long long int fnow = 0, fnext = 1, tempf;
将变量设为 long long 而不是 int。 'int' 取决于机器可能是 64、32、16 或 8 位。
如果您想自己指定整数的大小并制作可移植代码，请使用 uint8_t、uint16_t 等或 int8_t、int16_t等。 'u' 代表无符号。这是 stdint.h 库的一部分！