Ir al contenido

Implementación de algoritmos de teoría de números/Función de Ackermann

De Wikilibros, la colección de libros de texto de contenido libre.

La 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. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:


Implementación en distintos lenguajes de programación

[editar]

Código en Java

[editar]
public static int Ackermann(int m, int n)
{
    if (m == 0)
        return (n + 1);
    else if (n == 0)
        return (Ackermann(m - 1, 1));
    else
        return (Ackermann(m - 1, Ackermann(m, n - 1)));
}

Código en C

[editar]
int ackermann(int m, int n)
{
    if (m == 0)
        return n + 1;
    else if (n == 0)
        return ackermann(m - 1, 1);
    else
        return ackermann(m - 1, ackermann(m, n - 1));
}

Código en Lisp

[editar]
(defun ackermann (m n)
  (cond ((= m 0) (1+ n))
        ((= n 0) (ackermann (1- m) 1))
        (t (ackermann (1- m)
                      (ackermann m (1- n))))))

Código en Haskell

[editar]
ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))
Véase también: Haskell

Código en Prolog

[editar]
ackermann(0,N,R):- R is N+1.
ackermann(M,0,R):- M1 is M-1,
                   ackermann(M1,1,R).
ackermann(M,N,R):- M1 is M-1,
	           N1 is N-1,
		   ackermann(M,R1,M1),
		   ackermann(M1,R1,R).

Código en Ada

[editar]
function Ackermann (m, n : Integer) return Integer is
begin
    if m = 0 then
        return n + 1;
    elsif m > 0 and n = 0 then
        return Ackermann (m - 1, 1);
    elsif m > 0 and n > 0 then
        return Ackermann (m - 1, Ackermann (m, n - 1));
    end if;
end Ackermann;

Código en Pascal

[editar]
program funcion_de_ackermann; {compatible hasta el par(4,0)}
uses crt;
procedure leerpar(var m, n : Integer);
begin
    writeln('Ingrese un numero: ');
    readln(m);
    writeln('Ingrese el otro numero: ');
    readln(n);
end;
function ackermann(m, n : Integer) : LongInt;
begin
    if m = 0 then
        ackermann := n + 1
    else if (m > 0) and (n = 0) then
        ackermann := ackermann(m - 1, 1)
    else if (m > 0) and (n > 0) then
        ackermann := ackermann(m - 1, ackermann(m, n - 1));
end;

var m, n : Integer;

begin
    clrscr;
    leerpar(m,n);
    writeln(ackermann(m, n));
    readkey;
end.

Código en Python

[editar]
def ackermann(n, m):
    if n == 0:
        return m + 1
    elif m == 0:
        return ackermann(n - 1,1)
    else:
        return ackermann(n - 1, ackermann(n, m - 1))
Véase también: Python

Código en Ruby

[editar]
def ackermann(m, n)
  return n + 1                                 if m == 0
  return ackermann(m - 1, 1)                   if m > 0 && n == 0
  return ackermann(m - 1, ackermann(m, n - 1)) if m > 0 && n > 0
end