Vamos a programar #59 - La función de Ackerman (ver. C)

Hola de nuevo a todos, el día de hoy; y después de casi un mes de "vacaciones"; vamos a continuar con un poco de programación.
Hace algunos días mientras hablaba con un amigo, me dijo que en la universidad, le habían dejado cómo tarea hacer un programa en C que probara la función de Ackerman.

Pero primero veamos una pequeña definicion sobre lo que es la función de Ackerman:
En teoría de la computación, función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann, tiene un crecimiento extremadamente rápido, de interés para la ciencia computacional teórica y la teoría de la computabilidad. Hoy en día, hay una serie de funciones que son llamadas funciones Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Wikipedia/FuncionDeAckerman
Y sigue las siguientes reglas:

  •  n+1 Si m = 0.
  • A(m-1, 1) si m > 0 y n = 0.
  • A(m - 1, A(m, n - 1)) si m > y n > 0.
Cómo podrás ver, se trata de una función que es recursiva, es decir, ella misma se manda a llamar dentro de la misma función.

Sabiendo lo anterior, podemos crear un programa en C usando el siguiente código:


# include <stdio.h>
int AckermanFunction(int m, int n)
{
	if (m == 0)
		return (n+1);
	else
		if (n == 0)
			return (AckermanFunction(m - 1, 1));
		return(AckermanFunction(m - 1, AckermanFunction(m, n - 1)));
}
int main()
{
	int i,j;
	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 3; j++)
		{
			printf("%6d", AckermanFunction(i, j));
		}
		printf("\n");
	}
	return 0;
}

El código anterior consta de dos partes, la primera es la función llamada "AckermanFunction" que recibe dos parámetros del tipo "int". La función sigue las reglas de la función de Ackerman por lo que si al evaluar, el parámetro "m", este vale cero, la función regresará el valor de "n" mas uno, si no es el caso, la comprobación se hará para el valor de "n = 0", si es el caso, la función se mandará a llamar a si misma y se pasará cómo argumentos a "m" con valor de "m - 1" y "n" con el valor de "n = 1" y regresará el resultado de llamarse a si misma. Finalmente, si "m" y "n" son valores mayores a cero "m > 0", "n > 0", el valor que la función regresará, será el resultante de llamarse a si misma con los parámetros "m-1"  para "m" y el resultado de llamarse a si misma con los parámetros "m = m - 1" y "n = n - 1" para "n".
Para poder ver los resultados, puedes copiar el código y usarlo en un compilador de c en linea. y debería de salir un resultado similar al anterior. Puedes modificar el código para ver que pasa "mas allá" de la quinta fila, pero el resultado puede tomar mucho tiempo.

Y bien, por ahora es todo.

Los leo luego.

No hay comentarios.