0

我有以下代码计算给定 n 和 k 的第二类斯特林数，

#include <cstdint>
#include <map>

#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;


mp::cpp_int stirlingS2(unsigned n, unsigned k)
{
    if (n == 0 && k == 0) {
        return 1;
    }

    if (n == 0 || k == 0) {
        return 0;
    }

    static auto memo = std::map<std::pair<unsigned, unsigned>, mp::cpp_int>();
    auto nKPair = std::pair<unsigned, unsigned>(n, k);

    if (memo.count(nKPair) > 0) {
        return memo[nKPair];
    }

    auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1);

    memo[nKPair] = val;

    return val;
}

不幸的是，当这段代码运行时，它会出现段错误。对于插入的前 87795 个值，它似乎运行良好memo，但此后不久就崩溃了。具体来说，段错误发生在map::count, 行中if (memo.count(nKPair) > 0) {。我认为这可能是memo尺寸不足的问题，所以我在分配给的任务中添加了以下警告memo，

if (memo.size() < memo.max_size()) {
    memo[nKPair] = val;
}

但这没有帮助。我还注意到 87795 值并不表示何时崩溃。通过一些小的修改，将第一个 if 语句更改为，

if (n <= k) {
    return 1;
}

将该值更改为 66453。

有谁知道这里发生了什么？

4

1 回答 1

1

好的，经过数小时的困惑，我将其范围缩小到表达式模板问题。我真的不完全明白为什么，但这一切都与那一点点auto有关

auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1)

基本上，将其更改auto为mp::cpp_int突然之间，没有段错误。

于 2016-08-09T04:51:37.477 回答