0

O exercício me pede para imprimir as menores rotas entre n cidades, considerando que a última é a mesma cidade do ponto inicial. Primeiro, eu preciso ler um arquivo de entrada como o seguinte:

5
1 10
4 4
5 1
2 0
7 21

Onde o primeiro número (5) representa o número de cidades e cada linha abaixo representa cada cidade e suas coordenadas (x,y). Cada cidade é representada pela estrutura:

typedef struct
{
    int x;
    int y;
} Cidade;

Depois, preciso imprimir todas as rotas possíveis e suas distâncias totais, parte que eu também já fiz. Pra isso, eu usei as seguintes funções:

void Troca(int *x, int *y)
{
    int aux;
    aux = *x;
    *x = *y;
    *y = aux;
}

void Permuta(FILE *saida, Cidade *C, int *sequencia, int inicio, int 
termino, int totalViagens)
{
    int i, j;
    totalViagens = TotalViagens(termino);
    if(inicio == termino)
    {
        for(i = 0; i < termino; i++)
            fprintf(saida, "%d\t", sequencia[i]+1);
        fprintf(saida, "= %f\n", Distancia(C, termino, sequencia));
    }
    else
    {
        for(j = inicio; j < termino; j++)
       {
            Troca((sequencia+inicio), (sequencia+j));
            Permuta(saida, C, sequencia, inicio+1, termino, totalViagens);
            Troca((sequencia+inicio), (sequencia+j));
       }
    }
}

void CriaSequencia(FILE *saida, Cidade *C, int *sequencia, int numeroCidade)
{
    int i;
    totalViagens = TotalViagens(numeroCidade);
    for(i = 0; i < numeroCidade; i++)
    {
        sequencia[i] = i;
    }
    Permuta(saida, C, sequencia, 0, numeroCidade, 
TotalViagens(numeroCidade));
}

Com essa funções, o programa imprime em um arquivo de saída essas informações:

120
1   2   3   4   5   = 47.063416
1   2   3   5   4   = 61.486000
1   2   4   3   5   = 46.907471
1   2   4   5   3   = 62.644718
1   2   5   4   3   = 58.522675
1   2   5   3   4   = 57.208015
1   3   2   4   5   = 51.513924
1   3   2   5   4   = 61.814468
1   3   4   2   5   = 47.235947
1   3   4   5   2   = 58.522675
1   3   5   4   2   = 62.644718
1   3   5   2   4   = 61.658531
1   4   3   2   5   = 46.077225
1   4   3   5   2   = 57.208015
1   4   2   3   5   = 50.199272
1   4   2   5   3   = 61.658527
1   4   5   2   3   = 61.814472
1   4   5   3   2   = 61.485996
1   5   3   4   2   = 46.907475  
1   5   3   2   4   = 50.199272
1   5   4   3   2   = 47.063412
1   5   4   2   3   = 51.513927
1   5   2   4   3   = 47.235943
1   5   2   3   4   = 46.077229
2   1   3   4   5   = 58.522675
2   1   3   5   4   = 62.644714
2   1   4   3   5   = 57.208019
2   1   4   5   3   = 61.486000
2   1   5   4   3   = 47.063416
2   1   5   3   4   = 46.907475
2   3   1   4   5   = 61.814472
2   3   1   5   4   = 51.513927
2   3   4   1   5   = 46.077225
2   3   4   5   1   = 47.063412
2   3   5   4   1   = 61.485996
2   3   5   1   4   = 50.199272
2   4   3   1   5   = 47.235947
2   4   3   5   1   = 46.907475
2   4   1   3   5   = 61.658527
2   4   1   5   3   = 50.199268
2   4   5   1   3   = 51.513927
2   4   5   3   1   = 62.644714
2   5   3   4   1   = 57.208015
2   5   3   1   4   = 61.658531
2   5   4   3   1   = 58.522675
2   5   4   1   3   = 61.814472
2   5   1   4   3   = 46.077225
2   5   1   3   4   = 47.235947
3   2   1   4   5   = 61.486000
3   2   1   5   4   = 47.063416
3   2   4   1   5   = 50.199272
3   2   4   5   1   = 51.513927
3   2   5   4   1   = 61.814472
3   2   5   1   4   = 46.077225
3   1   2   4   5   = 62.644714
3   1   2   5   4   = 58.522675
3   1   4   2   5   = 61.658531
3   1   4   5   2   = 61.814472
3   1   5   4   2   = 51.513927
3   1   5   2   4   = 47.235947 
3   4   1   2   5   = 57.208015
3   4   1   5   2   = 46.077225
3   4   2   1   5   = 46.907471
3   4   2   5   1   = 47.235943
3   4   5   2   1   = 58.522675
3   4   5   1   2   = 47.063412
3   5   1   4   2   = 50.199272  
3   5   1   2   4   = 46.907475
3   5   4   1   2   = 61.485996
3   5   4   2   1   = 62.644714
3   5   2   4   1   = 61.658531
3   5   2   1   4   = 57.208015
4   2   3   1   5   = 51.513927
4   2   3   5   1   = 50.199272
4   2   1   3   5   = 62.644714
4   2   1   5   3   = 46.907471
4   2   5   1   3   = 47.235943
4   2   5   3   1   = 61.658527
4   3   2   1   5   = 47.063416
4   3   2   5   1   = 46.077225
4   3   1   2   5   = 58.522675
4   3   1   5   2   = 47.235947
4   3   5   1   2   = 46.907475
4   3   5   2   1   = 57.208015
4   1   3   2   5   = 61.814468
4   1   3   5   2   = 61.658531
4   1   2   3   5   = 61.486000
4   1   2   5   3   = 57.208015
4   1   5   2   3   = 46.077225
4   1   5   3   2   = 50.199272
4   5   3   1   2   = 62.644714
4   5   3   2   1   = 61.485996
4   5   1   3   2   = 51.513927
4   5   1   2   3   = 47.063412
4   5   2   1   3   = 58.522675
4   5   2   3   1   = 61.814472
5   2   3   4   1   = 46.077225
5   2   3   1   4   = 61.814468
5   2   4   3   1   = 47.235947
5   2   4   1   3   = 61.658531
5   2   1   4   3   = 57.208015
5   2   1   3   4   = 58.522675
5   3   2   4   1   = 50.199272
5   3   2   1   4   = 61.486000
5   3   4   2   1   = 46.907471
5   3   4   1   2   = 57.208015
5   3   1   4   2   = 61.658531
5   3   1   2   4   = 62.644714
5   4   3   2   1   = 47.063416
5   4   3   1   2   = 58.522675
5   4   2   3   1   = 51.513924
5   4   2   1   3   = 62.644714
5   4   1   2   3   = 61.486000
5   4   1   3   2   = 61.814472
5   1   3   4   2   = 47.235943
5   1   3   2   4   = 51.513924
5   1   4   3   2   = 46.077225
5   1   4   2   3   = 50.199268
5   1   2   4   3   = 46.907471
5   1   2   3   4   = 47.063416

Onde o primeiro número (120) representa todas as rotas possíveis e cada linha abaixo tem o índice+1 de cada cidade e a distância total da rota. Agora, eu tenho que comparar todas essas distâncias e dizer qual ou quais são as menores, imprimindo a sua rota seguida de sua distância. Lembrando que, caso exista mais de uma rota menor, também preciso imprimir ela. Tentando fazer isso, criei a seguinte função:

float MenorDistancia(FILE *saida, Cidade *C, int numeroCidade, int 
totalViagens, int *sequencia)
{
    int i;
    float menor = INFINITO; //INFINITO = 10000000
    for(i = 0; i < totalViagens; i++)
    {
        if(Distancia(C, numeroCidade, sequencia) <= menor)
            menor = Distancia(C, numeroCidade, sequencia);
    }
    return fprintf(saida, "\nMenor rota: %f\n", menor);
}

E eu mudei a função CriaSequencia, tentando fazê-la funcionar com a nova função MenorDistancia.

void CriaSequencia(FILE *saida, Cidade *C, int *sequencia, int numeroCidade, 
int totalViagens)
{
    int i;
    totalViagens = TotalViagens(numeroCidade);
    for(i = 0; i < numeroCidade; i++)
    {
        sequencia[i] = i;
    }
    Permuta(saida, C, sequencia, 0, numeroCidade, 
TotalViagens(numeroCidade));
    MenorDistancia(saida, C, numeroCidade, totalViagens, sequencia);
}

Com essas funções, eu tenho o mesmo arquivo de saida mostrado acima, porém, em seu final, eu tenho apenas uma linha

Menor rota: 47.063416

Primeiramente eu gostaria de saber porquê não é mostrada a menor rota, sendo que há rotas menores no arquivo, como podemos ver. E também gostaria de saber uma forma de imprimir as rotas com o índice+1 de cada cidade e, no final, a sua distância total. Lembrando que preciso imprimir todas as menores rotas.

1
  • Faltam ai coisas para se conseguir ajudar. Como foi definida a função Distancia ? Como foi chamada a função MenorDistancia para produzir aquele resultado ? Se é uma permutação de cidades, porque a sequencia é um int* ?
    – Isac
    Commented 1/10/2017 às 23:15

1 Resposta 1

0

Se os itens estão em uma array você pode fazer assim.

Faça a iteração sobre todos os itens e depois cheque um por um. Não sei muito de c então vou fazer um pseudo code pra você

double menorvalor = 10000000;
for(int i = 0;i < lista.Tamanho;i++) //iteração sobre todos os itens
{
    if (lista[i] < menorvalor)//toda vez que o valor for menor ele vai ser setado como o menor sendo o menor setado primeiramente um valor absurdo.
    {
        menorvalor = lista[i];
    }
}

isso iria funcionar, se for isso que você queria é só adaptar para o c.

Pelo que eu vi no seu código me parece que você compara com os valores errados.

for(i = 0; i < totalViagens; i++)

não deveria ser o total de distancias?

enfim posso estar viajando mas...

Agora se você quer uma lista de menores valores basta você fazer a mesma iteração só que usando uma array x (onde x é o numero de menores valores que quer) e comparar com a lista Ex

float[] listamenor = float[x]; //lista de x menores valores.
float menorvalor = 10000000;
for(int i = 0;i < listamenor.Tamanho;i++)
{
listamenor[i] = 0; //setando todos os valores a 0.
}

for(int i = 0;i < lista.Tamanho;i++) //iteração sobre todos os itens
{
    if (lista[i] < listamenor[0])// vamos supor que a lista é de 2 menores numeros
    {
        listamenor[0] = lista[i];
    }
    else if (lista[i] < listamenor[1])
//isso é uma má pratica mas você pode fazer usando o for para comparar todos os itens da listamenor.
    {
        listamenor[1] = lista[i];
    }
}

Boa sorte.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .