Ir para o conteúdo
ruibessa

Duvida Pascal - Lazarus

Mensagens Recomendadas

ruibessa

Boa tarde, gostaria de saber se alguém me poderia ajudar com um pequeno trabalho.. A minha dúvida está em como conseguir achar o caminho mais curto de uma "cidade" a outra, que têm as distâncias inseridas dentro de uma matriz que são geradas aleatoriamente..

O objetivo é encontrar o caminho mais curto passando por todas as "cidades" apenas 1 vez e na ultima voltar à cidade de origem, somando essas mesmas distâncias e depois apresentar qual o caminho escolhido e a distancia percorrida nesse caminho..

-------------------------------------------------------------------------

program curto;

uses crt;

const max_cidades=25;

var
       matriz_distancia: array of array of integer;
       ncidades, linhas, colunas: integer;

function matriz_aleatoria():integer; forward;
procedure listar_matriz(); forward;
procedure mais_curto(); forward;

function main():integer;

begin
    writeln('**************************************');
    writeln('* Qual o numero de cidades? (Max.25) *');
    writeln('**************************************');
    readln(ncidades);
    begin
            if ncidades>max_cidades then
                    begin
                         writeln('Foi inserido um valor mais alto do que o permitido. Tente novamente..');
                 writeln();
                     main();
                    end
            else
            clrscr;
            writeln('******************************************');
            writeln('            Escolheu ',ncidades,' cidades.');
            writeln('******************************************');
            writeln();
            exit;
    end;
end;

function matriz_aleatoria(): integer;

var diagonal: integer;

begin
diagonal:=0;
ClrScr;
setlength(matriz_distancia,ncidades,ncidades);

   for linhas:=0 to (ncidades-1) do
           begin
               for colunas:=0 to (ncidades-1) do
                   begin
                       if linhas=colunas then
                              begin
                                     matriz_distancia[linhas,colunas]:=diagonal;
                              end
                    else
                    begin
                            matriz_distancia[linhas,colunas]:=random(10);
                            matriz_distancia[colunas,linhas]:=matriz_distancia[linhas,colunas];
                        end;
                   end;
           end;
clrscr;
exit;
end;

procedure listar_matriz();

begin
clrscr;
       writeln('***********************************');
       writeln('   As distancias geradas foram:    ');
       writeln('***********************************');
       writeln();
   for linhas:=0 to (ncidades-1) do
       begin;
           for colunas:=0 to (ncidades-1) do
               begin;
                                     write(matriz_distancia[linhas,colunas]:2,'|');
               end;
           writeln;
               end;
       writeln();
       writeln('Prima uma tecla para voltar ao menu...');
       readln();
       clrscr;
       exit;
end;

function mais_curto();

begin

writeln('Qual o ponto de origem?');
readln(origem);

end;

{* ----------------------------------
              "main"
     aqui inicia-se o programa
---------------------------------- *}
Begin
    main();
    matriz_aleatoria();
    listar_matriz();
    mais_curto();
readkey;
end.

Editado por pwseo
syntax highlight.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
nunopicado

Boa tarde

Fiquei sem perceber qual a tua dúvida em concreto.

No entanto, reparei que o teu código tem um problema na função matriz_aleatoria:

Ao colocares dois for's encadeados, ambos entre 0 e ncidades-1, os comandos executados pelo for interno serão executados exactamente uma vez por cada posição da matriz.

No entanto, o que estás a fazer lá dentro é a preencher 2 casas da matriz, e não apenas uma.

Isso significa que vais preencher todas as casas duas vezes cada uma, ou seja, um dos valores que estás a meter vai ser sobrescrito, ou seja, vai-se perder metade de todo o trabalho feito por essa função.

Se a ideia é que haja uma simetria, como parece ser, tens de o fazer de outra forma, com apenas um for, e com uma formula que te permita aceder às posições cuja distância deve ser igual.


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
ruibessa

Obrigado pela resposta, a minha dúvida é mesmo por onde começar o código para calcular o caminho mais curto. Como estou a começar ainda não tenho muito pratica.

Nesta parte o programa terá de perguntar ao utilizador qual o ponto de origem(na matriz), calcular os caminhos possíveis e dar a indicação de qual o mais curto e assim sucessivamente até passar por todos os pontos e no final voltar ao inicial..

Usei dois ciclos for porque como a matriz tem 2 índices, pensei que fosse necessário colocar um valor para a linha e outro valor para a coluna, logo usei um for para correr o primeiro índice e o segundo for para o segundo indice..

Se me puder ajudar também nesta parte gostaria de saber a melhor forma..

Cumprimentos

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
nunopicado

Usei dois ciclos for porque como a matriz tem 2 índices, pensei que fosse necessário colocar um valor para a linha e outro valor para a coluna, logo usei um for para correr o primeiro índice e o segundo for para o segundo indice..

E estaria correcto se a cada iteração só preenchesses uma casa da matriz.

matriz_distancia[linhas,colunas]:=random(10);                        // Vamos chamar a este comando S1
matriz_distancia[colunas,linhas]:=matriz_distancia[linhas,colunas];  // Vamos chamar a este comando S2

Mas com estas duas linhas, estás a preencher duas casas, pelo que tens de percorrer apenas metade das casas da matriz.

Vamos assumir uma matriz de 3, para facilitar o exemplo. 3 x 3 = 9, pelo que terás 9 casas na matriz, ou seja, o teu conjunto dos dois FORs vão ser executados 9 vezes (uma por cada casa).

|L0 C0 P1 | L0 C1 P2 | L0 C2 P3|
|L1 C0 P4 | L1 C1 P5 | L1 C2 P6|
|L2 C0 P7 | L2 C1 P8 | L2 C2 P9|

Legenda:

L = Linha

C = Coluna

P = Número da casa (apenas para ser mais fácil aqui referenciar)

Vamos simular os teus FORs...

1ª Passagem: Linha = 0, Coluna = 0, Casa P1

S1: Atribui à casa P1 por exemplo o valor 5

S2: Inverte o valor de linhas e colunas, que no caso continua a ser L0 C0, ou seja, ainda P1. Volta a meter o valor 5 na mesma casa que já o tinha.

2ª Passagem: Linha = 0, Coluna = 1, Casa P2

S1: Atribui à casa P2 por exemplo o valor 8

S2: Inverte, pelo que fica com a casa P4, e mete o mesmo valor 8

À segunda passagem, tens 3 casas preenchidas.

3ª Passagem: Linha = 0, Coluna = 2, Casa P3

S1: Atribui à casa P3 por exemplo o valor 7

S2: Inverte, pelo que fica com a casa P7, e mete o mesmo valor 7

À terceira passagem, tens já 5 casas preenchidas.

4ª Passagem: Linha = 1, Coluna = 0, Casa P4

S1: Atribui à casa P4 por exemplo o valor 3

Ora, P4 já estava preenchida, desde a segunda passagem. Vais sobreescrever o valor que lá estava (o 8), pelo novo valor (o 3). Estás a ver aqui o problema?

S2: Invertes, ficas com a casa P2, que também já estava preenchida, e leva outro valor por cima, no caso o 3.

Com isto, a segunda passagem foi completamente ao ar, e é como se nunca tivesse ocorrido (excepto pelo tempo que demorou).

5ª Passagem: Linha = 1, Coluna = 1, Casa P5

S1: Atribui à casa P5 por exemplo o valor 2

S2: Inverte, e fica na mesma com a casa P5 (porque linha e coluna são iguais), e mete lá o valor 2, que já lá estava.

6ª Passagem: Linha = 1, Coluna = 2, Casa P6

S1: Atribui à casa P6 por exemplo o valor 1

S2: Inverte, e fica com a casa P8, onde também mete o valor 1

7ª Passagem: Linha = 2, Coluna = 0, casa P7

S1: Atribui à casa P7 por exemplo o valor 9. A Casa P7 já estava preenchida desde a 3ª passagem, pelo que se perdeu o valor anterior

S2: Inverte, e fica com a casa P3, onde também mete o valor 9, perdendo-se o que lá estava.

A 3ª passagem foi ao ar.

8ª Passagem: Linha = 2, Coluna = 1, casa P8

S1: Atribui à casa P8 por exemplo o valor 6. A casa P8 já estava preenchida desde a 6ª passagem

S2: Inverte e fica com a casa P6, onde também mete o valor 6, perdendo-se o que lá estava.

A 6ª passagem foi ao ar.

9ª Passagem: Linha = 2, Coluna = 2, casa P9

S1: Atribui à casa P9 o valor 5

S2: Inverte e fica na mesma em P9. Volta a meter lá o valor 5, que já lá estava

Com isto se conclui as passagens dos teus 2 FORs. Como podes ver, muito do trabalho feito é repetição de outro anterior.

E isto é com uma matriz pequena.

Enquanto programador, tens de descobrir forma de minimizar isto, ou se possível, eliminar de todo.

Como o fazer, depende do que queres fazer exactamente.

Se a ideia é manter a simetria que consegues com esta passagem, em que em termos de valor atribuido, P2 = P4, P3 = P7 e P6 = P8, tens de percorrer a matriz metade das vezes, usando uma formula matemática (a formular) que te permita bater certo com todas estas casas.

Quanto ao restante do programa, ainda não percebi bem o que precisas com isso das distâncias...

Tens de clarificar.


"A humanidade está a perder os seus génios... Aristóteles morreu, Newton já lá está, Einstein finou-se, e eu hoje não me estou a sentir bem!"

> Não esclareço dúvidas por PM: Indica a tua dúvida no quadro correcto do forum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.