Colocar Resposta 
 
Avaliação do Tópico:
  • 0 votos - 0 Média
  • 1
  • 2
  • 3
  • 4
  • 5
Problema Algoritmico - O Labirinto
02-11-2015, 20:41 (Esta mensagem foi modificada pela última vez a: 02-11-2015 20:44 por Vasco127.)
Mensagem: #1
Problema Algoritmico - O Labirinto
Olá



Para a realização da cadeira de programação do 1ºano correspondente ao 1ºsemestre foi-me colocado um problema sobre o qual terei de me debruçar nas próximas semanas. Não sei como começar a desenvolver o algoritmo. Gostaria de alguma ajuda. Obrigado



Enunciado do problema: 



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










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
Procurar todas as mensagens deste utilizador
Citar esta mensagem numa resposta
03-11-2015, 13:34 (Esta mensagem foi modificada pela última vez a: 06-11-2015 10:53 por Informatica.)
Mensagem: #2
RE: Problema Algoritmico - O Labirinto
vais utilizar que tipo de linguagem?
Dá uma olhada neste link: https://www.ime.usp.br/~cris/aulas/01_1_5710/crono/programas/ratinho.c

Eu penso que esse problema é feito com o algoritmo de prim
Procurar todas as mensagens deste utilizador
Citar esta mensagem numa resposta
05-11-2015, 16:08
Mensagem: #3
RE: Problema Algoritmico - O Labirinto
Linguagem C
Procurar todas as mensagens deste utilizador
Citar esta mensagem numa resposta
07-11-2015, 12:01
Mensagem: #4
RE: Problema Algoritmico - O Labirinto
Obrigado pela ajuda
Procurar todas as mensagens deste utilizador
Citar esta mensagem numa resposta
Colocar Resposta 


Saltar Fórum:


Utilizadores a ver este tópico: 2 Visitante(s)