PasseioDoCavalo (1)

Prévia do material em texto

PASSEIO DO CAVALO 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ana Izabel Rezende 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PROBLEMA 
 
Escreva um algoritmo, e o respectivo programa em Java, que faça a simulação do movimento 
do cavalo no tabuleiro de Xadrez. Para isso o programa deverá 
 sortear a casa inicial e marcá-la com o número 1. Em seguida deverá escolher 
 uma das casas disponíveis para ocupação e marcá-la com o próximo número 
 que corresponda à seqüência da jogada. A partir desta nova posição o cavalo 
 deverá fazer novo movimento e assim sucessivamente até percorrer todas as 
 casas do tabuleiro, ou atingir uma casa a partir da qual ele não possa mais 
 avançar. O cavalo não pode ocupar uma casa já visitada. 
 O programa deverá imprimir a matriz que representa o tabuleiro após a 
 simulação, o número total de casas visitadas e o tempo que o programa levou 
 para realizar a simulação. Deverão ser apresentadas pelo menos cinco 
 tentativas para se avaliar se a posição inicial influencia o número de tentativas 
 e o tempo de simulação. 
 
 
 
 
 
 
 
SOLUÇÃO 
A solução deste problema, consiste e em uma classe, para o controle das iterações do cavalo, 
entrada de dados, controle do tempo e geração dos números aleatórios. Que será apresentada 
posteriormente. 
A recursividade foi a técnica utilizada para encontrar a sequência de movimentos, usada 
como tentativa e erro, tentando a combinação de todos os possíveis movimentos 
 
 
CLASSE 
Classe Tabuleiro 
A classe tabuleiro possui uma matriz bidimensional de inteiros para armazenar 
 os valores do tabuleiro, que podem variar de 0 a 64, sendo que zero é uma casa que ainda não 
foi visitada, e se for diferente de 0 a casa já foi visitada na iteração x preenchida na posição. 
A união das matrizes de inteiros movimentoX[] movimentoY[] , armazenam todos os 9 
possíveis movimentos do cavalo. 
 Foi utilizado também as variáveis estáticas e longas limite e iterações, para controlar a 
recursividade também pelo número de iterações e não só pelo número de movimentos, sendo 
que nem sempre, em todas as posições de partida do cavalo é possivel os 64 movimentos caindo 
em um loop infinito, um tabuleiro de xadrez utilizando carácteres especiais e os valores da 
matriz que representa os valores do tabuleiro utilizando do laço for. 
 O método público valida(int contador, int x , int y) , recebe como parâmetro um inteiro 
(contador), a posição x, e a posição y do cavalo, e é chamado recursivamente até que o contador 
seja igual a 65, ou que a quantidade de iterações seja igual a 1000000000. Este método utiliza 
um for para testar todos os possíveis movimentos do cavalo (armazenados em movimentoX[] 
movimentoY[] ) adicionado de x e de y (variáveis de entrada do método) , e atribuí a u e v , 
caso este movimento esteja dentro do tabuleiro, e que a nova casa não tenha sido ocupada 
anteriormente ele atribui ao tabuleiro [posição u][posição v] o valor do contador. É criado um 
teste de validade do método valida (contador +1, a posição x que será testada [no caso u] , a 
posição y que será testada[no caso v ]). Caso o retorno seja verdadeiro, existem novos 
candidatos a movimento e o método é chamado em uma nova execução, caso 
 não ele atribui a posição interação anterior o valor 0 ao tabuleiro e tenta a verificação dos 
movimentos posteriores ao tentando anteriormente. A cada iteração executada, a variável 
iterações e acrescida de 1. 
E um metodo (Main), que controla o tempo de execução, utilizamos o método estático da 
classe System currentTimeMillis() (System.currentTimeMillis()), que retorna o tempo em 
milissegundos(Obtido do sistema) no momento em que a classe é instanciada, e utilizei no 
final da classe o mesmo método, para fazermos a diferença entre os valores dando como 
resultado o tempo de execução em milissegundos. Este valor é impresso na tela. 
Foi criada uma instância da classe Random(java.util.Random). O método utilizado foi o 
random.nextInt() que recebe como parâmetro um inteiro, que no nosso caso foi o número 7, 
que retorna valores aleatórios compreendidos de 0 e o inteiro utilizado, que no nosso caso foi 
o 7. Os valores gerados por esse método estão compreendidos entre 0 e 7, ou seja: 
{0,1,2,3,4,5,6,7}. Este método foi utilizado duas vezes e armazenado em duas variáveis 
(numero1 e numero2), para criar a posição inicial de nosso cavalo de forma aleatória. 
 Foi utilizado o Método println() da Classe System (System.out.println()) que recebe como 
parâmetro uma string para imprimirmos a posição inicial do cavalo. 
 Foi chamado o método valida () que recebe como parâmetro o número do contador, que no 
nosso caso, vai ser o 1 por ser a primeira iteração do cavalo, a posição x e a posição y. E no 
final da execução da classe é impresso o tabuleiro depois de todas as iterações possíveis, 
utilizando o método imprimeTabuleiro(). 
 
 
 
 
CODIFICAÇÃO 
 
package br.com.xadrez.entidades; 
import java.util.Random; 
public class Tabuleiro { 
 static long iteracoes=0L;static long limite = 1000000000L; 
 private int tabuleiro[][] = new int[8][8]; 
 private int movimentosX[] = {0, 2, 1, -1, -2, -2, -1, 1, 2 }; 
 private int movimentosY[] = {0, 1, 2, 2, 1, -1, -2, -2, -1 }; 
 
 public Tabuleiro() { 
 for (int i = 0; i < 8; i++) { 
 for (int j = 0; j < 8; j++) { 
 tabuleiro[i][j] = 0; 
 } 
 } 
 } 
 public void imprimeTabuleiro() { 
 for (int i = 0; i < 8; i++) { 
 System.out.println("\n+---------+---------+--------+---------+---------+---------+---------+-
--------+"); 
 for (int j = 0; j < 8; j++) { 
 if (tabuleiro[i][j] < 10) { 
 System.out.print("|----" +tabuleiro[i][j] + "----"); 
 } else { 
 System.out.print("|---" + tabuleiro[i][j] + "----"); 
 } 
 } 
 System.out.print("|"); 
 } 
 System.out.println("\n+---------+---------+---------+--------+---------+---------+---------+----
-----+"); 
 } 
 public boolean valida(int contador, int x, int y) { 
 int u, v; 
 iteracoes++; 
 if ((contador == 65) || iteracoes > limite) { 
 if(contador == 65) { 
 System.out.println("\nTodos os 64 movimentosforam encontrados!\n"); 
 }else{ 
 System.out.println("\nNão foi possível encontrar todos os 65 movimentos em 
1.000.000.000L de iterações\n"); 
 System.out.println("\nEncontrado: " + contador + " movimentos \n"); 
 } 
 return true; 
 } 
 for (int k = 0; k < 9; k++) { 
 u = x + movimentosX[k]; 
 v = y + movimentosY[k]; 
 if ((u >= 0 && u < 8) && (v >= 0 && v < 8) &&tabuleiro[u][v] == 0) { 
 tabuleiro[u][v] = contador; 
 if (!valida(contador+1,u,v)) 
 tabuleiro[u][v] = 0; 
 else return true; 
 } 
 } 
 return false; 
 } 
 public static void main(String[] args) { 
 long tempoInicio = System.currentTimeMillis(); 
 Random random = new Random(); 
 Tabuleiro tabuleiro = new Tabuleiro(); 
 int numero1 , numero2 ; 
 numero1= random.nextInt(7); 
 numero2= random.nextInt(7); 
 System.out.println("\nPosição inicial do cavalo: [ "+ numero1 +" , "+ numero2 + " ]\n"); 
 tabuleiro.valida(1, numero1, numero2); 
 tabuleiro.imprimeTabuleiro();System.out.println(""); 
 System.out.println("Tempo Total de execução: "+ (System.currentTimeMillis() - 
tempoInicio) +" Milisegundos"); 
 } 
 
} 
 
 
 
 
 
 
 
 
 
SIMULAÇÕES 
 Simulação 1 
 Posição inicial do cavalo: [ 0 , 0 ] 
 Todos os 64 movimentos foram encontrados. 
Tempo Total de execução: 954 Milissegundos 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----1----|---60----|---39----|---34----|---31----|---18----|----9----|---64----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---38----|---35----|---32----|---61----|---10----|---63----|---30----|---17----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---59----|----2----|---37----|---40----|---33----|---28----|---19----|----8----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---36----|---49----|---42----|---27----|---62----|---11----|---16----|---29----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---43----|---58----|----3----|---50----|---41----|---24----|----7----|---20----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---48----|---51----|---46----|---55----|---26----|---21----|---12----|---15----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+|---57----|---44----|---
53----|----4----|---23----|---14----|---25----|----6----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---52----|---47----|---56----|---45----|---54----|----5----|---22----|---13----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 Simulação 2 
 Posição inicial do cavalo: [ 4 , 2 ] 
 Todos os 64 movimentos foram encontrados! 
 Tempo Total de execução: 12348 Milissegundos 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---31----|---34----|---59----|---46----|---29----|---16----|----7----|---64----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---60----|---45----|---30----|---33----|----8----|---63----|---28----|---15----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---35----|---32----|---61----|---58----|---47----|---26----|---17----|----6----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---44----|---49----|---56----|---25----|---62----|----9----|---14----|---27----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---55----|---36----|----1----|---48----|---57----|---22----|----5----|---18----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---50----|---43----|---52----|---39----|---24----|---19----|---10----|---13----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---37----|---54----|---41----|----2----|---21----|---12----|---23----|----4----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+|---42----|---51----|---
38----|---53----|---40----|----3----|---20----|---11----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 Simulação 3 
 Posição inicial do cavalo: [ 4 , 5 ] 
 Todos os 64 movimentos foram encontrados! 
 Tempo Total de execução: 1417 Milissegundos 
+---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---54----|---49----|---26----|---61----|---14----|---63----|---24----|----5----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---45----|---60----|---53----|---48----|---25----|----6----|---13----|---64----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---50----|---55----|---46----|---27----|---62----|---15----|----4----|---23----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---59----|---44----|---29----|---52----|---47----|---22----|----7----|---12----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---56----|---51----|---58----|---21----|---28----|----1----|---16----|----3----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---43----|---34----|---37----|---30----|---39----|---18----|---11----|----8----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---36----|---57----|---32----|---41----|---20----|----9----|----2----|---17----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---33----|---42----|---35----|---38----|---31----|---40----|---19----|---10----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 Simulação 4 
 Posição inicial do cavalo: [ 1 , 1 ] 
 Não foi possível encontrar todos os 65 movimentos em 1.000.000.000L de iterações 
 Encontrado: 49 movimentos 
 Tempo Total de execução: 113175 Milissegundos 
+---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---33----|----0----|---27----|----0----|---15----|----0----|----0----|----8----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---28----|----1----|---32----|----0----|---36----|----9----|---14----|----0----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----0----|---34----|---45----|---26----|---31----|---16----|----7----|----0----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---44----|---29----|----2----|---35----|----0----|---37----|---10----|---13----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---41----|---46----|---43----|---30----|---25----|---12----|---17----|----6----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----0----|----0----|---40----|----3----|---38----|---19----|---22----|---11----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----0----|---42----|---47----|----0----|---21----|---24----|----5----|---18----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---48----|----0----|----0----|---39----|----4----|----0----|---20----|---23----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 Simulação 5 
 Posição inicial do cavalo: [5 , 0 ] 
 Não foi possível encontrar todos os 65 movimentos em 1.000.000.000L de iterações 
 Encontrado: 55 movimentos. 
Tempo Total de execução: 112249 Milissegundos 
+---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---42----|---49----|----0----|---33----|---30----|---17----|----8----|----0----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----0----|----0----|---41----|---48----|----9----|---32----|---29----|---16----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---50----|---43----|---34----|---31----|----0----|---27----|---18----|----7----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---35----|---40----|----0----|---26----|---47----|---10----|---15----|---28----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---44----|---51----|---46----|---39----|----0----|---23----|----6----|---19----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |----1----|---36----|----0----|---54----|---25----|---20----|---11----|---14----|+---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---52----|---45----|---38----|----3----|---22----|---13----|---24----|----5----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 |---37----|----2----|---53----|----0----|----0----|----4----|---21----|---12----| 
 +---------+---------+---------+---------+---------+---------+---------+---------+ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CONCLUSÃO 
 
Com os resultados obtidos, conseguimos concluir que determinadas posições iniciais, a 
solução, utilizando o método implantado é impossível. Também é possível concluir que a 
posição inicial é um fator fundamental para a redução ou aumento do tempo de execução do 
código. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Parte 2 – Pesquisa 
Coesão: Coesão mede a intensidade da associação funcional dos elementos de um módulo. 
Deseja-se módulos altamente coesos, cujos elementos são relacionados um com os outros. 
 Porém, os elementos de um módulo não devem ser fortemente relacionados com os 
elementos de outros módulos, pois isto levaria a um forte acoplamento entre eles. 
A melhor forma de minimizar o acoplamento é ter certeza que todos os módulos possuem boa 
coesão. 
 
Coesão Funcional 
É apresentada em um módulo quando suas funções internas contribuem para exeução de uma 
e apenas uma tarefa relacionada ao problema. 
 
Coesão Sequencial 
É apresentada quando funções internas estão envolvidas em atividades de tal maneira, que os 
dados de saída de uma atividade sirvam como dados de entrada para a próxima. Este fluxo 
estabelece uma sequência de execução das funções, porém, não deve caracterizar o conjunto 
delas como uma única tarefa. 
Um módulo com Coesão Sequencial é caracterizado de fácil manutenção, porém, de baixa 
reutilização, pois possui atividades que são utilizadas juntas. 
 
Coesão Procedural 
 
Quando as funções internas de um módulo executam atividades diferentes e não 
correlacionadas, exceto por serem executadas em uma mesma ordem, nas quais o controle 
flui (e não os dados) de uma atividade para outra. É comum em um módulo com Coesão 
Procedural que os dados de entrada e saída tenham pouca relação, e também que tais módulos 
devolvam resultados parciais, tais como: flags, chaves. 
Coesão Temporal 
 
Quando as funções internas de um módulo executam atividades que estão relacionadas 
apenas com o tempo (as atividades não estão relacionadas entre si). A ordem de execução de 
atividades é mais importante em módulos procedurais do que em módulos temporais. 
Coesão Lógica 
 
Quando as funções internas de um módulo contribuem para atividades da mesma categoria 
geral, onde a atividade é selecionada fora do módulo. Assim, módulos logicamente coesos 
apresentam uma interface descaracterizada. 
 
 
Acoplamento: Mede o grau de interdependência entre os módulos do diagrama. O que se 
deseja são módulos de baixo acoplamento para diminuir o máximo possível o efeito em 
cadeia quando um módulo for alterado. 
 
Acoplamento de dados 
 
Corresponde à comunicação de dados necessária entre módulos. Uma vez que os módulos têm 
que se comunicar, a ligação de dados é inevitável, e não é crítica desde que mantidas as taxas 
mínimas. Deve-se tomar cuidado com o chamado dado migrante (um grupo de informações 
que vaga pelo sistema), indesejável e sem sentido para a maioria dos módulos pelos quais passa. 
Acoplamento de controle 
Dois módulos são acoplados por controle se um passa um grupo de dados (controle) para o 
outro para controlar sua lógica interna. No primeiro exemplo, o acoplamento não é tão crítico 
uma vez que o controle indica uma validação, porém o segundo exemplo exige que o módulo 
que enviou o controle (validar pedido) conheça o outro módulo. 
 
Acoplamento comum 
 
Dois módulos possuem acoplamento comum quando fazem referência a uma área global de 
dados (ex. Working Storage Section da linguagem Cobol). Este tipo de acoplamento não é 
desejável pois: 
- um erro em uma área global pode se propagar por diversos módulos; 
- programas com muitos dados globais são de difícil entendimento; 
- fica difícil descobrir que módulos devem ser alterados quando um dado é modificado. 
 
Acoplamento de conteúdo 
 
Dois módulos apresentam acoplamento de conteúdo (ou patológico) se um faz referência ou 
desvia a sequência de instruções para o interior de um outro módulo (GO TO). Tal acoplamento 
torna o conceito de caixas-pretas sem sentido. 
Acoplamento de carimbo 
Dois módulos apresentam acoplamento de carimbo se uma estrutura de dados for passada na 
forma de um argumento, porém, o módulo é chamado a operar somente sobre alguns dos 
componentes individuais dessa estrutura de dados. 
 
	Acoplamento: Mede o grau de interdependência entre os módulos do diagrama. O que se deseja são módulos de baixo acoplamento para diminuir o máximo possível o efeito em cadeia quando um módulo for alterado.