Función de conteo de C++ en mapas con std::pair

Función de conteo de C++ en mapas con std::pair

Estoy tratando de codificar una función que tiene un int sin firmar como salida y dos int sin firmar como entradas. Ahora que esta función se ha definido de forma recursiva, estaba tratando de implementar la memorización usando std::map para aumentar la eficiencia del tiempo.

código:

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)


}

Aquí, deseo usar la función de conteo para ver si un valor particular con entradas (m,n) está presente o no.

Por ejemplo, si la función de conteo devuelve> 0, la función solo devolverá el valor almacenado de la función, que se calculó previamente, por lo que no es necesario volver a calcular. Si la función de conteo devuelve cero, la función original calcula el valor correspondiente a ese par usando la definición de la función.

Aquí está el problema: la función de conteo no aceptará std::pair como argumento, ni aceptará dos argumentos de entrada. ¿De qué otra manera le digo a la función de conteo que cuente el número de ocurrencias de un par de entrada en particular y, si ya existe, devuelva un número positivo (1, en este caso)?

Al pasar un std::pair, aparece el siguiente error: Operandos no válidos para la expresión binaria ('par' y 'int sin firmar')

La solución recursiva original no memorizada fue:

#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;
}
Mostrar la mejor respuesta

¿Podría explicar qué está haciendo la función?

¿Puedes mostrar tu código actual en el que intentas pasar un std::pair? Debería aceptar un par.

Intente escribirlo sin memorización primero. Una vez que tenga ese trabajo, no debería ser demasiado difícil agregar la memorización.

@Kevin, ya lo hice, funciona bien.

ackpair<m,n> no es una sintaxis C++ válida.

@BhargavVarshney ¿Puede editar su pregunta para incluir ese código? Lo que tienes ahora no funciona, incluso si ignoramos que la memorización está incompleta

Dados m y n como entradas, calcula A(m,n) que se define como: A(m,n) da n+1, si m = 0, da A(m-1,1), si n = 0 , da A(m-1,A(m,n-1)), de lo contrario

No entiendo por qué tienes una variable de par global aleatoria 'ackpair'. ¿Se supone que esto es un typedef o algo así?

Puede buscar en el mapa usando find para obtener una compilación clave de todos sus parámetros de entrada y devolver el valor que encontró. Si no hay ningún valor en el mapa/memoria, lo calcula, guárdelo en el mapa para más tarde y devuélvalo.

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

Aún puedes usar std::map::count() como:

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

pero realmente no necesita el conteo y tendrá que buscar el valor de todos modos.

También podría considerar std::unordered_map que tiene complejidad casi constante.


Aquí hay versión:

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

¿Por qué asumir C++ 11?

@user202729: Hasta que se especifique, podríamos suponer una versión "reciente", ya hay 2 versiones desde C++11.

(¿quiso decir "no c++11" o "c++03-solo"?)

@ usuario202729 cierto. Simplemente terminó de esta manera después de algunas ediciones. Gracias