Ackermann - Programacion Dinámica

[GGZ]

Hola a todos!

Código (c) [Seleccionar] Expandir

int ackerman_or(int m, int n)
{
       if(m==0)
               return n+1;

       else
       {
               if(n==0)
                       return ackerman_or(m-1, 1);
               else
                       return ackerman_or(m-1, ackerman_or(m, n-1));
       }
}



Intenté hacer una versión utilizando programación dinámica, ya que en esta versión se recalculan demasiadas cosas pero no tuve éxito.

¿Alguien que me podría dar una calavera de como hacerlo?

Saludos.

[ivancea96]

Podrías construir una matriz bidimensional M\N e irla rellenando. Y cuando calcules un valor más grande, la haces más grande.

Sin embargo, esta función da resultados muy grandes muy temprano cuando aumenta M, así que...

Una posibilidad sería utilizar estas formulas: https://es.wikipedia.org/wiki/Funci%C3%B3n_de_Ackermann#Tabla_de_valores
Cuando M esté en el rango [0,3], puedes retornar directamente las fórmulas que aparecen (n+1, n+2, 2n+3, 8*(2^n) - 3).

Si realmente lo quieres hacer con memroia dinámica, almacenando valores intuyo, entonces es solo tener una matriz. Si al llamar a la función, la matriz tiene esa posicion ya calculada, la retornas sin más. Sino, la calculas recursivamente tal como lo tienes, la guardas, y la retornas.
En caso de que se pidan valores de M o N fuera dle rango de la matriz, habrá que incrementar su tamaño generando otra matriz y copiando los valores antiguos.
Para posiciones de la matriz que aun no han sido calculadas, puedes guardar un 0, por ejemplo, que es un valor que no existe en esta función que yo sepa.

[GGZ]

Intenté hacer TOP-DOWN como bien mencionas, pero no es tan sencillo como otros casos parecidos a fibonacci o la factorial porque a diferencia de esos esta llama a una función y el argumento es otra llamada a una función, ¿me explico?

factorial.0 = 1
factorial.n = n*factorial(n-1)

fib.0 = 0
fib.1 = 1
fib.n = fib.(n-1) + fib.(n-2)

Pero esta es así:




Lo que me jode es el: A(m-1,A(m,n-1))

[ivancea96]

¿Qué problema tienes con que el argumento sea una llamada a función?
Es lo mismo hacer fib(a) + fib(b) que hacer ack(a, arck(b,c)). En ambos casos, primero calculas uno, y luego el otro.

[GGZ]

Primero que todo hay dos, bottom-up y top-down, intenté hacer algo como esto:

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int table[1000][1000];


void tstart(int m, int n){

       int i,j;
       for (j=0; j<n; j++)
               for (i=0; i<m; i++)
                       table[i][j] = -1;
}


int Ack (int m, int n){

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

int Ack_td (int m, int n){

       if (m == 0)
               return n+1;

       if (n == 0)
               return Ack(m-1,1);

       if (table[m][n-1] == -1)
               table[m][n-1] = Ack(m,n-1);

       if (table[m][n] == -1)
               table[m][n] = Ack(m-1,table[m][n-1]);



       return table[m][n];

}

int main (void){

       tstart(1000,1000);
       printf ("Resultado: %d\n",Ack(5,0));
       printf ("Resultado: %d\n",Ack_td(5,0));


       return 0;
}


Ese sería el TOP-DOWN y ahora el ¿bottom up? lo intenté y no me salió

Probé con varios casos parece funcionar pero no sé si está bien optimizado ahora voy a compararlos con el comando time.

Pero no está funcionando bien al parecer

Código [Seleccionar] Expandir

sickcunt@skynet:~$ time ./Ack
Resultado: 65533

real 0m21.944s
user 0m21.924s
sys 0m0.008s
sickcunt@skynet:~$ vi Ack.c
sickcunt@skynet:~$ gcc Ack.c -o Ack
sickcunt@skynet:~$ time ./Ack
Resultado: 65533

real 0m22.105s
user 0m22.084s
sys 0m0.008s
sickcunt@skynet:~$


Me acabo de dar cuenta que cometí varios errores puse mal el nombre de la función, estoy intentando repararlo.