 Autor
|
Tema: Ackermann - Programacion Dinámica (Leído 3,148 veces)
|
GGZ
 Desconectado
Mensajes: 144
|
Hola a todos! 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.
|
|
|
|
|
En línea
|
LET'S DO STUFF!!
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
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_valoresCuando 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
Mensajes: 144
|
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
Mensajes: 3.412
ASMático
|
¿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
Mensajes: 144
|
Primero que todo hay dos, bottom-up y top-down, intenté hacer algo como esto: #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 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!!
|
|
|
|
| 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,082
|
19 Enero 2015, 23:01 pm
por Eleкtro
|
|
|
|
Programación Dinámica
Java
|
erikcdlm
|
0
|
1,870
|
7 Noviembre 2014, 20:32 pm
por erikcdlm
|
|
|
|
Problema Programación Dinamica
Programación C/C++
|
maxisolis
|
3
|
2,499
|
29 Junio 2015, 02:19 am
por maxisolis
|
|
|
|
problema de backtracking y programacion dinamica
Programación C/C++
|
aprendiz de programador
|
6
|
6,419
|
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,162
|
7 Noviembre 2016, 08:20 am
por GGZ
|
 |
