elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a Git (Primera Parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ackermann - Programacion Dinámica
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ackermann - Programacion Dinámica  (Leído 3,207 veces)
GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Ackermann - Programacion Dinámica
« en: 11 Febrero 2017, 20:31 pm »

Hola a todos!

Código
  1. int ackerman_or(int m, int n)
  2. {
  3.        if(m==0)
  4.                return n+1;
  5.  
  6.        else
  7.        {
  8.                if(n==0)
  9.                        return ackerman_or(m-1, 1);
  10.                else
  11.                        return ackerman_or(m-1, ackerman_or(m, n-1));
  12.        }
  13. }
  14.  


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.


En línea

LET'S DO STUFF!!
ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Ackermann - Programacion Dinámica
« Respuesta #1 en: 11 Febrero 2017, 22:00 pm »

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.


En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: Ackermann - Programacion Dinámica
« Respuesta #2 en: 11 Febrero 2017, 23:48 pm »

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))
« Última modificación: 12 Febrero 2017, 01:20 am por GGZ » En línea

LET'S DO STUFF!!
ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Ackermann - Programacion Dinámica
« Respuesta #3 en: 12 Febrero 2017, 00:24 am »

¿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.
En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: Ackermann - Programacion Dinámica
« Respuesta #4 en: 12 Febrero 2017, 14:35 pm »

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


Código
  1. #include <stdio.h>
  2.  
  3. int table[1000][1000];
  4.  
  5.  
  6. void tstart(int m, int n){
  7.  
  8.        int i,j;
  9.        for (j=0; j<n; j++)
  10.                for (i=0; i<m; i++)
  11.                        table[i][j] = -1;
  12. }
  13.  
  14.  
  15. int Ack (int m, int n){
  16.  
  17.        if (m == 0)
  18.                return n+1;
  19.        if (n == 0)
  20.                return Ack(m-1,1);
  21.        return Ack(m-1,Ack(m,n-1));
  22. }
  23.  
  24. int Ack_td (int m, int n){
  25.  
  26.        if (m == 0)
  27.                return n+1;
  28.  
  29.        if (n == 0)
  30.                return Ack(m-1,1);
  31.  
  32.        if (table[m][n-1] == -1)
  33.                table[m][n-1] = Ack(m,n-1);
  34.  
  35.        if (table[m][n] == -1)
  36.                table[m][n] = Ack(m-1,table[m][n-1]);
  37.  
  38.  
  39.  
  40.        return table[m][n];
  41.  
  42. }
  43.  
  44. int main (void){
  45.  
  46.        tstart(1000,1000);
  47.        printf ("Resultado: %d\n",Ack(5,0));
  48.        printf ("Resultado: %d\n",Ack_td(5,0));
  49.  
  50.  
  51.        return 0;
  52. }
  53.  

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:
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.
« Última modificación: 12 Febrero 2017, 15:03 pm por GGZ » En línea

LET'S DO STUFF!!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
1 muestra del poder de la programacion dinamica « 1 2 3 »
.NET (C#, VB.NET, ASP)
spiritdead 23 13,180 Último mensaje 19 Enero 2015, 23:01 pm
por Eleкtro
Programación Dinámica
Java
erikcdlm 0 1,889 Último mensaje 7 Noviembre 2014, 20:32 pm
por erikcdlm
Problema Programación Dinamica
Programación C/C++
maxisolis 3 2,550 Último mensaje 29 Junio 2015, 02:19 am
por maxisolis
problema de backtracking y programacion dinamica
Programación C/C++
aprendiz de programador 6 6,815 Último mensaje 12 Diciembre 2015, 16:08 pm
por SnzCeb
[Estrategias] Programación Dinámica vs Divide y conquistarás (DUDA)
Programación C/C++
GGZ 4 5,539 Último mensaje 7 Noviembre 2016, 08:20 am
por GGZ
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines