El problema de las Torres de Hanoi es curioso porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos.
Resolución de la torre de cuatro discos
(imagen tomada de Wikipedia)
Es un problema que se suele plantear a menudo en ámbitos de programación, especialmente para explicar recursividad y el algoritmo para resolverlo es realmente corto:
hanoi(n, Orig, Aux, Dst)
si (n>0) hacer
hanoi(n-1, Orig, Dst, Aux)
escribir(Mover Orig a Dst)
hanoi(n-1, Aux, Orig, Dst)
A continuación se muestra una implementación Java del algoritmo. El programa se invoca de la siguiente manera:
(donde n es el numero de discos)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Hanoi
{
public static void main (String [] args )
{
int numDiscs = Integer. parseInt(args [0]);
move (numDiscs, "A", "B", "C");
}
protected static void move (int n, String orig, String aux, String dest )
{
if (n >0)
{
move (n -1, orig, dest, aux );
System. out. println("Mover disco de " + orig + " a " + dest );
move (n -1, aux, orig, dest );
}
}
} |
Aquí pueden verse las sucesivas llamadas recursivas a la funciónmove()para el caso de 3 discos:
Read more »
Tags: code, java, logic, recursivity
