Мемоизация с помощью функции Аккермана C++

Question

Хорошо, это для домашнего задания, поэтому, пожалуйста, просто попробуйте направить меня, не давая мне прямой ответ. Я пытаюсь установить запоминание с помощью функции Аккермана (C++). Он не делает то, что я ожидал, достигнув Аккермана (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;
}

Итак, ниже мой новый подход. Но я не могу понять, почему я не могу использовать memoMap.insert(make_pair(m, n), (acker(m - 1, 1))); изнутри моего acker функция??

#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;
}

Answer 1

Запоминание функции требует запоминания, если весь кортеж аргумента был замечен ранее. Использование массива, индексированного одним целым числом, не решит эту проблему: есть два аргумента! Вы можете использовать двумерный массив, одно измерение для m и другое для n. Это практично для функций, которые имеют только небольшие аргументы. Поэтому массив 2d может быть небольшим и по-прежнему охватывать интересные случаи. Вы можете прочитать и поэкспериментировать, чтобы определить, соответствует ли Аккерман этому критерию. В целом, однако, вы захотите использовать карту из (m, n) пар в результаты. Карты C++ - это отличная структура данных для изучения, поэтому я предлагаю вам попробовать их здесь. Я не буду предоставлять код, если вы не озадачены. Гораздо лучше научиться понимать, как использовать библиотеки из документации и доступных примеров, чем получать код, который решает вашу проблему.

Answer 2

map.insert() будет принимать пару. Пара должна быть парой из целых чисел (для m,n) и целого числа (для значения функции Ack).

Таким образом, это будет выглядеть следующим образом:

auto key = make_pair(m, n);
auto value = acker(m-1, 1);
memoMap.insert(make_pair(key, value));

Если вы используете C++03 или более старый стандарт, auto может не работать. Они должны быть:

pair<int, int> key = make_pair(m, n);
int  value = acker(m-1, 1);

Я думаю, что вы в пути. Мне интересно, почему вы не просматриваете memoMap, прежде чем рассчитывать нетривиальные случаи. Например, acker(m-1, n) может быть рассчитан несколько раз. Кроме того, когда mn!= 0, кодовый блок, кажется, не имеет записи в таблице и / или поиска.