Torre de Hanoi com N discos utilizando recursividade.[RESOLVIDO]

Bem galera, sou novo aqui e estou precisando da ajuda de vocês. Estou estudando função recursiva e preciso resolver o problema da famosa Torre de Hanoi para “n” discos, ou seja, o usuário vai informar quantos discos tem a torre que ele quer a resolução. A princípio, por este ser um problema comum, achei várias resoluções na internet porém, sempre na forma interativa; e eu preciso fazer utilizando recursão.
Segue abaixo um modelo que gostei bastante por estar bastante claro. Eu encontrei aqui mesmo no GUJ mas esta na forma interativa… Dêem uma olhada para facilitar, já que o que preciso é apenas alterar a forma desta resolução.

import java.util.InputMismatchException;
import java.util.Scanner;

Algoritmo iterativo Hanoi

@author Fábio
*/
public class HanoiIterativo {

private int qtDiscos;

private int tamanhoMax;

private String sequenciaPares[] = {“1–>2”, “2–>3”, “3–>1”};//para pares

private int indexPar;

private int indexImpar;

private String sequenciaImpares[] = {“1–>3”, “1–>2”, “3–>2”};//paraimapres

public void lerDados() {

System.out.println(“Digite a quantidade de  discos”);

Scanner rc = new Scanner(System.in);

try{

qtDiscos = rc.nextInt();

}catch(InputMismatchException e){

System.out.println(“Amigão é fácil,digite o numero de discos em inteiros por favor!”);

lerDados();

}

tamanhoMax = (int) Math.pow(2, qtDiscos) - 1;

}
public void hanoi() {

if (qtDiscos % 2 == 0) {
   sequenciaPares  = new String[]{"1--->2", "2--->3", "3--->1"};//para pares
   sequenciaImpares =new String[]{"1--->3", "1--->2", "3--->2"};//para impares
 }else{
   sequenciaPares  = new String[]{"1--->3", "3--->2", "2--->1"};//para pares
   sequenciaImpares =new String[]{"1--->2", "1--->3", "2--->3"};//para impares
 }
  for (int i = 0; i < tamanhoMax; i++) {
         if (i % 2 == 0) {
             if (indexPar > 2) {
                 indexPar = 0;
             }
             System.out.println(sequenciaPares[indexPar]);
             indexPar++;
         } else {
             if (indexImpar > 2) {
                 indexImpar = 0;
             }
              System.out.println(sequenciaImpares[indexImpar]);
             indexImpar++;
         }
   
     }

}

public static void main(String[] args) {

HanoiIterativo h = new HanoiIterativo();

h.lerDados();

h.hanoi();

}

}

1 Resposta

guilherme.oq 11 de jun. de 2010

Bem, ninguem postou nada mas eu achei a resposta. Vou deixar aqui para ajudar outros. RESOLVIDO. :lol:

package hanoiex;

/**
*

@author Marcos
*/
public class TowerOfHanoi
{
int numDisks; // número de discos a serem movidos
```
public TowerOfHanoi( int disks )

{

numDisks = disks;

} // fim do construtor TowerOfHanoi
```
```
// move os discos recursivamente pelas torres

public void solveTowers( int disks, int sourcePeg, int destinationPeg,

int tempPeg )

{

// caso básico – somente um disco a ser movido

if ( disks == 1 )

{

System.out.printf( “\n%d --> %d”, sourcePeg, destinationPeg );

return;

} // fim do if
```
// passo de recursão – move o disco p/ tempPeg, e depois p/ destinationPeg
// move ( disks - 1 ) discos de sourcePeg para tempPeg recursivamente
solveTowers( disks - 1, sourcePeg, tempPeg, destinationPeg );

// move o último disco de sourcePeg para destinationPeg
System.out.printf( “\n%d --> %d”, sourcePeg, destinationPeg );

// move ( disks - 1 ) discos de tempPeg para destinationPeg
solveTowers( disks - 1, tempPeg, destinationPeg, sourcePeg );
} // fim do método solveTowers
} // fim da classe TowerOfHanoi

package hanoiex;

/**
*

@author Marcos

*/

public class HanoiTeste

{

public static void main( String args[] )

{

int startPeg = 1;   // valor 1 utilizado para indicar startPeg na saída

int endPeg = 3;     // valor 3 utilizado para indicar endPeg na saída

int tempPeg = 2;    // valor 2 utilizado para indicar tempPeg na saída

int totalDisks = 5; // número de discos

TowerOfHanoi towersOfHanoi = new TowerOfHanoi( totalDisks );

// chamada não recursiva inicial: move todos os discos.
towersOfHanoi.solveTowers( totalDisks, startPeg, endPeg, tempPeg );
} // fim de main
} // fim da classe TowersOfHanoiTest

1 Resposta

Topicos relacionados