Jump to content
ruibessa

Duvida Pascal - Lazarus

Recommended Posts

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.

Edited by pwseo
syntax highlight.

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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.

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.