Torres de hanoi

18 de octubre de 2010

Las Torres de Hanoi
Introduccion
Edouard Lucas tuvo inspiración de una leyenda para construir el juego de las Torres de Hanói. Ya su nombre fue inspirado en la torre símbolo de la ciudad de Hanoi, en el Vietnam.
Existen varias leyendas acerca del origen del juego, de más conocida dice respeto a un templo Hndu, situado en el centro del universo. Se dice que Brahamasupuestamente había creado una torre con 64 discos de oro y dos más estacas equilibradas sobre una plataforma. Brahma les hube ordenado que movieran todos los discos de una estaca para otra según sus instrucciones. Las reglas eran simples: sólo un disco podría ser movido por vez y nunca un disco mayor debería quedar por cima de un disco más pequeño. Según la leyenda, cuando todos los discos fuerantransferidos de una estaca para la otra, el templo desmoronar-se-iba y el mundo desaparecería.
Las Torres de Hanoi es un juego matemático que 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 una varilla ascendentemente, y no se puede colocar ningún disco mayor sobreuno menor a él en ningún momento. El juego consiste en pasar todos los discos a otra varilla colocados de mayor a menor ascendentemente. Para poder resolverlo hace falta un algoritmo.
Un algoritmo es una descripción detallada y precisa de como resolver un problema que consiste en una secuencia finita de instrucciones, se producen datos de entrada y salida.

Justificación
Este tema nos pareciómuy interesante ya que el juego de las torres de Hanoi es muy complicado y el uso de las matemáticas y el razonamiento es fundamental para lograrlo.
Es necesario analizar el problema del juego para poder llegar a una posible solución, eso es lo que hace entretenido al juego.
Es un juego de muchos retos y creemos que eso hace que se busquen varias soluciones para jugarlo. Nosotros lo vamos aplantear a través de una metodología de solución de problemas

Definición del problema:
Tenemos tres torres A, B y C. Al principio, una de las torres por lo general la torre A, tiene apilados n anillos, digamos n=3 anillos, de distintos diámetros colocados de mayor a menor en forma ascendente. El objetivo del problema es producir como salida los movimientos necesarios para mover todos losanillos a otra torre uno por uno. Cada movimiento debe efectuarse de la siguiente forma: tomar el anillo que se encuentra hasta arriba de la torre X y colocarlos arriba de la torre Y, donde X y Y pueden tomar cualquiera de los valores A,B o C. Este movimiento puede ejecutarse siempre y cuando el anillo que se coloque en la torre Y no descanse sobre un anillo de menor diámetro.
Análisis de la solución:Se tiene que diseñar un algoritmo que resuelve el problema, es conveniente colocar las torres en círculo, si las colocaramos en línea estableceríamos una diferencia entre las torres: una sería la primera y la otra la última. En círculo todas son iguales y las podemos recorrer en el orden de las manesillas del reloj.
Diseño de la solución:
El problema de las Torres de Hanoi es curioso porque susolución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. 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 dospilas 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,...