torre de hanói - Wikilingue - Encydia
La Torre de Hanói es uno quiebra-cabeza que consiste en una base conteniendo tres pasadores, en uno de los cuales son dispuestos algunos discos unos sobre los otros, en orden creciente de diámetro, de cima para bajo. El problema consiste en pasar todos los discos de un pasador para otro cualquiera, usando uno de los pasadores como auxiliar, de modo que un disco mayor nunca quede encima de otro menor en ninguna situación. El número de discos puede variar siendo que el más simple contiene sólo tres.
La Torre de Hanói ha sido tradicionalmente considerada como un procedimiento para evaluación de la capacidad de memoria de trabajo, y principalmente de planificación y solución de problemas.
Tabla de contenido |
Orígenes
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 Hanói , en el Vietnam.
Existen varias leyendas acerca del origen del juego, de más conocida dice respeto a un templo Hindu, situado en el centro del universo. Se dice que Brahma supuestamente 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 fueran transferidos de una estaca para la otra, el templo desmoronar-se-iba y el mundo desaparecería.
Soluciones
ES interesante observar que el número mínimo de "movimientos" para conseguir transferir todos los discos de la primera estaca a la tercera es 2n-1, siendo n el número de discos. Inmediatamente:
Para solucionar un Hanói de 3 discos, son necesarios 2³ -1 movimientos = 7 movimientos
Para solucionar un Hanói de 7 discos, son necesarios 127 movimientos
Para solucionar un Hanói de 15 discos, son necesarios 32.767 movimientos
Para solucionar un Hanói de 64 discos, como dice la leyenda, son necesarios 18.446.744.073.709.551.615 movimientos.
Para entender la lógica de la Torre de Hanói es necesario analizar la construcción de diferentes niveles de la torre con el número mínimo de movimientos, teniendo el nivel anterior ya formado, siendo que esos niveles son el número de piezas desintegradas de la torre original que irán a formar otra torre con los más pequeños discos.
Para mover el primer disco de la torre original, 1 movimiento es gasto. Para mover el segundo de la torre original, siendo que el primero ya fue movido y será construida una torre con los 2 más pequeños discos, son gastos 2 movimientos. Para desplazar el tercer disco formando nueva torre con los tres más pequeños discos, teniendo la torre con los dos menores ya formada, son gastos 4 movimientos.
Así se sucede con los próximos discos hasta que el enésimo disco (el último) sea desplazado componiendo una torre con los otros discos teniendo una torre con el penúltimo disco y los demás juntos ya formada. La sucesión formada por la suma de los movimientos es una sucesión Falló al verificar gramática (El ejecutable texvc no fue encontrado. Consulte math/README para instrucciones de la configuración.): (1,2,4,8...2^n)
La fórmula Falló al verificar gramática (El ejecutable texvc no fue encontrado. Consulte math/README para instrucciones de la configuración.): 2^n-1
es provinda de la suma de una progresión geométrica.
Se sabe que en una progresión geométrica la suma de sus términos equivale a Falló al verificar gramática (El ejecutable texvc no fue encontrado. Consulte math/README para instrucciones de la configuración.): [a*(q^n-1)]/q-1 , donde "a" es el primer término y "q" es la razón.
Ya que la razón es 2 y el primer término es 1 tenemos que Falló al verificar gramática (El ejecutable texvc no fue encontrado. Consulte math/README para instrucciones de la configuración.): [a*(q^n-1)]/q-1 = [1*(2^n-1)]/2-1 = 2^n-1
Aplicación Práctica
La Torre de Hanói puede ser trabajada en niveles de desarrollo con niños. En la pre-escuela, con reglas simples de criba de colores y tamaños, la torre de Hanói ayuda en cuestiones de coordinación motora, identificación de formas, orden creciente y decrescente, entre otras formas de aprendizado.
De una manera más amplia, el juego puede ser usado para el establecimiento de estrategias de transferencia de las piezas, como la cuenta de los movimientos y raciocínio.
Iniciando con un número más pequeño de piezas, o sea, resolviendo problemas más simples, tendremos oportunidad de experimentar una de las más importantes formas de raciocínio matemático.
Ventajas
Algoritmos recursivos son más compactos para ese tipo de algoritmo, más legibles y más fáciles de ser comprendidos. Además de la facilidad de ser implementados en lenguajes de programación.
Desvantagens
Por usar intensivamente la pila, los algoritmos recursivos tienden a ser más lentos que los iterativos, sin embargo puede merecer la pena sacrificar la eficiencia en beneficio de la claridad.
Conclusión
La Torre de Hanoi consiste en pasar todos los discos de una extremidad la otra sin que un disco mayor quede encima de un más pequeño.
Sus aplicaciones son básicamente usadas en escuelas para que los profesores puedan mejorar y desarrollar el cognitivo de los niños, además del trabajo en grupo. Siendo este aplicado en pequeños grupos o individualmente.
La Torre de Hanói posee varias formas de resolución. Una de ellas es la resolución recursiva la cual podemos decir que es de más limitada en cuanto al tiempo de realización, ya que su ejecución dependerá de algunos factores para hacerse más eficaz.
La resolución Iterativa utiliza algunos ciclos (estructuras) de repetición (sea, whiles) que pueden ser llamados de lazos, existe aún la posibilidad de algunas estructuras adicionales (más complejas) las cuales hacen el algoritmo más rápido.
ES hecho que todo algoritmo recursivo posee un algoritmo interactivo equivalente; Dependiendo sólo de su complejidad de construcción.
Conexiones externas
