[Resolvido] algoritimo pra torre de hanoi

wagnermoliveira · Junho 11, 2009

Boa noite Galera

to com o segunte problema:

O professor da facul pediu pra desenvolvermos um algoritimo q resolva o probema das torres de anoi pra 5 discos usando estrutura de pilha , o problema consiste em mover os discos da torre A pra C usando a B como aux, sem que nenhum disco maior fique por cima de um menor, ae tem a historia completa Torre de hanoi - Wikipedia. Tive a ideia de fazer funçoes que mudem os discos e uma repete elas ate que o problema esteja resolvido. So que nao ta dando muito certo. Alguem tem uma outra ideia?

//Torre de Hanoi

//bibliotecas
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

// varialvel de valor continuo
#define max 4

//prototipo das funçoes
void move_discos(void);
void imprimi_torre(void);
void limpa_tela(void);
void mover_de_a_para_c(void);
void mover_de_a_para_b(void);
void mover_de_c_para_b(void);
void mover_de_b_para_a(void);
void resolver(void);
// vairiáveis globais( antes da função main())
	   int i;
	   int a[5]={5,4,3,2,1},n=4;
	   int b[5]={0,0,0,0,0},m=0;
	   int c[5]={0,0,0,0,0},o=0;
	   int movimentos=0;

//programa principal	   
main()
{
	  
	   
			   
						   
		  imprimi_torre();
		  mover_de_a_para_c();
		  mover_de_a_para_b();
		  mover_de_c_para_b();
		  mover_de_a_para_c();
		  mover_de_b_para_a();
		  
		  
	   
	   
	   getche();		   
}



void mover_de_a_para_c(void)// move destino - origem
{
	if(c[o]<a[n])
	{
				  //Operação de Push p/ pilha C
				  c[o]=a[n];
				  o++;
				  //Operação pop p/A
				  a[n]=0;
				  n--; 
	 movimentos++;							 
	 }
	 
	 imprimi_torre();
	 
}	 


void mover_de_a_para_b(void)
{
	if(b[m]<a[n])
	{
				  //Operação de Push p/ pilha B
				  b[m]=a[n];
				  m++;
				  //Operação pop p/A
				  a[n]=0;
				  n--; 
								  
	 movimentos++;
	 }
	 
	 imprimi_torre();
	
}  
void mover_de_c_para_b(void)
{
	
	if(b[m-1]>c[o-1])
	{
				  //Operação de Push p/ pilha B
				  b[m]=c[o-1];
				  m++;
				  //Operação pop p/C
				  o--;
				  c[o]=0; 
								  
	 movimentos++;
	 }
	 
	 imprimi_torre();
}  
void limpa_tela(void)
{
	 system("cls");
}	 
void imprimi_torre(void)
{
	 for(i=max;i>=0;i--)
	 
						 printf("%d %d %d\n", a[i], b[i], c[i]);
	 printf("A B C\n");
	 printf("-----\n");	 
	 printf("\n Movimentos: %d",movimentos);
}
void mover_de_b_para_a(void)// move aux - origem
{
	
	if(a[n]>b[m-1])
	{
				  //Operação de Push p/ pilha A
				  a[n+1]=b[m-1];
				  n++;
				  //Operação pop p/B
				  m--; 
				  b[m]=0;
								  
	 movimentos++;
	 }
	 
	 imprimi_torre();
	 
}	 
void resolver(void)
{
	 do
	 {
		  imprimi_torre();
		  mover_de_a_para_c();
		  mover_de_a_para_b();
		  mover_de_c_para_b();
		  mover_de_b_para_a();
				   
	 }while(o<=5);			  
}

euMesmo2 · Junho 11, 2009

Não entendi seu algoritmo, a biblioteca "conio.h" não e padrão e meu ambienter não a reconhece, alem disso, a função main devfe retornar um inteiro, mas a solução mais classica pode ser obtida do seguinte modo:

Voce sabe mover uma pedra ate seu destino.

Para mover 2 pedras, voce precisa mover uma pedra para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move a pedra da auxiliar para o destino.

Agora você sabe como mover 2 pedras.

Para mover 3 pedras, voce precisa mover 2 pedras para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move 2 pedras da auxiliar para o destino.

Agora você sabe como mover 3 pedras.

Para mover 4 pedras, voce precisa mover 3 pedras para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move 3 pedras da auxiliar para o destino.

Agora você sabe como mover 4 pedras.

E assim sucessivamente...

Com esse raciocinio, chegamos à função:

void resolve(origem, destino, auxiliar, numero)

{

if(numero==1)

{

move_para_(origem, destino);

}

else

{

resolve(origem, auxiliar, destino, numero-1);

move_para_(origem, destino);

resolve(auxiliar, destino, origem, numero-1);

}

O problema e q essa e muito classica e nao sei se seu professor vai aceita-la, mas pode servir de base.

Qualquer coisa, to as ordens, t+

wagnermoliveira · Junho 13, 2009

Não entendi seu algoritmo, a biblioteca "conio.h" não e padrão e meu ambienter não a reconhece, alem disso, a função main devfe retornar um inteiro, mas a solução mais classica pode ser obtida do seguinte modo:

Voce sabe mover uma pedra ate seu destino.

Para mover 2 pedras, voce precisa mover uma pedra para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move a pedra da auxiliar para o destino.

Agora você sabe como mover 2 pedras.

Para mover 3 pedras, voce precisa mover 2 pedras para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move 2 pedras da auxiliar para o destino.

Agora você sabe como mover 3 pedras.

Para mover 4 pedras, voce precisa mover 3 pedras para a auxiliar ,depois mover a pedra que sobrou para o destino e ai, move 3 pedras da auxiliar para o destino.

Agora você sabe como mover 4 pedras.

E assim sucessivamente...

Com esse raciocinio, chegamos à função:

void resolve(origem, destino, auxiliar, numero)

{

if(numero==1)

{

move_para_(origem, destino);

}

else

{

resolve(origem, auxiliar, destino, numero-1);

move_para_(origem, destino);

resolve(auxiliar, destino, origem, numero-1);

}

}

O problema e q essa e muito classica e nao sei se seu professor vai aceita-la, mas pode servir de base.

Qualquer coisa, to as ordens, t+

Cara, valeu pela dica, a gente usa o Dev C++ pra compilar esse codigo, copila certim.

esse exempo q você cito tem um cogio aki Torre de hanoi recursiva. Não estamos conseguindo ver outro jeito de resolver se nao com esse, mas o professor não explico pra gente como funciona função recursiva, você pode explicar ?

quitZAUMMM · Junho 13, 2009

Função recursiva faz chamada a ela mesma.

Algo de empilhar e desempilhar.

[]s

euMesmo2 · Junho 13, 2009

Cara, valeu pela dica, a gente usa o Dev C++ pra compilar esse codigo, copila certim.

esse exempo q você cito tem um cogio aki Torre de hanoi recursiva. Não estamos conseguindo ver outro jeito de resolver se nao com esse, mas o professor não explico pra gente como funciona função recursiva, você pode explicar ?

Para contornar as chamadas recursivas, você pode criar as funções move5, move4, move3, move2 e move1, equivalentes à função resolve acima, mas seria uma perda de tempo pq o efeito e o mesmo, so q menos otimizado.

No caso acima, move5 chama move4 que chama move3...

wagnermoliveira · Junho 14, 2009

Cara, valeu pela dica, a gente usa o Dev C++ pra compilar esse codigo, copila certim.

esse exempo q você cito tem um cogio aki Torre de hanoi recursiva. Não estamos conseguindo ver outro jeito de resolver se nao com esse, mas o professor não explico pra gente como funciona função recursiva, você pode explicar ?

Para contornar as chamadas recursivas, você pode criar as funções move5, move4, move3, move2 e move1, equivalentes à função resolve acima, mas seria uma perda de tempo pq o efeito e o mesmo, so q menos otimizado.

No caso acima, move5 chama move4 que chama move3...

Hum legal sua ideia , o professor quer que a gente tente uma solução interativa e nao recursiva, axo q essa sua ideia daria certo, mas tem como você dar um exemplo de como seria o codigo dessa funções move1 a move[n], nao consegui entender muito bem. Abraço

euMesmo2 · Junho 16, 2009

Hum legal sua ideia , o professor quer que a gente tente uma solução interativa e nao recursiva, axo q essa sua ideia daria certo, mas tem como você dar um exemplo de como seria o codigo dessa funções move1 a move[n], nao consegui entender muito bem. Abraço

.
   .
   .
void move1(int origem, int destino)
{
//faça aki a função para trocar a pedra do topo da torre de origem para a torre de destino.
}
void move2(int origem, int destino, int auxiliar)
{
   move1(origem, auxiliar, destino);
   move1(origem, destino);
   move1(auxiliar, destino, origem);
}
void move3(int origem, int destino, int auxiliar)
{
   move2(origem, auxiliar, destino);
   move1(origem, destino);
   move2(auxiliar, destino, origem);
}
void move4(int origem, int destino, int auxiliar)
{
   move3(origem, auxiliar, destino);
   move1(origem, destino);
   move3(auxiliar, destino, origem);
}
void move5(int origem, int destino, int auxiliar)
{
   move4(origem, auxiliar, destino);
   move1(origem, destino);
   move4(auxiliar, destino, origem);
}
int main()
{
   move5(1,3,2);
}

Para 5 pedras.

Não sei se esse funciona. fiz meio corrido.

Desculpa a demora, flw.

wagnermoliveira · Junho 19, 2009

Valeu pela ajuda galera, mas não teve jeito, tivemos que ficar com a soluão recursiva, o professor gosto bastante do nosso trabalho, vou postar nosso codigo, talvez ajude mais alguem.

/*
.
.
		TORRES DE HANOI
.
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h>

#define N 5	//Numero de discos
int movimentos=0;
int A[N], B[N], C[N];  /* Estes são os três torres. Por exemplo, se o
estado de A é 0,1,3,4, o que significa que existem três discos em um dos tamanhos
1, 3 e 4. (Pense em direito como sendo o "baixo" direcção.) */

void Hanoi(int,int*,int*,int*); 
void limpa_tela(void)		   
{
	 system("cls");
}	 
void pausa(void)
{
	  int tempo = GetTickCount();
	while(tempo + 4000 > GetTickCount())
	// nota, tempo + 10000 poderia estar fora do loop, para economizar tempo...
	// mas como a gente não quer economizar, e sim gastar ele, acho que
	// não faz diferença =)
	{
		bool faz_nada = true;
	}
} 
/* Imprimir a configuração atual de A, B e C para a tela */

void
imprimetorre(void)
{
	int i;

	limpa_tela();
	printf("\n\n\n\n");
	for(i=0;i<N;i++)printf("\t\t\t   ( %d )  ( %d )	( %d ) \n",A[i],B[i],C[i]);
	printf("\t\t\t ___  _____  _______  ___\n");
	printf("\t\t\t|						|\n");
	printf("\t\t\t|	A	  B		C   |\n");
	printf("\t\t\t|________________________|\n");
	printf("Movimentos %d",movimentos);
	pausa();
	movimentos++;
	return;
}
	
/* Mova o elemento não zero à esquerda da fonte para dest, deixar 0. */
/* Retorna o valor transferido (não utilizado). */

int Mover(int *origem, int *destino)
{
	int i=0,j=0;

	while((*(origem + i)==0)&&(i<N))i++; //o ponteiro apontará para o proximo valor armazenado na memória, 
	while((*(destino + j)==0)&&(j<N))j++;


	*(destino+j-1) = *(origem+i);
	*(origem + i) = 0;
	imprimetorre();	   	/* Imprimir configuração após cada jogada. */
	return *(destino+j-1);
}


/* Move primeiros n números não zero a partir do código fonte para dest utilizando as regras de Hanói.
	Solicita própria recursivamente.
*/

void
Hanoi(int n,int *origem, int *destino, int *aux) //recebendo valores,  partir de agora
												 //o ponteiro estará apontando para A[0], B[0], C[0] 
{
	int i;
	if(n==1){
		Mover(origem,destino);
		return;
	}

	Hanoi(n-1,origem,aux,destino);
	Mover(origem,destino);
	Hanoi(n-1,aux,destino,origem);	
	return;
}


int
main()
{
	int i,x;

	do{				 printf("				   Univerdade do Estado de Matro\n");
						printf("				Campus Universitario de Alto Araguaia\n");
						printf("			Estrutura de Dados e Tecnicas de Programacao\n");
						printf("Docente: Prof. Max Robert Marinho\n");
						printf("Discentes: Marcos Vinicios Campos Linhares\n");
						printf("		   Risiane Margarete Vieira Barroso\n");
						printf("		   Roni Pess\n");
						printf("		   Wagner Moraes Oliveira\n\n");
		
						printf("					  /////////////////////////\n");
						printf("					 /					   /\n");
						printf("					/	TORRES DE HANOI	/\n");
						printf("				   /					   /\n");
						printf("				  /////////////////////////\n\n");
						printf("1. Conheca a Historia;\n");
						printf("2. Ver a solucao do problema para 5 Entradas;\n");
						printf("3. Sair;\n\n");
						printf("Digite sua opcao:");
						scanf("%d",&x);
						switch (x) 
						{
							   case 1 :
										   limpa_tela();
										   printf("							   TORRES DE HANOI \n\n\n");
										   printf("							 _	  _		_\n");
										   printf("							(1)	| |	  | |\n");
										   printf("							| |	| |	  | |\n");
										   printf("						   (_2_)   | |	  | |\n");
										   printf("						   _|_|_   | |	  | |\n");
										   printf("						 _(__3__)__|_|______|_|_\n");
										   printf("						|					   |\n");
										   printf("						|	A	  B		C  |\n");
										   printf("						|_______________________|\n");
										   printf("\n\n	 A Torre de Hanoi e um quebra-cabeca que consiste em uma base contendo tres pinos, em um dos quais sao dispostos alguns discos uns sobre os outros, em ordem crescente de diametro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situacao.\n");
										   printf("	 Existem varias lendas a respeito da origem do jogo, a mais conhecida diz respeito a um templo Hindu, situado no centro do universo. Diz-se que Brahma supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre uma plataforma. Brahma ordenara-lhes que movessem todos os discos de uma estaca para outra segundo as suas instrucoes. As regras eram simples: apenas um disco poderia ser movido por vez e nunca um disco maior deveria ficar por cima de um disco menor. Segundo a lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o templo desmoronar-se-ia e o mundo desapareceria.\n");
										   printf("	 E interessante observar que o numero minimo de ""movimentos"" para conseguir transferir todos os discos da primeira estaca a terceira é (2 elevado n)-1, sendo n o numero de discos.\n\n");
										   printf("	 Logo,para solucionar um Hanoi de:\n\n"); 
										   printf("3 discos, sao necessarios: (2 elevado a n -1) = 7 movimentos\n");
										   printf("5 discos, sao necessarios: (2 elevado a n -1) = 31 movimentos\n");
										   printf("64 discos, sao necessarios: (2 elevado a n -1) = 18.446.744.073.709.551.615 movimentos\n\n");
										   printf("						   fonte: http://pt.wikipedia.org/wiki/Torre_de_Hanoi\n\n");				  
										   system("pause");
										   limpa_tela();
							   break;
							   case 2 :
										   	/* Inicializar o torres */
											for(i=0;i<N;i++)A[i]=i+1;
											for(i=0;i<N;i++)B[i]=0;
											for(i=0;i<N;i++)C[i]=0;
											movimentos=0;
										 
											printf("Solucao para o problema das Torres de Hanoi com %d Discos\n\n",N);

											/* Imprimir a partida estado */
											imprimetorre();
											printf("\n\t\t\t	 Torre Inicial\n\n");
											printf("\n\n Para comecar a solucao do problema,\n");
											system("pause");
											/* Faça isso! Use A = Origem, Destino = C, B = Auxiliar */
											Hanoi(N,A,C,B);
											printf("\n\n\nProblema resolvido....\n");
											system("pause");
											limpa_tela(); 
							   break;
							   case 3 : break;
							   default: printf("OPCAO INVALIDA!!!\a\n");
										getche();
										limpa_tela();
	
						}
		  }while(x!=3);

return 0;
	
}

Arquivado

[Resolvido] algoritimo pra torre de hanoi

Recommended Posts

wagnermoliveira 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

euMesmo2 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

wagnermoliveira 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

quitZAUMMM 18

Compartilhar este post

Link para o post

Compartilhar em outros sites

euMesmo2 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

wagnermoliveira 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

euMesmo2 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

wagnermoliveira 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

Fixar div até atingir uma certa altura

Ajuda com Extends e envio para o banco

PHP+Codeginiter - Orientação para Impressão

Fóruns

Tempo Real

Informação importante