Algoritmo de Ackermann -Explicación del Funcionamiento-
Código de Ackermann
Explicación.
Es una
función recursiva que toma dos números naturales y devuelve un único número
natural.
En 1928,
Wilhelm Ackermann observó que A(x,y,z), la z-ésima exponenciación iterada de x
con y como exponente, es una función
recursiva que no es recursiva primitiva. En 1935, Rózsa Peter simplificó
A(x,y,z) a una función de dos variables. En 1948, Raphael M. Robinson
simplificó la condición inicial. Quedando una función doblemente recursiva de N2 en N, definida recursivamente por las tres
condiciones siguientes:
A[0,n] :
= n+1;
A[m_,0] :
= A[m -1,1] ;
A[m_,n]
:= A [m -1, A[m,n - 1]] ;
Pseudocódigo.
A(m,n) = A(m-1, A(m,n-1)) m > 0 ^ n > 0
A(0,n) = n +1 m
= 0
A(m,0) = A(m-1,1) m
> 0 ^ n = 0
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
INICIO
Akr(m,n)
SI (m == 0)
RETURN
N + 1
/* Caso Contrario */
SI ( n == 0 ^ m > 0)
RETURN
Akr(m – 1, 1 )
/* Caso Contrario */
RETURN Akr(m – 1, Akr(m, 0 – 1)
FIN – SI
FIN – SI
FIN Akr
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
¿Como funcióna el código?
--------------------------------------------------------------------------------------------------------------------
Ejemplo 1: (0,1)
SI (m = =
0)
RETURN N + 1
ü Resultado
de (0,1) = 2
---------------------------------------------------------------------------------------------------------------
Ejemplo 2: (1,0)
Desarrollo
SI ( n = =
0 ^ m > 0)
RETURN Akr(m – 1, 1 )
ü Resultado de (1,0)
= Akr(0,1) = 2
---------------------------------------------------------------------------------------------------------------
Ejemplo 3: (1,1)
Desarrollo
ü Resultado
de (1,1) =
Paso 1°
RETURN
Akr(m – 1, Akr(m, 0 – 1)
= Akr(0, Akr(1,0))
Paso 2°
SI ( n ==
0 ^ m > 0)
RETURN Akr(m – 1, 1 )
= Akr(0,Akr(0,1))
Paso 3°
SI (m ==
0)
RETURN N + 1
= Akr(0, Akr, 2)
Paso
4°
SI
(m == 0)
RETURN N + 1
ü Resultado de (1,1) es: 3
v En
los ejemplos anteriores muestran los posibles casos del Algoritmo de Ackerman.
Comentarios
Publicar un comentario