Pessoal bom dia
Alguem sabe como resolver o problema da torre de Hanoi estou qubrando a cabeça
Torre de Hanoi
13 Respostas
Dê uma olhada em :
Aee galera estou com grande dificuldade para conseguir fazer os movimentos das peças,
vou postar aqui o meu código pra vocês verem como está.
Fiz com 3 arrays, cada um representando uma torre, só que agora não sei como fazer para mover os valores
de um array para o outro.
import javax.swing.JOptionPane;
public class TorreHanoi {
public static void main (String args[]){
int x = Integer.parseInt(JOptionPane.showInputDialog("Digite a qtde de discos"));
int pilhaA[] = new int [x];
int pilhaB[] = new int [x];
int pilhaC[] = new int [x];
for (int cont =0; cont<x; cont++){
pilhaA[cont]= cont;
}
if (){
}
}
}
Sei que na resolução da Torre de Hanoi existe um padrão de movimentação, ou seja, para qualquer quantidade de peças que vc tenha, bastá seguir este padrão que encontrará a quantidade de movimentos minimos, vou falar com o brother meu que encontrou este padrão e posto aqui depois! abs!
É simples. Vamos lá.
Você tem três pinos. Vamos chamar os pinos de A, B e C.
Seu objetivo é mover todas as peças do pino A para o pino C.
A solução da torre é mais fácil de ser visualizada se construída aos poucos.
Imagine que você tem que mover apenas um pino. É muito fácil. Você move o disco do pino A para o C.
Solução para dois discos. Move o primeiro disco para o pino B. Move o segundo disco para o pino C e por fim move o primeiro disco do pino B para o pino C.
Agora a solução para três discos (a mais genérica de todas e que você vai aplicar para qualquer número de pinos)
Mova o primeiro disco para do pino A para o pino C.
Mova o segundo disco do pino A para o pino B.
Mova o primeiro disco do pino C para o pino B.
(Note que realizamos o mesmo procedimento que fizemos com dois discos)
Mova o terceiro disco do pino A para o pino C.
Mova o primeiro disco do pino B para o pino A.
Mova o segundo disco do pino B para o pino C.
Mova o primeiro disco do pino A para o pino C.
Pronto.
Para quatro discos o procedimento é o mesmo. Você vai mover os três discos para o pino B, mover o quarto para o C e por fim mover novamente os três do pino B para o pino C.
Para cinco, faça mova quatro para o pino B, mova o quinto para o pino C e por fim mova novamente os quatro para o pino C.
A quantidade de movimentos necessária para mover os pinos é 2^n + 1, onde n é o número de discos.
Boa sorte.
F
È verdade existe sim um padrão.Tinha feito este trabalho na faculdade .O trabalho consistia em trasformar um algoritmo do Hanoi recursivo em interativo.Segue a lógica do padrão de números e para implementar é bem moleza!
Execute um qualquer algoritmo correcto do Hanoi para 4 , 6 , 8 n+2 disco numeros pares
vai perceber que sempre a sequência é a seguinte:
Neste caso Hanoi para 4 discos,temos;
move 1 --> 2 “indice 0” imagine esta estrutura como sendo uma lista ou um array por isso “indices”
move 1 --> 3
move 2 --> 3 “indice 2”
move 1 --> 2
move 3 --> 1 “indice 4”
move 3 --> 2
move 1 --> 2 “indice 6”
move 1 --> 3
move 2 --> 3 “indice 8”
move 2 --> 1
move 3 --> 1 “indice 10”
move 2 --> 3
move 1 --> 2 “indice 12”
move 1 --> 3
move 2 --> 3 “indice 14”
Perceba que a cada indice par vc tem uma sequência com um padrão ou seja
1->2
2->3
3->1
1->2
2->3
3->1
ect…
E que para cada indice impar vc tem outra sequência
1->3
1->2
3->2
1->3
1->2
3->2
ect…
Agora preste atenção que quando executar hanoi para 7 discos ou seja um numero impar terá o inverso!
Bom tenho essa implementação em C e em Java é melhor ainda para implementar,então bom estudo!! 
Sabe esse codigo das torres de hanoi iterativo e muito pau !
Será que vc pode postar o codigo em c , ou em java , para download .Eu agradeceria .
F
Cara como o programa que tinha feito em C era monstruosamente feio esta aqui em Java zero bala de e de graça!! :lol:
O bacana que nesse meu algoritmo é praticamente impossivel um estouro de memoria pq não
tem necessidade de armazenar uma pilha de dados como no caso da recursão!
Agora testa o Hanoi recursivo com 20 discos são necessário 4 minutos o meu interativo
necessita de 3 minutos!!Essas diferenças tu vai perceber na quantidade acima de 20 discos.
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();
}
}
Cara parabens eu me matei uma semna pra fazer uma logica iterativa pra isso ( desafio do professor muito gente fina que eu tive ) , e o maximo que eu consegui foi uma logica pra 5 discos pra ampliar tinha que copiar um bloco de codigo .Meus parabens.
F
Este é novo código em C que refiz do zero
#include <stdio.h>
#include <stdlib.h>
/**
Hanoi iterativo
* author Fábio
*/
int main(int argc, char *argv[])
{
int qtDiscos=20;
int tamanhoMax=(int) pow(2, qtDiscos) - 1;
int sequenciaPares[3];//para pares
int indexPar=0;
int indexImpar=0;
int sequenciaImpares[3];//para impares
int i=0;
if (qtDiscos % 2 == 0) {
sequenciaPares[0]=12;
sequenciaPares[1]=23;
sequenciaPares[2]=31;
////////////////////////
sequenciaImpares[0]=13;
sequenciaImpares[1]=12;
sequenciaImpares[2]=32;
}else{
sequenciaPares[0]=13;
sequenciaPares[1]=32;
sequenciaPares[2]=21;
////////////////////////
sequenciaImpares[0]=12;
sequenciaImpares[1]=13;
sequenciaImpares[2]=23;
}
for (i = 0; i < tamanhoMax; i++) {
if (i % 2 == 0) {
if (indexPar > 2) {
indexPar = 0;
}
printf(" %d ---> %d \n",sequenciaPares[indexPar]/10,sequenciaPares[indexPar]%10);
indexPar++;
} else {
if (indexImpar > 2) {
indexImpar = 0;
}
printf(" %d ---> %d \n",sequenciaImpares[indexImpar]/10,sequenciaImpares[indexImpar]%10);
indexImpar++;
}
}
system("PAUSE");
return 0;
}
Com 20 discos tempo de 1 minuto e 40 segundos!! Nem precisa comentar o do porque ne galera!
Gostaria de comparar o desempenho do meu algoritmo com de outros,alguém??
F
valeu ccefetpb
Mas me lembro que eu também penei para encontrar esse padrão,o caminmho de implementar a pilha imitando a recursão é bem mais trabalhoso!! Mas que talvez a nível academico seja até mais interessante assim o aluno aprende como funciona o todo:lol:
F
Lucas_Skyline,
Corregi o erro, realmente o código anterior que havia postado estava com um problema.
Teste com esse applet:
http://www.cut-the-knot.org/recurrence/hanoi.shtml
O disco "A" equivale ao mais a esquerda, o "C" é o do meio e o" B" é o último.
Explicando...
Quando vc escolhe 6 disco, por exemplo, vai ter [(2 elevado a 6) - 1] movimentações.
Executando para Hanoi com 6 discos temos:
execute: 1 A-->C
execute: 2 A-->B
execute: 3 C-->B
execute: 4 A-->C
execute: 5 B-->A
execute: 6 B-->C
execute: 7 A-->C
execute: 8 A-->B
execute: 9 C-->B
execute: 10 C-->A
execute: 11 B-->A
execute: 12 C-->B
execute: 13 A-->C
execute: 14 A-->B
execute: 15 C-->B
execute: 16 A-->C
execute: 17 B-->A
execute: 18 B-->C
execute: 19 A-->C
execute: 20 B-->A
execute: 21 C-->B
execute: 22 C-->A
execute: 23 B-->A
execute: 24 B-->C
execute: 25 A-->C
execute: 26 A-->B
execute: 27 C-->B
execute: 28 A-->C
execute: 29 B-->A
execute: 30 B-->C
execute: 31 A-->C
execute: 32 A-->B
execute: 33 C-->B
execute: 34 C-->A
execute: 35 B-->A
execute: 36 C-->B
execute: 37 A-->C
execute: 38 A-->B
execute: 39 C-->B
execute: 40 C-->A
execute: 41 B-->A
execute: 42 B-->C
execute: 43 A-->C
execute: 44 B-->A
execute: 45 C-->B
execute: 46 C-->A
execute: 47 B-->A
execute: 48 C-->B
execute: 49 A-->C
execute: 50 A-->B
execute: 51 C-->B
execute: 52 A-->C
execute: 53 B-->A
execute: 54 B-->C
execute: 55 A-->C
execute: 56 A-->B
execute: 57 C-->B
execute: 58 C-->A
execute: 59 B-->A
execute: 60 C-->B
execute: 61 A-->C
execute: 62 A-->B
execute: 63 C-->B
pegue todos os ímpares:
execute: 1 A-->C
execute: 3 C-->B
execute: 5 B-->A
execute: 7 A-->C
execute: 9 C-->B
execute: 11 B-->A
execute: 13 A-->C
execute: 15 C-->B
execute: 17 B-->A
execute: 19 A-->C
execute: 21 C-->B
execute: 23 B-->A
execute: 25 A-->C
execute: 27 C-->B
execute: 29 B-->A
execute: 31 A-->C
execute: 33 C-->B
execute: 35 B-->A
execute: 37 A-->C
execute: 39 C-->B
execute: 41 B-->A
execute: 43 A-->C
execute: 45 C-->B
execute: 47 B-->A
execute: 49 A-->C
execute: 51 C-->B
execute: 53 B-->A
execute: 55 A-->C
execute: 57 C-->B
execute: 59 B-->A
execute: 61 A-->C
execute: 63 C-->B
Percebeu alguma coisa? Existe um ciclo que sempre se repete a cada 3 posições:
execute: A-->C
execute: C-->B
execute: B-->A
Agora, separando os pares:
execute: 2 A-->B ------Ciclo do intervalo 2----
execute: 4 A-->C------Ciclo do intervalo 3 ----
execute: 6 B-->C ------Ciclo do intervalo 2----
execute: 8 A-->B------Ciclo do intervalo 4 ----
execute: 10 C-->A ------Ciclo do intervalo 2----
execute: 12 C-->B ------Ciclo do intervalo 3 ----
execute: 14 A-->B ------Ciclo do intervalo 2----
execute: 16 A-->C------Ciclo do intervalo 5 ----
execute: 18 B-->C ------Ciclo do intervalo 2----
execute: 20 B-->A ------Ciclo do intervalo 3 ----
execute: 22 C-->A ------Ciclo do intervalo 2----
execute: 24 B-->C------Ciclo do intervalo 3 ----
execute: 26 A-->B ------Ciclo do intervalo 2----
execute: 28 A-->C------Ciclo do intervalo 3 ----
execute: 30 B-->C ------Ciclo do intervalo 2----
execute: 32 A-->B------Ciclo do intervalo 6 ----
execute: 34 C-->A ------Ciclo do intervalo 2----
execute: 36 C-->B------Ciclo do intervalo 3 ----
execute: 38 A-->B------Ciclo do intervalo 2----
execute: 40 C-->A------Ciclo do intervalo 4 ----
execute: 42 B-->C------Ciclo do intervalo 2----
execute: 44 B-->A------Ciclo do intervalo 3 ----
execute: 46 C-->A------Ciclo do intervalo 2----
execute: 48 C-->B------Ciclo do intervalo 5 ----
execute: 50 A-->B------Ciclo do intervalo 2----
execute: 52 A-->C------Ciclo do intervalo 3 ----
execute: 54 B-->C------Ciclo do intervalo 2----
execute: 56 A-->B------Ciclo do intervalo 4 ----
execute: 58 C-->A------Ciclo do intervalo 2----
execute: 60 C-->B------Ciclo do intervalo 3 ----
execute: 62 A-->B------Ciclo do intervalo 2----
Para ficar ainda mais claro. Quando fazemos hanoi para seis discos, temos:
2 elevado a 1 = 2 temos o ciclo: AC|CB|BA para um array com 63 posições, que irá começar na posição 1. Esses ciclos irão ficar nas posições impares do vetor.
a cada um dois intervalos fazemos rodar o ciclo acima.
2 elevado a 2 = 4 temos o ciclo: AB|BC|CA para um array com 63 posições, que irá começar na posição 2. Esses ciclos irão ficar nas posições pares do vetor.
a cada quatro intervalos fazemos rodar o ciclo acima.
2 elevado a 3 = 8 temos o ciclo: AC|CB|BA para um array com 63 posições, que irá começar na posição 4. Esses ciclos irão ficar nas posições pares do vetor.
a cada um três intervalos fazemos rodar o ciclo acima.
2 elevado a 4 = 16 temos o ciclo: AB|BC|CA para um array com 63 posições, que irá começar na posição 8. Esses ciclos irão ficar nas posições pares do vetor.
a cada quatro intervalos fazemos rodar o ciclo acima.
2 elevado a 5 = 32 temos o ciclo: AC|CB|BA para um array com 63 posições, que irá começar na posição 16. Esses ciclos irão ficar nas posições pares do vetor.
a cada cinco intervalos fazemos rodar o ciclo acima.
2 elevado a 6 = 64 temos o ciclo: AB|BC|CA para um array com 63 posições, que irá começar na posição 32. Esses ciclos irão ficar nas posições pares do vetor.
a cada seis intervalos fazemos rodar o ciclo acima. (Apesar que esse último nunca irá aparecer)
Mais um detalhe, essa combinação vale para números de discos pares, quando for impar, tipo hanoi 3, deves inverter a lógicas dos ciclos.
Uma vez separados todos os ciclos é suficiente ordenar como fiz chamando o Collections.sort.
Abraços
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;
/*
* Algoritmo iterativo Hanoi
* @author FábioEm
*/
class Disco implements Comparable<Disco>{
Integer index;
String movimento;
Disco(int index,String movimento){
this.index=index;
this.movimento=movimento;
}
public int compareTo(Disco o) {
return index.compareTo(o.index);
}
}
public class HanoiIterativo {
private int qtDiscos;
private String sequenciaImpares[] = {"A-->C", "C-->B", "B-->A"};//para impares
private String sequenciaPares [] = {"A-->B", "B-->C", "C-->A"};//para pares
private List<Disco> arrayDiscos = new ArrayList<Disco>();
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 por favor!");
lerDados();
}
}
public void hanoi() {
int maxP=(int) Math.pow(2, qtDiscos);
int y = 1;
int pos =1;
while(y <= qtDiscos ){
int ctPulos = (int) Math.pow(2, y);
pos*=2;
if(y==1){
pos=1;
}
if(qtDiscos%2==0){
populaArrayPares(pos,ctPulos,maxP,y);
}else{
populaArrayImpares(pos,ctPulos,maxP,y);
}
y++;
}
}
private void populaArrayPares(int pos,int intervalos, int maxP,int y){
int index = 0;
if(y%2==0){
for (int i = pos; i <= maxP; i+=intervalos) {
Disco d = new Disco(i, sequenciaPares[index]);
arrayDiscos.add(d);
index++;
if(index>2){
index=0;
}
}
}else{
for (int i = pos; i < maxP; i+=intervalos) {
Disco d = new Disco(i, sequenciaImpares[index]);
arrayDiscos.add(d);
index++;
if(index>2){
index=0;
}
}
}
}
private void populaArrayImpares(int pos,int intervalos, int maxP,int y){
int index = 0;
if(y%2==0){
for (int i = pos; i < maxP; i+=intervalos) {
Disco d = new Disco(i, sequenciaImpares[index]);
arrayDiscos.add(d);
index++;
if(index>2){
index=0;
}
}
}else{
for (int i = pos; i <= maxP; i+=intervalos) {
Disco d = new Disco(i, sequenciaPares[index]);
arrayDiscos.add(d);
index++;
if(index>2){
index=0;
}
}
}
}
public static void main(String[] args) {
HanoiIterativo h = new HanoiIterativo();
h.lerDados();
h.hanoi();
Collections.sort(h.arrayDiscos);
for (Disco d : h.arrayDiscos) {
System.out.println("execute: "+d.index+" "+d.movimento);
}
}
}
Collections.sort(h.arrayDiscos);
C
Olá!
Encontrei um bom paper sobre soluções alternativas para o problema “Torres de Hanoi”, infelizmente está em inglês mas mesmo para quem não domina o idioma vai conseguir entender apenas analisando os códigos.
http://www.waset.org/journals/ijmcs/v7/v7-1-2.pdf
Abraços.
Criado 3 de julho de 2009
Ultima resposta 26 de jan. de 2012
Respostas 13
Participantes 8
Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.
Casa do Codigo Ontologias e Web Semantica: Do conceito a aplicacao Por Ivam Galvao Filho — Casa do Codigo