Función de Ackermann usando programación dinámica

Dados dos enteros M y N distintos de cero , el problema es calcular el resultado de la función de Ackermann en función de algunas ecuaciones particulares.
 

La función de Ackermann se define como:

Ejemplos:

Entrada: M = 2, N = 2
Salida: 7

Entrada: M = 2, N = 7
Salida: 6141004759

1. Mesa vacía – Paso inicial

Relleno usando A ( 0, n ) = n + 1

A ( 1, 0 ) = A ( 0, 1 ) —– (consulte la ecuación (3)) Dado que A ( 0, 1 ) = 2 Por lo tanto, A ( 1, 0 ) = 2 —–(Eq 4)

A ( 1, 1 ) = A ( 0, A ( 1, 0 ) ) —– consulte la ecuación (1) = A ( 0, 2 ) —– consulte la ecuación (4) = 3 —– consulte la ecuación (2) Entonces, A ( 1, 1 ) = 3 —–(Ecuación 5)

A ( 1, 2 ) = A ( 0, A ( 1, 1 ) ) —– consulte la ecuación (1) = A ( 0, 3 ) —– consulte la ecuación (5) = 4 —– consulte la ecuación (2) Entonces, A ( 1, 2 ) = 4 —–(Ecuación 6)

1. Llene la tabla usando ecuaciones y valores almacenados

A ( 2, 0 ) = A ( 1, 1 ) —– consulte la ecuación (3) A ( 1, 1 ) = 3 Entonces, A ( 2, 0 ) = 3 —– (Ec. 7)

A ( 2, 1 ) = A ( 1, A ( 2, 0 ) ) —– consulte la ecuación (1) A ( 2, 0 ) = 3 A ( 2, 1 ) = A ( 1, 3 ) Entonces, para calcular esto valor, nuevamente use la ecuación (1) A ( 1, 3 ) = A ( 0, A ( 1, 2 ) ) A ( 1, 2 ) = 4 A ( 1, 3 ) = A ( 0, 4 ) —– consulte ecuación(2) = 5 Por lo tanto A ( 2, 1 ) = A ( 1, 3 ) = 5 — (Eq 7)

A ( 2, 2 ) = A ( 1, A ( 2, 1 ) ) —– consulte la ecuación (1) A ( 2, 1 ) = 5 A ( 2, 2 ) = A ( 1, 5 )

UNA ( 1, 5 ) = UNA ( 0, UNA ( 1, 4 ) ) UNA ( 1, 4 ) = UNA( 0, UNA ( 1, 3 ) ) UNA ( 1, 3 ) = UNA ( 0, UNA ( 1 , 2 ) ) A ( 1, 2 ) = 4 Volviendo de la función obtenemos, A ( 1, 3 ) = A ( 0, 4 ) = 5 —– consulte la ecuación (2) A ( 1, 4 ) = A ( 0, A (1, 3 ) ) = A ( 0, 5 ) = 6 —–Ya que A ( 1, 3 ) = 5 A ( 1, 5 ) = A ( 0, A ( 1, 4 ) ) = A ( 0, 6 ) = 7 Entonces, A ( 2, 2 ) = 7 ——- (Ecuación 9)

1. Tabla final con resultado de cada subproblema

A continuación se muestra la implementación del enfoque anterior: 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// Bottom Up Approach
long long int Ackermann(int m, int n){
 
    // creating 2D LIST
    vector<vector<long long int>> cache(m + 1, vector<long long int>(n + 1, 0));
 
    for (int rows = 0 ; rows < m + 1 ; rows++){
        for (int cols = 0 ; cols < n + 1 ; cols++){
 
            // base case A ( 0, n ) = n + 1
            if (rows == 0){
                cache[rows][cols] = cols + 1;
            }
 
            // base case A ( m, 0 ) =
            // A ( m-1, 1) [Computed already]
            else if (cols == 0)
            {
                cache[rows][cols] = cache[rows-1][1];
            }
            else
            {
 
                // if rows and cols > 0
                // then applying A ( m, n ) =
                // A ( m-1, A ( m, n-1 ) )
                long long int r = rows - 1;
                long long int c = cache[rows][cols-1];
                long long int ans;
                 
                // applying equation (2)
                // here A ( 0, n ) = n + 1
                if (r == 0){
                    ans = c + 1;
                }else if (c <= n){
                    // using stored value in cache
                    ans = cache[rows-1][cache[rows][cols-1]];
                }else{
                    // Using the Derived Formula
                    // to compute mystery values in O(1) time
                    ans = (c-n)*(r) + cache[r][n];
                }
 
                cache[rows][cols] = ans;
            }
        }
    }
    return cache[m][n];
}
 
 
// Driver code
int main()
{
 
    // very small values
    int m = 2;   
    int n = 2;
 
    // a bit higher value
    int m1 = 5;   
    int n1 = 7;
 
 
    cout << "Ackermann value for m = " << m <<
      " and n = " << n << " is -> " <<
      Ackermann(m, n) << endl;
 
    cout << "Ackermann value for m = " <<
      m1 << " and n = " << n1 << " is -> " <<
      Ackermann(m1, n1) << endl;
     
    return 0;
}
 
// This code is contributed by subhamgoyal2014.

# Python code for the above approach
 
# Bottom Up Approach
 
 
def Ackermann(m, n):
 
    # creating 2D LIST
    cache = [[0 for i in range(n + 1)] for j in range(m + 1)]
    for rows in range(m + 1):
        for cols in range(n + 1):
            # base case A ( 0, n ) = n + 1
            if rows == 0:
                cache[rows][cols] = cols + 1
            # base case  A ( m, 0 ) =
            # A ( m-1, 1) [Computed already]
            elif cols == 0:
                cache[rows][cols] = cache[rows-1][1]
            else:
                # if rows and cols > 0
                # then applying A ( m, n ) =
                # A ( m-1, A ( m, n-1 ) )
                r = rows - 1
                c = cache[rows][cols-1]
                # applying equation (2)
                # here A ( 0, n ) = n + 1
                if r == 0:
                    ans = c + 1
                elif c <= n:
                    # using stored value in cache
                    ans = cache[rows-1][cache[rows][cols-1]]
                else:
                    # Using the Derived Formula
                    # to compute mystery values in O(1) time
                    ans = (c-n)*(r) + cache[r][n]
 
                cache[rows][cols] = ans
 
    return cache[m][n]
 
 
# very small values
m = 2
n = 2
 
# a bit higher value
m1 = 5
n1 = 7
 
 
print("Ackermann value for m = ", m,
      " and n = ", n, "is -> ",
      Ackermann(m, n))
 
print("Ackermann value for m = ", m1,
      " and n = ", n1, "is -> ",
      Ackermann(m1, n1))

Complejidad de tiempo: O( M * N ) Complejidad de espacio auxiliar: O( M * N )