Contenido principal
Ciencias de la computación
Torres de Hanoi
Si pasaste por la lección acerca de recursividad, entonces estás listo para ver otro problema en donde hacer recursividad varias veces realmente ayuda. Se llama las Torres de Hanoi. Te dan un conjunto de tres varillas y n discos, con cada disco de un tamaño diferente. Llamemos a las varillas A, B y C, y numeremos los discos desde 1, el disco más pequeño, hasta n, el disco más grande. Al principio, todos los n discos están en la varilla A, en orden de tamaño decreciente de la parte inferior a la parte superior, de modo que el disco n está en la parte inferior y el disco 1 está en la parte superior. Aquí está cómo se ven las Torres de Hanoi para n, equals, 5 discos:
El objetivo es pasar todos los n discos de la varilla A a la varilla B:
¿Suena fácil, verdad? No es tan sencillo, porque tienes que obedecer dos reglas:
- Puedes mover solamente un disco a la vez.
- Ningún disco puede estar encima de un disco más pequeño. Por ejemplo, si el disco 3 está en una varilla, entonces todos los discos debajo del disco 3 deben tener números mayores que 3.
Puedes pensar que este problema no es terriblemente importante. ¡Al contrario! Cuenta la leyenda que en algún lugar de Asia (Tíbet, Vietnam, India; escoge en Internet qué leyenda te gusta), los monjes están resolviendo este problema con un conjunto de 64 discos y, según la historia, los monjes creen que una vez que terminen de mover todos los 64 discos de la varilla A a la varilla B de acuerdo con las dos reglas, el mundo se acabará. ¿Si los monjes están en lo correcto, deberíamos entrar en pánico?
Primero, vamos a ver cómo resolver el problema de manera recursiva. Vamos a empezar con un caso realmente sencillo: un disco, es decir, n, equals, 1. El caso de n, equals, 1 será nuestro caso base. Siempre puedes mover el disco 1 de la varilla A a la varilla B, porque sabes que cualquier disco debajo debe ser mayor. Y no hay nada especial acerca de las varillas A y B. Puedes mover el disco 1 de la varilla B a varilla C si lo deseas, o de la varilla C a la varilla A, o de cualquier varilla a cualquier varilla. Resolver el problema de las Torres de Hanoi con un disco es trivial, y requiere mover el único un disco solamente una vez.
¿Qué pasa con dos discos? ¿Cómo resuelves el problema cuando n, equals, 2? Puedes hacerlo en tres pasos. Aquí está cómo se ve al principio:
Primero, mueve el disco 1 de la varilla A a la varilla C:
Observa que usamos la varilla C como una varilla libre, un lugar en donde poner el disco 1 para que podamos llegar al disco 2. Ahora que el disco 2 (el disco inferior) está expuesto, muévelo a la varilla B:
Por último, mueve el disco 1 de la varilla C a la varilla B:
Esta solución toma tres pasos, y una vez más no hay nada especial acerca de cómo mover los dos discos de la varilla A a la varilla B. Puedes moverlos de la varilla B a la varilla C al usar la varilla A como la varilla libre: mueve el disco 1 de la varilla B a la varilla A, luego mueve el disco 2 de la varilla B a la varilla C y termina por mover el disco 1 de la varilla A a la varilla C. ¿Estás de acuerdo que puedes mover los discos 1 y 2 de cualquier varilla a cualquier varilla en tres pasos? (Di que "sí").
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- como se resuelve una torre de hanoi?(4 votos)
- en ir moviendo los numeros pero no dejar un numero chico abajo de un grande(3 votos)
- - Tiene alguna importancia en que varilla se encuentren los discos al inicio del problema?
- Tienen algún nombre en particular las varillas? Lo digo porque parece que siempre va a ver una en la que se encuentren todos los discos mientras que las restantes se usan para pasos intermedios.
- Hay alguna relación entre la cantidad de discos, el número de varillas y la cantidad de pasos para resolver el problema.
- El juego es siempre con tres varillas?(3 votos) - como se resuelve una torre de hanoi?(3 votos)
- ¿Cual es el menor numero de movimientos que puedo hacer con una torre de 7 discos, en mi caso quiero pasarlos del punto "A" al punto "C"?(2 votos)
- el numero mínimo de movimientos para resolver uno de 7 discos es = 127(2 votos)
- la torre de hanoi se determinaria como una aplicacion interlineada en las funciones.(1 voto)
- el numero mínimo de movimientos para resolver uno de 7 discos es = 127(1 voto)
- ya ok como se resuelven?(1 voto)