Java Programação Desafio: Recuperando as Torres de Hanoi - dummies

Este desafio ajuda você a usar seus talentos de programação para escrever um programa Java que imprimirá as etapas necessárias para resolver um enigma de Towers of Hanoi, dado o número de discos.

The Towers of Hanoi é um enigma de lógica clássico que consiste em três cavilhas verticais e uma série de discos de vários diâmetros. Cada disco tem um orifício no centro, permitindo que os discos sejam deslizados sobre as cavilhas.

O quebra-cabeça começa com todos os discos empilhados em uma das cavilhas, com o maior disco na parte inferior e o menor no topo. O objeto do quebra-cabeça é mover a pilha de discos para uma das outras cavilhas, obedecendo apenas duas regras simples: (1) você pode mover apenas um disco por vez, e (2) você nunca pode colocar um disco maior topo de um menor.

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. Mover o disco 1 de Peg 1 para Peg 3.

2. Mover o disco 2 do Peg 1 para o Peg 2.

3. Mover o disco 1 do Peg 3 para o Peg 2.

4. Mover o Disco 3 do Peg 1 para o Peg 3.

5. Mover o Disco 1 do Peg 2 para o Peg 1.

6. Mover o Disco 2 do Peg 2 para o Peg 3.

7. Mover o disco 1 de Peg 1 para Peg 3.

Após estes sete passos, a pilha de discos estará no Peg 3.

A solução para o quebra-cabeça Towers of Hanoi com três discos.

O quebra-cabeça fica interessante quando você começa a adicionar discos à posição inicial. Com três discos, o quebra-cabeça requer apenas 7 movimentos para resolver. Com quatro discos, são necessários 15 movimentos. Com cinco discos, você precisará de 31 movimentos. Seis discos requerem 64 movimentos.

Se você seguiu 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 os discos n é 2 ⁿ - 1. Por exemplo, uma pilha de 20 discos exigirá 2 ²⁰ - 1 movimentos; Isso é mais de um milhão de movimentos!

Uma legenda interessante está associada ao quebra-cabeça: em um templo em Hanói, os monges trabalharam em um puzzle Towers of Hanoi com 64 discos desde a criação da Terra. Quando terminem, o mundo chegará ao fim. Felizmente, temos muito tempo para esperar: se os monges podem mover um disco por segundo, serão mais 580 bilhões de anos antes de terminar o quebra-cabeça.

Seu desafio é simples: escreva um programa Java que imprimirá as etapas necessárias para resolver um puzzle Towers of Hanoi dado o número de discos. O programa deve primeiro solicitar ao usuário o número de discos. Em seguida, deve exibir os passos, um por linha.Cada passo deve indicar a qual pega para mover um disco e para qual pega para mover o disco. As etapas também devem ser numeradas seqüencialmente.

Uma vez terminado, o programa deve repetir, perguntando ao usuário o número de discos novamente. O programa deve terminar quando o usuário entrar 0.

Aqui está uma amostra da saída do console que seu programa deve gerar:

Quantos discos? (0 a fim) 3 1: 1 a 3 2: 1 a 2 3: 3 a 2 4: 1 a 3 5: 2 a 1 6: 2 a 3 7: 1 a 3 Quantos discos ? (0 a fim) 0

O único outro requisito para resolver esse desafio é que sua solução deve usar a programação recursiva. Em outras palavras, sua solução deve incluir um método que se chame a resolver o enigma.

A programação recursiva pode ser desafiadora, então aqui estão algumas dicas para a solução deste quebra-cabeça:

• O quebra-cabeça consiste em três cavilhas. Um deles contém a pilha inicial de discos; chame essa peg a fonte peg . Uma das duas pinos restantes é a peça em que você deseja mover a pilha de discos; chame essa peg a alvo peg . A terceira peg está disponível para você usar como uma peg intermediária para armazenar discos temporariamente quando você os move. Ligue para esta peça a pedaço sobressalente .

• O seu método recursivo deve aceitar três parâmetros: o número de discos a serem movidos, a ligação da fonte e a captura de destino. Use os valores inteiros 1, 2 e 3 para representar as cavilhas.

• A idéia básica de resolver o enigma de forma recursiva é a seguinte: mover uma pilha de discos de uma cavilha de origem para uma pegada de destino requer três etapas:

  1. Mover todos os discos na pilha, exceto o disco inferior para o Pegada sobressalente.

  2. Mova o disco maior na pilha original para o peg de destino.

  3. Mova a pilha que você moveu no Passo 1 da pegada sobressalente para a cavilha de destino.

• Claro, as regras do quebra-cabeça permitem que você mova apenas um disco por vez, então você não pode realizar os passos 1 e 3 do procedimento fornecido aqui, simplesmente, pegando a pilha e movendo-a. É aí que a recursão entra. Para os Passos 1 e 3, você chama o método de forma recursiva, cada vez que especifica um disco menor para ser movido, e cada vez que usa a pegada de destino anterior como a pegada de reposição.

• Perguntando por que o método recursivo não precisa aceitar a pegada sobressalente como argumento? Porque você pode calculá-lo facilmente, tendo em conta as cavilhas de origem e de destino. Uma vez que existem apenas três cavilhas, numeradas 1, 2 e 3, a soma das três cavilhas é 6 (1 + 2 + 3). Dado os pinos de origem e de destino, você pode calcular a pegada de reposição subtraindo a cavilha de origem e de destino de 6. Por exemplo, se a cavilha de fonte for 1 e a cavilha de destino for 3, a cavilha de reposição deve ser 2 porque

  6 - 3 - 1 = 2.

Para a solução, vá para a guia Downloads da página de produtos Java All-in-One For Dummies, 4th Edition.

Boa sorte!