Java desafío de programación: de manera recursiva las torres de hanoi
Video: Entendiendo la recursividad con las Torres de Hanoi
Este reto le ayuda a utilizar sus talentos de programación para escribir un programa Java que imprimirá los pasos necesarios para resolver un rompecabezas Torres de Hanoi dado el número de discos.
Video: Recursividad en Java Cap 03 - Torres de Hanoi
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 en 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 clavijas de otros, obedeciendo sólo dos reglas simples: (1) Sólo se puede mover un disco a la vez, y (2) nunca se puede colocar un disco más grande de la parte superior de una más pequeña.
La siguiente figura muestra la solución para una pila de tres discos. Como se puede ver, la solución requiere siete movimientos:
Mover el disco 1 de Peg Peg 1 a 3.
Mover el disco 2 de Peg Peg 1 a 2.
Mover el disco 1 de Peg Peg 3 a 2.
Mover el disco 3 de Peg Peg 1 a 3.
Mover el disco 1 de Peg Peg 2 a 1.
Mover el disco 2 de Peg Peg 2 a 3.
Mover el disco 1 de Peg Peg 1 a 3.
Video: Estrutura de Dados e Algoritmos com Java: Pilhas: Exer 08 Desafio Torre de Hanoi
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 movimientos. Con cinco discos, necesitará 31 movimientos. Seis discos requiere 64 movimientos.
Si usted ha estado siguiendo los cálculos, el número de movimientos necesarios para resolver el puzzle aumenta exponencialmente a medida que el número de discos aumenta. Específicamente, el número de movimientos necesaria para mover norte discos es 2norte - 1. Por ejemplo, una pila de 20 discos requerirá 220 - 1 moves- que es más de un millón de movimientos!
Una 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 de años antes de que termine el puzzle.
Su reto es simple: escribir un programa Java que imprimirá los pasos necesarios para resolver un rompecabezas Torres de Hanoi dado el número de discos. El programa debe primero solicitar al usuario el número de discos. A continuación, debe mostrar los pasos, uno por línea. Cada paso debe indicar qué clavija para mover de disco, y el que la clavija para mover el disco a. Los pasos también deben ser numeradas secuencialmente.
Una vez terminado, el programa debe repetir, preguntar al usuario por el número de discos de nuevo. El programa debería terminar cuando el usuario entra en 0.
Este es un ejemplo 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 problema es que la solución debe utilizar la programación recursiva. En otras palabras, la solución debe incluir un método que llama a sí mismo para resolver el puzzle.
Video: Torres Hanoi - Java
la programación recursiva puede ser un reto, por lo que aquí hay algunos consejos para la solución de este rompecabezas:
El rompecabezas se compone de tres clavijas. Uno de ellos contiene la pila inicial de la llamada disks- esta clavija del PEG fuente. Una de las dos clavijas restantes es la clavija que desea mover la pila de discos a- llamar a esta clavija de la PEG objetivo. La tercera clavija está disponible para su uso como una clavija intermedia para almacenar los discos en 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. Usa 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:
Mover todos los discos de la pila, excepto para el disco inferior a la clavija de repuesto.
Mover el disco más grande de la pila original a la clavija de destino.
Mover la pila movió en el paso 1 de la clavija de repuesto a la clavija de destino.
Por supuesto, las reglas del rompecabezas le permiten moverse con 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 entra en juego la recursividad. Para los pasos 1 y 3, se llama al método de forma recursiva, especificando cada vez menos uno de los discos que desea mover, y cada vez que utiliza la anterior paridad como objetivo la clavija de repuesto.
Se pregunta por qué el método recursivo no tiene por qué aceptar la clavija de repuesto como un argumento? Porque se puede calcular fácilmente 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 clavija de repuesto restando el origen y el destino de PEG 6. Por ejemplo, si la clavija fuente es 1 y la clavija objetivo 3, la clavija de repuesto debe ser 2, ya
6 - 3 - 1 = 2.
Para la solución, vaya a la pestaña de descargas del Java Todo-en-uno para los maniquíes, 4ª Edición página del producto.
¡Buena suerte!