std::pair 地图中的 C++ 计数函数

Question

我正在尝试编写一个函数，该函数具有一个无符号整数作为输出，两个无符号整数作为输入。现在由于这个函数已经被递归定义，我试图使用 std::map 来实现记忆以提高时间效率。

代码：

unsigned memo_ack(unsigned m,unsigned n)

{

    static map <pair<int,int>,unsigned> mem;
    unsigned ans;
    if(m==0)
        return n+1;
    else if(n==0)
        if(mem.count(ackpair<m,n>)>0)


}

在这里，我想使用计数函数来查看输入为 (m,n) 的特定值是否存在。

例如，如果计数函数returns > 0，那么，该函数将return该函数的存储值，该值之前已经计算过，因此没有需要重新计算。如果计数函数 return 为零，则原始函数使用函数定义计算与该对对应的值。

问题在于：count 函数不接受 std::pair 作为参数，也不接受两个输入参数。我还如何告诉计数函数计算特定输入对的出现次数，如果它已经存在，return 一个正数（在这种情况下为 1）？

传递 std::pair 时，出现以下错误：二进制表达式的操作数无效（'pair' 和 'unsigned int'）

原始的非记忆递归解决方案是：

#include<iostream>

using namespace std;

int myAckermann(int m, int n)

{

    if(m==0)
        return n+1;
    else if (n==0)
        return myAckermann(m-1,1);
    else
        return myAckermann(m-1,myAckermann(m,n-1));
}

int main()

{

    int m,n;
    cin>>m>>n;
    long long ans;
    ans = myAckermann(m,n);
    cout<<ans;
    return 0;
}

Answer 1

您可以使用 find 从您的所有输入参数和 return 您找到的值中搜索关键构建。如果 map/mem 中没有您计算的值，则将其存储在地图中以备后用 return。

#include <map>

unsigned int memo_ack(unsigned int m, unsigned int n)
{
    static std::map <std::pair<unsigned int, unsigned int>, unsigned int> mem;
    unsigned ans = 0;
    if (m == 0) {
        return n+1;
    } else if (n == 0) {
        auto found = mem.find({ m, n }); // look-up whether we already provided an answer for these paramaters
        if (found != mem.end()) {
            ans = found->second;         // already know the answer
        } else {
            ans = 42;                    // Find the answer
            mem[{ m, n }] = ans;         // and keep it for later
        }
    }
    return ans;
}

您仍然可以使用 std::map::count() 如：

    int c = mem.count(std::make_pair(m, n));

但您并不真正需要计数，无论如何您都必须搜索该值。

您还可以考虑 std::unordered_map，它的复杂度几乎不变。

这里是 c++03 版本：

#include <map>

unsigned int memo_ack(unsigned int m, unsigned int n)
{
    static std::map <std::pair<unsigned int, unsigned int>, unsigned int> mem;
    unsigned ans = 0;
    if (m == 0) {
        return n+1;
    } else if (n == 0) {
        std::map<std::pair<unsigned int, unsigned int>, unsigned int>::const_iterator found = mem.find(std::make_pair(m, n));
        if (found != mem.end()) {
            ans = found->second;
        } else {
            ans = 42;
            mem[std::make_pair(m, n)] = ans;
        }
    }
    return ans;
}

std::pair 地图中的 C++ 计数函数

C++ count function in maps with std::pair

c++

stdmap

std-pair