C++带记忆化的斐波那契函数计算出现负数结果的原因咨询

你遇到的负数问题，本质是有符号整数溢出导致的环绕行为，和记忆化实现完全无关——两个版本都出问题，是因为它们计算的是同一个斐波那契数列，当数值超过int类型的最大值时，就会触发溢出。

为什么会变成负数？ #

现代系统中，int通常是32位有符号整数，它的取值范围是 -2^31（-2147483648）到 2^31-1（2147483647）。

我们来算一下斐波那契数列的临界项：

• 第46项：fib(46) = 1836311903，这个值还在int的范围内
• 第47项：fib(47) = fib(46) + fib(45) = 1836311903 + 1134903170 = 2971215073，这个值已经超过了2^31-1（2147483647）

对于有符号整数，溢出属于C++标准中的未定义行为，但绝大多数编译器会按照补码环绕的方式处理：当数值超过最大值时，会从最小值开始重新计数，原本的正数就变成了负数——这就是你看到第47项及以后出现负数的原因。

为什么换成double还是出负数？ #

你提到替换成double仍然出现负数，大概率是因为你没有彻底修改类型：

• 如果只是把数组seq的类型改成double，但函数返回类型还是int，计算出的double值会被强制转换为int，当数值超过int范围时，依然会溢出变成负数
• 或者在输出时，你把double值转成了int类型输出，同样会触发溢出

double类型的整数精确表示范围是到2^53（约9e15），斐波那契数列到第70项左右才会超出这个范围，所以只要全程用double处理（函数返回、数组、输出都用double），就不会出现负数，但超过2^53后会丢失精度（变成近似值）。

解决方案 #

根据你的需求，可以选择以下几种方式：

1. 使用更大的整数类型

最直接的办法是改用64位整数类型，比如long long（或C++11标准的int64_t），它的范围是 -9223372036854775808 到 9223372036854775807，足够计算到斐波那契第90项左右。

修改你的fibo函数示例：

long long fibo(int i) // Recursive & Memoisation
{
    static int const maxIndex = 2000;
    static long long seq[maxIndex] = {0, 1};
    static int count = 2;
    if(i < count){return seq[i];}
    long long temp = fibo(i-2) + fibo(i-1);
    count = count + 1;
    seq[i] = temp;
    return temp;
}

同时main函数中的输出也不需要额外修改，cout可以直接输出long long类型的值。

2. 使用无符号整数

如果不需要负数，可以用unsigned long long，它的范围是0到18446744073709551615，能计算到第93项左右。

3. 任意精度整数（如果需要更大的项）

如果要计算第100项甚至更大的斐波那契数，需要用任意精度整数库，比如GMP（GNU Multiple Precision Arithmetic Library），或者自己实现大整数加法逻辑（用字符串或数组存储每一位数字）。

总结 #

你的两个版本都出问题，是因为它们都用int存储计算结果，当数值超过int范围时必然溢出。改用更大的整数类型可以解决这个问题，而double的问题是因为你没有全程使用该类型处理数据。

内容的提问来源于stack exchange，提问作者user14389165