Jump to content
Vasco127

Problema algoritmico - Labirinto

Recommended Posts

Vasco127

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 "

Share this post


Link to post
Share on other sites
HappyHippyHippo

por outras palavras, não fizeste nada ...

o único conselho que te darei será : pesquisa sobre o algoritmo de Dijkstra na net


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.