Desafío de programación Java: recursiva las torres de hanoi

Este reto le ayuda a utilizar su talento de programación para escribir un programa Java que imprimirá los pasos necesarios para resolver un Torres de Hanoi rompecabezas dado el número de discos.

Las Torres de Hanoi es un rompecabezas de la lógica clásica que consta de tres clavijas verticales y un número de discos de diferentes diámetros. Cada disco tiene un agujero en el centro, permitiendo que los discos para deslizarse sobre las clavijas.

El rompecabezas comienza con todos los discos apilados sobre una de las clavijas, con el disco más grande en la parte inferior y el más pequeño en la parte superior. El objeto del rompecabezas es mover la pila de discos a una de las otras clavijas, obedeciendo sólo dos reglas simples: (1) se puede mover sólo un disco a la vez, y (2) que nunca se puede colocar un disco más grande de parte superior de una más pequeña.

La siguiente figura muestra la solución para una pila de tres discos. Como puede ver, la solución requiere de siete movimientos:

1. Mueva el disco 1 de la clavija 1 a la clavija 3.

2. Mueva el disco 2 de la clavija 1 a la clavija 2.

3. Mueva el disco 1 de la clavija 3 de la clavija 2.

4. Mueva el disco 3 de la clavija 1 a la clavija 3.

5. Mueva el disco 1 de la clavija 2 a la clavija 1.

6. Mueva el disco 2 de la clavija 2 a la clavija 3.

7. Mueva el disco 1 de la clavija 1 a la clavija 3.

Después de estos siete pasos, la pila de discos estará en la clavija 3.

El rompecabezas se pone interesante cuando se empieza la adición de discos a la posición inicial. Con tres discos, el rompecabezas requiere sólo 7 movimientos para resolver. Con cuatro discos, se requieren 15 se mueve. Con cinco discos, tendrá 31 movimientos. Seis discos requiere 64 se mueve.

Si usted ha estado siguiendo los cálculos, el número de movimientos necesarios para resolver el rompecabezas aumenta exponencialmente a medida que el número de discos aumenta. En concreto, el número de movimientos necesaria para mover n discos es 2ⁿ - 1. Por ejemplo, una pila de 20 discos requerirá 2²⁰ - 1 moves- que es más de un millón de movimientos!

Un interesante leyenda se asocia con el rompecabezas: En un templo en Hanoi, los monjes han estado trabajando en un rompecabezas Torres de Hanoi con 64 discos desde la creación de la tierra. Cuando terminan, el mundo llegará a su fin. Afortunadamente, tenemos un largo tiempo de espera: Si los monjes pueden mover un disco por segundo, pasarán otros 580 mil millones años o más antes de terminar el rompecabezas.

Su reto es simple: escribir un programa Java que imprimirá los pasos necesarios para resolver un Torres de Hanoi rompecabezas dado el número de discos. El programa debe primero solicitar al usuario el número de discos. Luego se debe mostrar los pasos, uno por línea. Cada paso debe indicar qué clavija para mover un disco de y que la clavija para mover el disco para. Los pasos también deben ser numerados secuencialmente.

Una vez terminado, el programa debe repetir, preguntando al usuario el número de discos de nuevo. El programa debe terminar cuando el usuario entra en 0.

He aquí una muestra de la salida de la consola de su programa debe generar:

¿Cuántos discos? (0 a extremo) 31: 1 a 32: 1 a 23: 3 a 24: 1 a 35: 2 a 16: 2 a 37: 1 a 3¿Cómo muchos discos? (0 a extremo)0

El único requisito para la solución de este reto es que su solución debe utilizar la programación recursiva. En otras palabras, su solución debe incluir un método que se llama para resolver el rompecabezas.

Programación recursiva puede ser un reto, así que aquí están algunos consejos para la solución de este rompecabezas:

• El rompecabezas se compone de tres clavijas. Uno de ellos contiene el stack inicial de la llamada disks- esta clavija del peg fuente. Una de las dos clavijas restantes es la vinculación que desea mover la pila de discos To- llamar a esta clavija de la peg objetivo. La tercera clavija está disponible para su uso como una clavija intermedia para almacenar discos de forma temporal a medida que los mueve. Llama a esta clavija de la peg repuesto.

• Su método recursivo debe aceptar tres parámetros: el número de discos para mover, peg fuente, y la clavija de destino. Utilice los valores enteros 1, 2 y 3 para representar las clavijas.

• La idea básica de resolver el rompecabezas de forma recursiva es la siguiente: Para mover una pila de discos de un gancho de origen a un tipo de cambio de destino requiere tres pasos:

• Mueva todos los discos en la pila, excepto para el disco inferior a la clavija de repuesto.

• Mueva el disco más grande de la pila original a la clavija de destino.

• Mueva la pila que movió en el paso 1 de la clavija de repuesto a la clavija de destino.

• Por supuesto, las reglas del rompecabezas le permiten mover sólo un disco a la vez, por lo que no pueden lograr los pasos 1 y 3 del procedimiento dado aquí simplemente recoger la pila y moverlo. Ahí es donde la recursividad entra. Para los pasos 1 y 3, se llama al método de forma recursiva, cada vez que especificar un disco menos se mueva, y cada vez que utiliza la clavija objetivo anterior como la clavija de repuesto.

• Se pregunta por qué el método recursivo no tiene por qué aceptar la paridad repuesto como argumento? Porque se puede fácilmente calcular que, dadas las clavijas de origen y de destino. Puesto que hay sólo tres clavijas, numeradas 1, 2, y 3, la suma de las tres clavijas es 6 (1 + 2 + 3). Dadas las clavijas de origen y de destino, se puede calcular la paridad repuesto restando la clavija de origen y destino de 6. Por ejemplo, si la clavija de origen es 1 y la clavija de destino es 3, la clavija de repuesto debe ser 2 porque

  6 - 3 - 1 = 2.

Para la solución, vaya a la Descargas pestaña de El Java All-in-One For Dummies, Página cuarto producto Edition.

¡Buena suerte!