C++使用unordered_map实现备忘斐波那契数列超过46输出异常求解

异常原因 #

C++ 中默认的int为32位有符号整型，常规取值范围是 -2^31 ~ 2^31-1（即-2147483648 到 2147483647）。斐波那契数列增长速度极快：fib(46) = 1836311903 仍在int取值范围内，而fib(47) = 2971215073已经超过int最大值，触发有符号整数溢出，这在C++中属于未定义行为，因此会输出异常值。
而Python的int为任意精度大整数，不存在溢出限制，因此可以正常计算更大的n值。

修正方法 #

将存储斐波那契数值的类型替换为取值范围更大的64位有符号整型long long即可，其取值范围为-2^63 ~ 2^63-1，可以支持计算到fib(92)不溢出。

修正后的完整代码如下：

#include<iostream>
#include<unordered_map>

using std::unordered_map;
using std::cout;

long long fib(int num, unordered_map <int, long long> &Dict)
{
  if (Dict.find(num) != Dict.end())
  {
    return Dict[num];
  }

  if (num <= 2)
  {
    return 1;
  }

  Dict[num] = fib(num-1, Dict) + fib(num-2, Dict);
  return Dict[num];
}

int main()
{
  int n;
  cout<<"Enter the number: ";
  std::cin>>n;
  unordered_map <int, long long> Dict;
  cout<<fib(n, Dict);
  return 0;
}

如果需要计算n>92的场景，可以自行实现大整数运算逻辑，或者接入第三方大整数计算库。

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