Torres de Hanói
Este Juego didáctico apto para niños y jóvenes, se emplea para promover diversos DISPOSITIVOS BÁSICOS DE APRENDIZAJE - DBA -.
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 nnn, el disco más grande. Al principio, todos los nnn 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 nnn está en la parte inferior y el disco 1 está en la parte superior. Aquí está cómo se ven las Torres de Hanói para n = 5n=5n, equals, 5 discos:
Configuración inicial de las Torres de Hanoi con 5 discos.
El objetivo es pasar todos los nnn discos de la varilla A a la varilla B:
Configuración final de las Torres de Hanoi con 5 discos
¿Suena fácil, verdad? No es tan sencillo, porque tienes que obedecer dos reglas:
1. Puedes mover solamente un disco a la vez.
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?
¿Qué pasa con dos discos? ¿Cómo resuelves el problema cuando n = 2n=2n, equals, 2? Puedes hacerlo en tres pasos. Aquí está cómo se ve al principio:
Configuración inicial de las Torres de Hanói con 2 discos
Primero, mueve el disco 1 de la varilla A a la varilla C:
Movimiento 1 de las Torres de Hanói, 2 discos
Movimiento 2 de las Torres de Hanoi, 2 discos
Por último, mueve el disco 1 de la varilla C a la varilla B:
Movimiento 3 de las Torres de Hanói, 2 discos
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 nnn, el disco más grande. Al principio, todos los nnn 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 nnn está en la parte inferior y el disco 1 está en la parte superior. Aquí está cómo se ven las Torres de Hanói para n = 5n=5n, equals, 5 discos:
Configuración inicial de las Torres de Hanoi con 5 discos.El objetivo es pasar todos los nnn discos de la varilla A a la varilla B:
Configuración final de las Torres de Hanoi con 5 discos
¿Suena fácil, verdad? No es tan sencillo, porque tienes que obedecer dos reglas:
1. Puedes mover solamente un disco a la vez.
2. 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 = 1n=1n, equals, 1. El caso de n = 1n=1n, 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.
Configuración inicial de las Torres de Hanói con 2 discos
Movimiento 1 de las Torres de Hanói, 2 discos
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:
Movimiento 2 de las Torres de Hanoi, 2 discos
Por último, mueve el disco 1 de la varilla C a la varilla B:
Movimiento 3 de las Torres de Hanói, 2 discos
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í").
Descargar
________________________________________Descargar
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Carmen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
