Aplicacao de um algoritmo de backtracking

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1603 palavras )
  • Download(s) : 0
  • Publicado : 28 de novembro de 2011
Ler documento completo
Amostra do texto
UNIVERSIDADE FEDERAL DE ITAJUBÁ CAMPUS ITABIRA

Disciplina: Complexidade de Algoritmos – ECO014

Trabalho prático 1

Alunos: Daniel Luis M. Timponi Diego Cordeiro Brioshi

RA: 16607 RA: 16.609

Professor: Rafael Francisco dos Santos

Itabira, 7 de maio de 2010

Sumário

1

DESCRIÇÃO DAS CLASSES................................................................................. 32

TENTATIVAS BEM SUCEDIDAS ........................................................................ 5

3

TENTATIVAS MAL SUCEDIDAS ........................................................................ 6

4

RESULTADOS E ANÁLISE DOS RESULTADOS ............................................... 7

1 DESCRIÇÃO DAS CLASSES
public class Projeto3
Variáveis Random random =new Random();//Variável randômica int matriz[][]; //matriz equivalente ao centro de BH int vet_pos[], // vetor que armazena o percurso do Jorge vet[]; //vetor que armazena o numero de vezes que cada esquina é visitada int e=0; //numero de quarteirões percorridos int topo; //auxiliar do vet_pos (vetor de percurso) int k=9; //auxiliar na impressão Métodos public Projeto3() Construtor da classe. Inicia osatributos declarados Pré-define a posição inicial do Jorge e a posição da casa do Jorge e do James Espalha randomicamente os bandidos public boolean movimento(int x , int y) Controla o percurso do Jorge evitando caminhos em direção a esquinas ocupadas por bandidos, esquinas já visitadas e mantendo o Jorge dentro dos limites do centro de BH eliminando o erro array out of bounds exception. public booleanmovimento2(int x, int y) Controla o caminho reverso do Jorge evitando o cruzamento com ladrões public boolean sucesso(int x, int y) Função booleana referente a posição de tentativa de fuga bem sucedida public boolean Fuga(int x, int y) Função recursiva que executa o percurso do Jorge no centro de BH Pré-define os movimentos (um quarteirão acima ,ou abaixo, ou a direita, ou a esquerda) public voidimprime() • Imprime matriz equivalente ao centro de BH 5 – esquina visitada 1 – Ladrão 3- Casa do Jorge e do James • Imprime o percurso do Jorge (as esquinas são numeradas de 1 a 100 horizontalmente)
3



Imprime as esquinas visitadas (1 visitada, 0 não visitada)

public class Main
Variáveis int k=9; // auxiliar na impressao int sucesso=0; //contador rentativas bem sucedidas intnquarteiroes=0; ///Contador de quarteiroes nas tentativas bem sucedidas double esquinas_visitadas []=new double [100]; //contador de cada esquina visitada DecimalFormat df = new DecimalFormat("000.00000"); //formatacao de saida Projeto3[] r =new Projeto3[1000]; // array do tipo Projeto3 (array de objetos) Metodo chave for ( int i=0; i < 1000; i++ ){ ... } Alocaçao de de um array de tamanho 1000 do tipoProjeto3 Verificacao de tentativa de fuga bem sucedida Armazena tentativas bem sucedidas acumulada Armazena o numero de quarteirões percorridos nas tentativas bem sucedidas acumulados Armazena esquinas visitadas acumuladas Obs.: Na parte de visualização são feitos cálculos para se obter os dados estatísticos requeridos. Número de fugas com sucesso - tentativas bem sucedidas acumulada Número médio dequarteirões visitados - nº quarteirões tentativas bem sucedidas acumulada

Porcentagem média das esquinas visitadas –

4

2 TENTATIVAS BEM SUCEDIDAS
1º Tentativa
Matriz equivalente ao centro de BH 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 5 1 1 1 0 1 0 1 1 0 5 5 5 5 1 0 1 1 1 1 0 0 1 5 5 5 5 1 0 1 0 0 0 0 1 5 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 3 0 0 0 1 0 1 1 0 0 0 10 0 1

2º Tentativa
Matriz equivalente ao centro de BH 0 1 0 0 0 1 5 5 5 5 0 0 0 1 1 1 5 1 1 5 1 0 1 5 5 5 5 5 5 5 0 1 0 0 0 1 5 1 1 5 0 0 1 0 5 5 5 1 0 1 0 0 0 0 5 1 5 1 3 1 1 0 0 0 5 5 1 1 1 1 1 0 1 0 0 5 1 1 1 1 0 1 0 1 1 5 1 1 0 1 0 1 0 1 0 0 1 0 0 1

vetor do percurso(11) 23 33 34 44 54 64 65 75 85 86 95

vetor do percurso( 25) 23 33 43 53 63 64 65 55 45 46 47 57 58 59 66 73 83 93 92...
tracking img