Java desafio de programação: recursão as torres de hanoi
Video: Torres de Hanoi com recursão em Java - Canal do Código
Conteúdo
Este desafio ajuda você a usar seus talentos de programação para escrever um programa em Java que irá imprimir os passos necessários para resolver um enigma Torres de Hanói dado o número de discos.
O Torres de Hanói é um puzzle clássico que consiste em três cavilhas verticais e um número de discos de vários diâmetros. Cada disco tem um buraco no centro, permitindo que os discos para ser deslizado ao longo dos pinos.
O quebra-cabeça começa com todos os discos empilhados em uma das estacas, com o maior disco na parte inferior eo menor no topo. O objeto do enigma é mover a pilha de discos para um dos outros pinos, obedecendo apenas duas regras simples: (1) você pode mover apenas um disco de cada vez, e (2) você nunca pode colocar um disco maior em topo de uma mais pequena.
Video: Estrutura de Dados e Algoritmos com Java: Pilhas: Exer 08 Desafio Torre de Hanoi
A figura seguinte mostra a solução de uma pilha de três discos. Como você pode ver, a solução requer sete movimentos:
Mova o disco 1 do Peg 1 a Peg 3.
Mova o disco 2 do Peg 1 a Peg 2.
Mova o disco 1 do Peg 3 a Peg 2.
Mova disco 3 de Peg 1 a Peg 3.
Mova o disco 1 do Peg 2 a Peg 1.
Mova o disco 2 do Peg 2 a Peg 3.
Mova o disco 1 do Peg 1 a Peg 3.
Video: 12 - Torres de Hanoi mediante Recursividad (EDDJava)
Após estes sete passos, a pilha de discos será no Peg 3.
O quebra-cabeça fica interessante quando você começar a adicionar discos para a posição inicial. Com três discos, o enigma requer apenas 7 move-se para resolver. Com quatro discos, 15 movimentos são necessários. Com cinco discos, você vai precisar de 31 movimentos. Seis discos requer 64 movimentos.
Video: Jogo Torre de Hanoi - logica de programação
Se você estiver seguindo a matemática, o número de movimentos necessários para resolver o quebra-cabeça aumenta exponencialmente à medida que o número de discos aumenta. Especificamente, o número de movimentos necessários para mover n discos é 2n - 1. Por exemplo, uma pilha de 20 discos exigirá 220 - 1 moves- que é mais de um milhão de movimentos!
Uma lenda interessante é associado com o quebra-cabeça: Em um templo em Hanoi, monges têm vindo a trabalhar em um quebra-cabeça Torres de Hanói, com 64 discos desde a criação da terra. Quando terminar, o mundo vai chegar a um fim. Felizmente, temos um longo tempo de espera: Se os monges pode mover um disco por segundo, será mais 580 bilhões de anos antes de terminar o quebra-cabeça.
Seu desafio é simples: Escreva um programa Java que irá imprimir os passos necessários para resolver um enigma Torres de Hanói dado o número de discos. O programa deve primeiro solicitar ao usuário o número de discos. Em seguida, ele deve exibir os degraus, um por linha. Cada passo deve indicar qual peg para mover um disco a partir de, e que peg para mover o disco para. As etapas também devem ser numerados sequencialmente.
Uma vez terminado, o programa deve repetir, pedindo ao usuário o número de discos novamente. O programa deve terminar quando o usuário insere 0.
Aqui está um exemplo da saída do console seu programa deve gerar:
Quantos discos? (0 a final) 31: 1 a 32: 1 para 23: 3 a 24: 1 para 35: 2 a 16: 2 a 37: 1 para 3Como muitos discos? (0 a final)0
A única outra exigência para resolver este desafio é que a sua solução deve usar programação recursiva. Em outras palavras, sua solução deve incluir um método que se chama para resolver o enigma.
Programação recursiva pode ser um desafio, então aqui estão algumas dicas para a solução deste enigma:
O quebra-cabeça é composto por três pinos. Um deles contém o stack inicial de chamada disks- este peg o peg fonte. Uma das restantes dois pinos é o pino que você deseja mover a pilha de discos to- chamar este peg o peg-alvo. O terceiro pino está disponível para você usar como um peg intermediária para armazenar discos em temporariamente como você movê-los. Chame esse peg o peg reposição.
Seu método recursivo deve aceitar três parâmetros: o número de discos para mover, peg fonte, eo peg-alvo. Utilizar os valores inteiros 1, 2 e 3 para representar os pinos.
A idéia básica de resolver o quebra-cabeça de forma recursiva é esta: Para mover uma pilha de discos de um pino de origem para um peg-alvo requer três etapas:
Mover todos os discos na pilha exceto para o disco inferior ao peg livre.
Mova o maior disco na pilha original para o peg-alvo.
Mover a pilha você moveu na etapa 1 do peg reposição para o peg-alvo.
É claro, as regras de quebra-cabeça permitem mover apenas um disco de cada vez, para que você não pode realizar os passos 1 e 3 do procedimento dado aqui, simplesmente pegando a pilha e movê-lo. É aí que a recursão entra em ação. Para os passos 1 e 3, você chamar o método de forma recursiva, cada vez especificando um a menos disco a ser movido, e cada vez usando o peg-alvo anterior como o peg livre.
Perguntando por que o método recursivo não precisa aceitar a peg de reposição como um argumento? Porque você pode facilmente calcular que, dada a origem eo destino pinos. Uma vez que existem apenas três cavilhas, numerados de 1, 2, e 3, a soma das três cavilhas é 6 (1 + 2 + 3). Dada a origem e de destino estacas, você pode calcular o pino de reposição, subtraindo o peg origem e de destino a partir 6. Por exemplo, se o peg fonte é 1 eo peg-alvo é 3, o pino de reposição deve ser 2 porque
6 - 3 - 1 = 2.
Para a solução, vá para o guia Downloads do Java All-in-One For Dummies, 4ª página do produto Edition.
Boa sorte!