好的,这是家庭作业,所以请尝试直接指导我,不要给我直接的答案。
我正在尝试使用 Ackermann 函数 (C++) 进行内存。当到达 Ackermann(1,2) 时,它没有达到我的预期。有些东西告诉我,我也许应该尝试建立一个 map
而不是 array
来进行内存?感谢任何输入。
#include <iostream>
using namespace std;
static int ackerMemoization[1000];
int acker(int m, int n)
{
if (m == 0)
return n + 1;
if (n == 0)
return acker(m - 1, 1);
if (ackerMemoization[m] != 0)
return ackerMemoization[m - 1];
else
{
ackerMemoization[m] = acker(m - 1, acker(m, n - 1));
return ackerMemoization[m];
//return acker(m - 1, acker(m, n - 1));
}
}
int main()
{
for (int i = 0; i < 1000; i++)
{
ackerMemoization[i] = 0;
}
//cout << "Ackermann(3, 20) = " << acker(3, 20) << endl;
//cout << "Ackermann(4, 0) = " << acker(4, 0) << endl;
//cout << "Ackermann(4, 1) = " << acker(4, 1) << endl;
for (int m = 0; m <= 4; ++m)
{
for (int n = 0; n < 20; ++n)
{
cout << "Ackermann(" << m << ", " << n << ") = " << acker(m, n) << "\n";
}
}
cin.get();
return 0;
}
下面是我的新方法。但我不明白为什么我不能在我的 acker 中使用
函数??memoMap.insert(make_pair(m, n), (acker(m - 1, 1)));
#include <iostream>
#include <map>
using namespace std;
static map<pair<int, int>, int> memoMap;
int acker(int m, int n)
{
if (m == 0)
return n + 1;
if (n == 0)
{
//memoMap.emplace[make_pair(m, n), (acker(m - 1, 1)];
memoMap.insert(make_pair(m, n), (acker(m - 1, 1)));
return acker(m - 1, 1);
}
else
{
return acker(m - 1, acker(m, n - 1));
}
}
int main()
{
//static map<pair<int, int>, int> memoMap;
//cout << "Ackermann(3, 20) = " << acker(3, 20) << endl;
//cout << "Ackermann(4, 0) = " << acker(4, 0) << endl;
//cout << "Ackermann(4, 1) = " << acker(4, 1) << endl;
for (int n = 0; n <= 20; ++n)
{
cout << "Ackermann(" << 0 << ", " << n << ") = " << acker(0, n) << endl;
}
cout << endl;
for (int n = 1; n <= 20; ++n)
{
cout << "Ackermann(" << 1 << ", " << n << ") = " << acker(1, n) << endl;
}
cout << endl;
for (int n = 2; n <= 20; ++n)
{
cout << "Ackermann(" << 2 << ", " << n << ") = " << acker(2, n) << endl;
}
cout << endl;
for (int n = 3; n <= 20; ++n)
{
cout << "Ackermann(" << 3 << ", " << n << ") = " << acker(3, n) << endl;
}
cout << endl;
for (int n = 4; n <= 2; ++n)
{
cout << "Ackermann(" << 4 << ", " << n << ") = " << acker(4, n) << endl;
}
cin.get();
return 0;
}
最佳答案
函数的记忆化需要记住整个参数元组是否曾被见过。使用由单个整数索引的数组不会解决这个问题:有两个参数!您可以使用二维数组,一维代表 m,另一维代表 n。这对于只有小参数的函数是实用的。因此,二维数组可能很小,但仍能覆盖感兴趣的案例。你可以做一些阅读和实验来确定阿克曼是否符合这个标准。不过,一般来说,您会希望使用从 (m,n) 对到结果的映射。 C++ 映射是一个很好的学习数据结构,所以我建议你在这里尝试一下。除非你被难住了,否则我不会提供代码。从文档和可用示例中学习如何弄清楚如何使用库,远比获得解决问题的代码要好得多。
关于c++ - 使用 Ackermann 函数 C++ 进行内存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48736210/