Ir para conteúdo
Fórum CódigoFonte.net
Vasco127

Problema Algorítmico – o Labirinto

Recommended Posts

Olá

Para uma cadeira de programação  tenho de realizar um projecto que consiste no seguinte:

 

Um grupo de ratos de laboratório foi treinado para fugir de um labirinto. O labirinto é composto por células, podendo cada célula estar, ou não, ligada a outra célula. Entre cada duas células interligadas podem existir obstáculos, implicando um atraso temporal no percurso a executar entre as células interligadas. Algumas interligações só permitem percursos unidirecionais. Apenas uma das células do labirinto permite que os ratos saiam do mesmo. Deve admitir-se que cada um dos ratos, depois de treinado num determinado labirinto, tem a capacidade de percorrer o caminho mais curto (ótimo) que lhe permite sair do labirinto, quando colocado aleatoriamente numa determinada célula. Pretende-se realizar uma experiência que consiste no seguinte:  é colocado um rato treinado em cada uma das células do labirinto  um cronómetro inicia uma contagem decrescente  quando o cronómetro chega a zero, conta-se o número de ratos que atingiu a saída do labirinto. O problema em resumo: deve ler-se a descrição do labirinto e o valor inicial do cronómetro (entradas ou inputs) e calcular o número de ratos que atinge a saída do labirinto (saída ou output). Deve ainda assumir-se que cada célula pode albergar um número arbitrário de ratos. Especificação das entradas: as células do labirinto estão numeradas sequencialmente de 1, 2, …, N, em que N é o número total de células. Pode assumir-se N ≤ 100. As primeiras três linhas de entrada contêm:  N, o número de células do labirinto  E, o número da célula de saída do labirinto  T, o valor inicial do cronómetro A quarta linha de entrada contém o número M de interligações do labirinto. Cada uma das seguintes M linhas especifica uma interligação à custa de três números inteiros:  Dois números de células A e B (pertencentes ao intervalo 1, …, N)  O número inteiro de unidades temporais que demora a percorrer a interligação entre a célula A e B De notar que cada interligação entre A e B só deverá ser considerada bidirecional se existir outra linha especificando a interligação entre B e A. Exemplo de entradas: 4 2 1 8 1 2 1 1 3 1 2 1 1 2 4 1 3 1 1 3 4 1 4 2 1 4 3 1 Métodos de Programação 1 (MP1) MIETI 1º ano 2015/2016 4 Especificação da saída (ou output): consiste numa única linha com um número inteiro que representa o número de ratos que atingiu a saída E do labirinto ao fim de T unidades de tempo. Exemplo de saída (tendo em conta as entradas indicadas no exemplo anterior): 3

 

Já comecei a desenvolver o algoritmo. As  minhas dúvidas são  as  seguintes :  Como definir as interligaçoes ? Em que situaçoes terá de se usar vetores\matrizes ?. Gostaria que alguem  pudesse esclarecer. Obrigado pela ajuda

 

 

Aqui está o que já foi desenvolvido:

 

Var

N,T,M,R:inteiro;

a1,a2,b1,b2,a3,b3:inteiro;


Inicio


R=1;

Escrever " Introduza o numero de celulas esxistentes "

Ler N

Escrever " Introduza o numero da celula de saida"

Ler E

Escrever " Introduza o valor inicial cronometro"

Ler T

Escrever " Introduza o numero de interligaçoes existentes"

Ler M


Escrever " Introduza valor celula de partida"

Ler a1


Escrever " Introduza valor celula de chegada"

Ler a2

Escrver "Introduza tempo que demora interligaçao"

Ler a3



Se a2==E&& a3==T&&R <=N


Escrever " Numero de ratos que saiu "

 

 

 

 

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar Agora

×