TP AEDS 3

1196 palavras 5 páginas
Trabalho prático 2 – Número de caminhos
Departamento de Ciência da Computação – Universidade Federal de Minas Gerais
(UFMG)
Algoritmos e Estruturas de Dados III – 2014 / 2 vini22004@gmail.com 1. INTRODUÇÃO
O objetivo deste trabalho é descobrir o número de caminhos mais curtos partindo de um ponto A até um ponto B. Esses caminhos podem ser ilustrados como as ruas e avenidas de uma cidade, as ruas serão sempre horizontais e as avenidas verticais. Um detalhe importante é que algumas esquinas entre ruas e avenidas estarão fechadas. O ponto A sempre estará na primeira rua e avenida e poderá haver mais de um ponto B, sendo necessário calcular o número de caminhos mais curtos para cada ponto B.
Os dados que irão representar a cidade serão passados através de um arquivo de entrada. Assim sendo este arquivo conterá as dimensões da cidade, as esquinas bloqueadas, e os pontos B.

2. SOLUÇÃO PROPOSTA
A solução proposta para resolver este problema é construir uma estrutura de dados simples, matriz, as linhas da matriz irão representar as ruas e as colunas as avenidas.
A partir do arquivo de entrada alocar as dimensões da matriz com os inteiros X Y.
Definir as esquinas bloqueadas através da posição informada no arquivo de entrada Definir os pontos B através da posição informada no arquivo de entrada
Para calcular a quantidade de caminhos mais curtos usei permutação com repetição, dessa forma eu posso calcular a quantidade de caminhos mais curtos do ponto A até B.
Exemplo: Conforme figura abaixo um possível caminho do ponto A até B é
RRRRDDD, onde R é direita e D é baixo. A quantidade de caminhos menores é dada assim

= 35 caminhos mais curtos

Porém temos os casos em que as esquinas estão bloqueadas, conforme figura abaixo. Nesse caso calculamos o número de caminhos de A até B que passam pelo caminho bloqueado.
Exemplo: RRDD, onde R é direita e D é baixo.

= 6 caminhos que passam por esquina bloqueada

Para calcular a quantidade de

Relacionados

  • Hash
    1179 palavras | 5 páginas
  • biologia
    697 palavras | 3 páginas
  • Algoritmo Genético Compacto Aplicado ao Problema de Alocação Ótima de Monitores de Qualidade da Energia Elétrica Sobre Sistemas de Distribuição
    2610 palavras | 11 páginas
  • HABILIDADE DE VIDA Conteudo Program Tico 2015
    1095 palavras | 5 páginas
  • Trab
    1281 palavras | 6 páginas
  • Oracle
    5315 palavras | 22 páginas
  • Lista De Exercicio 1
    2297 palavras | 10 páginas
  • plano de ensino
    1319 palavras | 6 páginas
  • Trabalho aeds 2 - tp0
    1482 palavras | 6 páginas
  • aula
    7667 palavras | 31 páginas