torre de hanoi

JUEGO DE LAS TORRES DE HANOI Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Édouard Lucas.[1] Este juego de mesa solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo ciertas reglas. Elproblema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.


El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Losdiscos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tressimples reglas:

1. Sólo se puede mover un disco cada vez.

2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.

3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.


SOLUCION ITERATIVA

Otra manera de resolver el problema, sinutilizar 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 dediscos 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úmeropar 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.

Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y losimpares de otro, y se resuelve el problema añadiendo la siguiente regla: no colocar juntos dos discos de un mismo color. De esta manera, solo queda un movimiento posible (además del de volver hacia atrás).


SOLUCION RECURSIVA Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a laprimera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

Algoritmo Torres de Hanói (Complejidad )

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada

Salida: La pila destino

1. si origen entoncesa. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila

destino)

b. terminar

2. si no

a. hanoi(,origen,destino, auxiliar) //mover todas las fichas menos la

más grande (n) a la varilla auxiliar

3. mover disco n a destino //mover la ficha grande hasta la varilla final

4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes,...