Desafio de programação Java: recursing as Torres de Hanói

Este desafio ajuda 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.

As Torres de Hanoi é um puzzle clássico que consiste em três pinos verticais e uma série de discos de vários diâmetros. Cada disco tem um orifício no centro, permitindo que os discos para ser deslizado ao longo dos pinos.

O quebra-cabeças começa com todos os discos empilhados sobre uma das cavilhas, com a maior disco na parte inferior e o menor na parte superior. 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.

A figura a seguir mostra a solução para uma pilha de três discos. Como você pode ver, a solução requer sete movimentos:

1. Mova o disco 1 do Peg 1 a Peg 3.

2. Mova o disco 2 do Peg 1 a Peg 2.

3. Mova o disco 1 do Peg 3 a Peg 2.

4. Mova disco 3 de Peg 1 a Peg 3.

5. Mova o disco 1 do Peg 2 a Peg 1.

6. Mova o disco 2 do Peg 2 a Peg 3.

7. Mova o disco 1 do Peg 1 a Peg 3.

Após estes sete passos, a pilha de discos irá estar em 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.

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 2 é discosⁿ- 1. Por exemplo, uma pilha de discos 20 vai exigir dois²⁰ - 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 eles terminarem, 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 e que peg para mover o disco para. As etapas também devem ser numeradas 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 até o final) 31: 1 a 32: 1 para 23: 3 a 24: 1 para 35: 2 para 16: 2 para 37: 1 para 3Como muitos discos? (0 até o final)0

O único outro requisito 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- esta indexação do 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 de reposição.

• Seu método recursivo deve aceitar três parâmetros: o número de discos para mover, peg origem eo peg-alvo. Use 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, excepto para o disco inferior para a cavilha de reposição.

• Mova o maior disco na pilha original para o peg-alvo.

• Mover a pilha você moveu na etapa 1 do peg de 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 de reposição.

• Perguntando por que o método recursivo não precisa aceitar o 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 eo destino estacas, você pode calcular o pino de reposição, subtraindo o peg de 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 de 2 por causa

  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!