时间戳

首页 > 解决方案 > 使用 std::map 在 C++ 中递归斐波那契

c++ - 使用 std::map 在 C++ 中递归斐波那契

问题描述

我是 C++ 的新手，试图拿起绳索，我试图编写一个返回第 n 个斐波那契数的递归和记忆斐波那契函数，我想使用 std::map 进行记忆，我还写了一个 python 版本做同样的事情。问题是在数字 94 处，程序的 c++ 版本返回了错误的值，但在那之前它运行良好，有人能指出我正确的方向吗？

#include <iostream>
#include <map>
#define Log(x) std::cout << x << std::endl;

unsigned long long int fib(const int &n)
{
    static std::map<int, unsigned long long int> memo;
    if (n < 3)
        return 1;
    if (memo.count(n) > 0)
        return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(int argc, const char *argv[])
{
    int number;
    std::cout << "Enter a number: ";
    std::cin >> number;
    Log(fib(number));
}

这是运行良好的python版本，

import sys


def fib(n, memo={}):
    if n < 3:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]


sys.setrecursionlimit(10**7)
number = int(input("Enter a number: "))
print(fib(number))

这是输出：

$ ./executables/fib
Enter a number: 93
12200160415121876738
$ python ./fib.py
Enter a number: 93
12200160415121876738
$ ./executables/fib
Enter a number: 94
1293530146158671551
$ python ./fib.py
Enter a number: 94
19740274219868223167

任何帮助将不胜感激

标签： c++recursionmemoization

解决方案

我通过使用 boost 多精度库中的 cpp_int 修复了由于数字太大而无法放入 unsigned long long int（由 tadman 指示的 uint64_t）而导致的问题。

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <map>

using namespace boost::multiprecision;
using namespace std;
cpp_int fib(const int &n)
{
    static map<int, cpp_int> memo;
    if (n < 3)
        return 1;
    if (memo.count(n) > 0)
        return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main()
{
    int number;
    cout << "Enter a number: ";
    cin >> number;
    cout << fib(number) << endl;
}

现在它工作得很好。

$ ./executables/fib
19740274219868223167

感谢评论中的所有帮助！

推荐阅读