Torres Hanoi
1°-¿Que son 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. Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas. 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.
La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es: 2n - 1
Descripción
El juego, en su forma más tradicional, consiste en tres postes verticales. En uno de los postes se apila un número indeterminado de discos perforados por su centro (elaborados de madera), que determinará la complejidad de la solución. Por regla general se consideran siete discos. Los discos se apilan sobre uno de los postes en tamaño decreciente de abajo a arriba. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio -desde la base del poste hacia arriba- en uno de los postes, quedando los otros dos postes vacíos. El juego consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples reglas:
- Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes.
- Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo.
- Solo se puede desplazar el disco que se encuentre arriba en cada poste.
Existen diversas formas de llegar a la solución final, todas ellas siguiendo estrategias diversas.
2°-¿Como es el algoritmo para resolver el problema de las Torres de Hanoi?
La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2n - 1, donde n es la cantidad de discos.
Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.
Solución simple
Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la varilla auxiliar. El disco 2.o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.o 1 se mueve también a la varilla destino para que quede sobre el disco n.o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.
Mediante recursividad
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 la primera 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:
El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2n – 1, siendo n el número de discos.
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 necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares solo 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.
Una forma equivalente de resolverlo es la siguiente: coloreando los discos pares de un color y los impares 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).
Reglas matemáticas de los desplazamientos
A la hora de resolver matemáticamente el problema, se producen numerosas circunstancias matemáticas particulares respecto a la resolución. Son las siguientes:
- La ficha número n (siendo 1 la más pequeña) se mueve por primera vez en el paso número 2^(n-1), y después de ese primer movimiento, se moverá cada 2^n movimientos. De este modo, la ficha 1, se mueve en 1, 3, 5, 7, 9... etc. La ficha 3, se mueve en 4, 12, 20, 28, 36... etc.
- Y el número de veces que se mueve cada ficha es de 2^(n-k),siendo n el número de fichas y k igual a 1 para la ficha más pequeña.
- El número de movimientos mínimo a realizar para resolver el problema es de (2^n)-1, siendo n el número de fichas.
- Todas las fichas impares (siendo 1 la más pequeña) se mueven siguiendo el mismo patrón. Asimismo, todas las fichas pares se mueven siguiendo el patrón inverso a las impares. Por ejemplo: si se quiere mover un número impar de piezas desde la columna 1 hasta la 3, sucederá lo siguiente:
- Todas las fichas impares seguirán este patrón de movimiento: 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1.
- Todas las fichas pares seguirán este patrón de movimiento: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3
- Estos patrones dependen únicamente del número de piezas. Si el número de piezas es par, los patrones de las impares serán los de las pares, y viceversa.
- Uniendo la primera regla con la segunda, se sabe siempre qué pieza hay que mover y a qué columna hay que desplazarla, por lo que el problema queda resuelto.
3°¿Es permutacion o combinación?
CUESTIONARIO
1°-¿Qué son las Torres de Hanoi?
La Torres de Hanoi es un rompecabezas o juego matemático.
2°-¿Cuándo se inventaron las Torres de Hanoi?
Fue inventado en 1883 por el matemático francés Édouard Lucas.
3°-¿En que consiste este juego?
Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero.
4°-¿Cuál es el objetivo del juego?
El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas. 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.
5°-¿Cual es la formula para el juego?
La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es: 2n - 1
6°-¿Cómo es el algoritmo para resolver el problema de las Torres de Hanoi?
La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2n - 1, donde n es la cantidad de discos.
Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.
7°-¿Mediante que procesos se puede resolver el problema de las Torres de Hanoi?
-Solución Simple
-Mediante recursividad
-Iterativa
8°-¿En qué consiste "La solución Simple"?
El disco 2.o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.o 1 se mueve también a la varilla destino para que quede sobre el disco n.o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.
9°-¿En qué consiste la solución "Mediante Recursividad"?
Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera 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:
El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2n – 1, siendo n el número de discos.
10°-¿En qué consiste la solución "Iterativa"?
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 solo existe un movimiento posible que no lo incluye.
No hay comentarios:
Publicar un comentario