La Vaca

Torres de Hanói
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
[pic]
[pic]
Torres de Hanói.
[pic]
Etapas de la resolución del problema con 4 discos.
Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.[1] Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una delas tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo dos reglas: Las piezas se trasladan de una en una y no se puede colocar una pieza mayor sobre una menor. El problema 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 problema de las Torres de Hanói es curiosísimoporque 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. Existen algunas versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual osuperior a 3) de ellas.
|Contenido |
|[ocultar] |
|1 Solución Algorítmica |
|1.1 Mediante recursividad |
|1.2 Iterativa|
|2 Referencias |
|3 Véase también |
|4 Enlaces externos |


[editar] Solución Algorítmica
Una forma de resolver la colocación de la torre es fundamentándose en el disco más pequeño, en este caso elde hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego; el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa dela varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.
[editar] Mediante recursividad
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a laintermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:
1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la másgrande (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, {0...n-1}, encima de la ficha grande (n)
5. terminar

Iterativa

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 necesariomover 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.

[editar] Referencias


La Torre de Hanoi


Índice

1. Introducción
2. Notación
3. Un algoritmo recursivo
4. Dos...