Algoritmos de Tentativa e Erro

Prévia do material em texto

Algoritmos de Tentativa e Erro 
Prof. Wladimir Araújo Tavares 
A recursividade pode ser usada para resolver problemas cuja solução é tentar todas as alternativas possíveis. A 
idéia para algoritmos tentativa e erro é decompor o problema em um número finitos de sub-tarefas parciais que 
devem ser exploradas exaustivamente. Isso significa que devemos testar todas as possibilidades de resultados 
em um problema à fim de descobrir qual o melhor resultado para esse. Costumam ser algoritmos com uma 
implementação simples, porém com uma complexidade geralmente elevada. 
Exemplo: Passeio de um cavalo no tabuleiro de xadrez 
Dado um tabuleiro com n x n posições, o cavalo movimenta-se segundo as regras do xadrez. 
 
A partir da posição inicial (x0,y0), o problema consiste em encontrar, se existir, um passeio do valo com n
2 – 1 
movimentos, tal que todos os pontos do tabuleiro são visitados uma única vez. Um caminho para resolver o 
problema é considerar a possibilidade de realizar o próximo movimento ou verificar que ele não é possível. 
Algoritmo Básico 
 
Um exemplo de uma solução para o problema do passeio de um cavalo para o tabuleiro 8x8. 
 
#include <stdio.h> 
int t[8][8],a[8],b[8]; 
void imprime(){ 
 int i,j; 
 for(i=0;i<8;i++){ for(j=0;j<8;j++){printf("%3d",t[i][j]);} printf("\n");} 
} 
int cavalo(int i, int x, int y){ 
 int u,v,k,q; 
 if(i==64){ imprime(); return 1;} 
 //executa movimentos 
 for(k=0;k<8;k++){ 
 u = x + a[k]; v = y + b[k]; 
 //testa limites do tabuleiro 
 if( (u>=0 && u<=7) && (v>=0 && v<=7)){ 
 if(t[u][v]==0){ 
 t[u][v]=i; 
 q = cavalo(i+1,u,v); 
 if(q==0) t[u][v]=0; else return 1; 
 } 
 } 
 } 
 return 0; 
} 
int main(){ 
 //inicialização dos deslocamentos dos movimentos 
 a[0]=2;a[1]=1;a[2]=-1;a[3]=-2; 
 b[0]=1;b[1]=2;b[2]=2;b[3]=1; 
 
 a[4]=-2;a[5]=-1;a[6]=1;a[7]=2; 
 b[4]=-1;b[5]=-2;b[6]=-2;b[7]=-1; 
 memset(t,0,sizeof(t)); 
 cont =1; 
 t[0][0]=1; 
 cavalo(2,0,0); 
 system("PAUSE"); 
} 
 
 
http://www.spoj.pl/problems/STABLEMP/