Soporte y Tecnología > C/C++

Funcion de Ackermann

(1/1)

MepL:
Hola.

Me dejaron de tarea de  realizar un programa en c++ recursivo de la funcion de Ackermann y ya encontre unos programitas, pero no entiendo como diablos trabaja esa funcion :-/, alguien que me saque de mi ignorancia por favor. :unsure:

mxgxw:
Bueno, no te voy a poner el codigo, porque ya he dicho antes que no hago tareas si no hay dinero de por medio fsakjhfskjfdsa  :evil:

Pero creo que un articulo mejor explicado que el de la wikipedia no vas a encontrar:

http://es.wikipedia.org/wiki/Función_de_Ackermann

Ahora te lo voy a tratar de explicar de manera entendible. La definición de la función de Ackerman es la siguiente:



Que significa esto? Bueno primero.

Vos tenes una funcion, una funcion "A" que recibe dos parametros m y n, La parte derecha del corchete te indica que vas a hacer con esos dos valores, y bajo que condiciones. Podemos hacer un algoritmo mas o menos así:


--- Código: ---// Sintaxis Ackermann(1,1);
funcion Ackermann ( m es entero, n es entero) {

// Evaluamos la primera condicion:

Si m = 0 entonces {
  devolver n+1;
}
Si m > 0 y n = 0 entonces {
  devolver Ackermann( m-1 , 1)
}

Si m > 0 y n > 0 entonces {
 devolver Ackermann( m-1 , Ackermann( m , n - 1));
}
}

--- Fin del código ---

La mejor forma de ver funcionar el algoritmo es agarrar lapiz y papel y probarlos, para este caso lo vamos a probar con la formula.

Primer ejemplo: "A(1,1)".

m = 1
n = 1

Se cumple m = 0? No.
Se cumple m > 0 y n = 0? No
Se cumple m > 0 y n > 0? Si

Como se cumple la tercera, entonces tenemos que llamar:

A(m-1,A(m,n-1));

m-1 = 0
m = 1
n-1 = 0

Con lo que la funcion nos queda:

A(0,A(1,0))

Aqui hay un problema, para poder evaluar la funcion de afuera, primero necesitamos el valor de la funcion de adentro, asi que evaluamos la funcion de adentro:

A(1,0)

m = 1
n = 0

Se cumple m = 0? No.
Se cumple m > 0 y n = 0? Si
Se cumple m > 0 y n > 0? No

Como se cumple la segunda, entonces llamamos a la funcion A(m-1,1)

m-1 = 0
n = 1

A(0,1)

m = 0
n = 1

Se cumple m = 0? Si
Se cumple m > 0 y n = 0? No
Se cumple m > 0 y n > 0? No

Devolvemos 1+1;

A(0,1) vale entonces 2

A(1,0) vale entonces 2

A(0,A(1,0)) se convierte en A(0,2)

Devolvemos 2+1;

A(0,2) vale entonces 3


En resumen:

--- Código: ---A(1,1)
A(0,A(1,0))
A(0,A(0,1))
A(0,2)
3

--- Fin del código ---


No te recomiendo probar el algoritmo con numeros mas grandes porque no vas a terminar. Con el Pseudo-codigo que te puse arriba bien podes implementar el algoritmo en cualquier lenguaje, espero haberte ayudado!

MepL:
1000 gracias brother, se ve que te tomaste tu tiempo, se ve mero fumada pero creo que el programita que me baje funciona por lo que me explicas alli arriba.

Gracias por la explicacion.  :thumbsup:

Navegación

[0] Índice de Mensajes