Las Torres de Hanói es un rompecabezas o juego matematico inventado en 1883 por el matematico frances Eduard Lucas. Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.
El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.
Las reglas son:
Sólo se puede mover un disco cada vez.
Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Iterativo
Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:
El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen). La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc. Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino). La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.
El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen). La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc. Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino). La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.
Torres de Hanoi en C
#include
int count = 0;
int moverdisco(int a, int b)
int count = 0;
int moverdisco(int a, int b)
{
cout << a << "->" << b << endl; count++;
cout << a << "->" << b << endl; count++;
}
int movertorre(int n, int desde, int hacia, int piv)
int movertorre(int n, int desde, int hacia, int piv)
{
if(n < 2) moverdisco(desde,hacia);
if(n < 2) moverdisco(desde,hacia);
else {
movertorre(n-1,desde,piv,hacia);
moverdisco(desde,hacia);
movertorre(n-1,piv,hacia,desde);
}
return 0;
}
int main()
{
moverdisco(desde,hacia);
movertorre(n-1,piv,hacia,desde);
}
return 0;
}
int main()
{
int discos = 7;
cout << "Las Torres de Hanoi\n";
cout << "Las Torres de Hanoi\n";
cout << "resolviendo para " << discos << " discos\n\n";
movertorre(discos,1,3,2);
cout << "\nResuelto en " << count << " movimiento(s)\n\n";
return 0;
}
