谁能告诉我为什么斐波那契函数不起作用？

Question

我想让它每隔一次就给地图添加一个尚未找到的参数，但是当我尝试大于 47 的数字时，它会给我负数，这显然是不可能的

#include <map>
using namespace std;


//memoization
map<unsigned int, unsigned int> memo;
map<unsigned int, unsigned int>::iterator it;
int fibonacci(int n)
{   
    it = memo.find(n);
    if (it != memo.end())
    {
        cout << it->first<<endl;
        return memo.at(n);
    }
    if (n <= 2)
    {
        return 1;
    }
    memo.insert({ n, fibonacci(n - 1) + fibonacci(n - 2) });
    cout << "----"<<n<<endl;
    return memo.at(n);
}
int main()
{
    cout<<fibonacci(48);
}

Answer 1

首先，我们来处理负数。上面的评论解释说您有 32 位 int 溢出。

但是，如果您不将计算出的无符号整数转换为 signed 您从该函数 return 得到的整数，您可以进一步扩展您的代码。

解决方案是使用更大的类型，例如 unsigned long long int，又名 uint64_t

更新

接受的答案中有一些次优的地方。

正如我在评论中指出的那样，代码正在搜索地图两次：it = memo.find(n); 和 memo[n];；应该 return it->second;
映射中的键不需要是 64 位宽； 32 位足以溢出 64 位斐波那契。
由于映射键的顺序并不重要（您只进行插入/查找），unordered_map 的性能会更好（常数时间而不是对数）。
您可能会注意到 memo 是按顺序填充的，并由索引访问。更好的容器是 vector，带有“免费”插入和查找功能。
调用函数不应该填写memo，因为这不关它的事。

这是我的版本：

#include <vector>
#include <iostream>

//memoization
static std::vector<uint64_t> memo = { 0, 0, 1 };
uint64_t fibonacci(unsigned int n) {
  if (n < memo.size())
    return memo[n];

  memo.push_back(fibonacci(n - 1) + fibonacci(n - 2));
  return memo[n];
}
int main() {
  std::cout << fibonacci(32'000);
}

Answer 2

but when I try numbers higher than 47 it gives me negative numbers, clearly impossible

unsigned int 大小为 {0 到 4,294,967,295}，第 48 位斐波那契数为 4,807,526,976

固定码

#include <map>
#include <iostream>
#include <cstdint>
using namespace std;


//memoization
map<int64_t , int64_t> memo;
map<int64_t , int64_t>::iterator it;
int64_t fibonacci(int64_t n) {
    it = memo.find(n);
    if (it != memo.end()) {
        return it->second;;
    }
    memo.insert({n, fibonacci(n - 1) + fibonacci(n - 2)});
    return memo[n];
}
int main() {
    memo.insert({0, 0});
    memo.insert({1, 1});
    memo.insert({2, 1});
    cout << fibonacci(50);
}

谁能告诉我为什么斐波那契函数不起作用？

can anyone tell me why the fibonacci function does not work?

c++

fibonacci