Ir ao conteúdo
  • Cadastre-se
Victor Portugal

C Caixeiro Viajante com 3 dimensões

Recommended Posts

Fala pessoal, boa tarde. Estou com um trabalho para fazer e não estou conseguindo completá-lo, então, queria ver se vocês conseguem me ajudar.

O trabalho consiste no código do caixeiro viajante com 3 dimensões, vou deixar o meu código com 2 dimensões aqui para olharem e se possível, me ajudarem a 'colocar a terceira dimensão' nele.

Valeu!

 

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

struct cidade {
    char nome;
    float x, y;
};

int main(int argc, char *argv[]) { //argc quantidade de argumentos e argv os argumentos
    int i, j, n, letra = 65; //65 e a letra A da tabela ASCII
    printf("\nQuantas Cidades? ");
    scanf("%d", &n);
    struct cidade cid[n]; //vetor de estrutura de cidades
    float distancia[n][n], x1, x2, y1, y2;
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        cid[i].nome = letra + i; //nome da cidade de A (65) ate A+n
        x1 = rand() % 100; //entre 0 e 99
        x2 = (rand() % 20) + 1; //1 e 20
        y1 = rand() % 100;
        y2 = (rand() % 20) + 1;
        cid[i].x = x1 / x2; //coordenada x da cidade 
        cid[i].y = y1 / y2; //coordenada y da cidade
    }
    for (i = 0; i < n; i++) {
        printf("\n%c(%.2f, %.2f)", cid[i].nome, cid[i].x, cid[i].y); //imprime as coordenadas da cidade
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            distancia[i][j] = sqrt((pow((cid[i].x - cid[j].x), 2) + pow((cid[i].y - cid[j].y), 2))); //calculo da distancia por pitagoras
            distancia[j][i] = distancia[i][j]; //espelhar a matriz
        }
    }
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i); //imprime o cabecalho
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i); //imprime a primeira coluna com a letra da cidade
        for (j = 0; j < n; j++) {
            printf("%.2f\t", distancia[i][j]); //imprime a distancia entre cidades
        }
        printf("\n\n");
    }
    int xMin, yMin; //armazena as coordenadas da menor distancia
    float menorValor, caminho[n][n]; //menor distancia e caminho a seguir 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            caminho[i][j] = 0; //inicializa a matriz de caminhos
        }
    }
    int todas = 0, k;
    char vetCam[n]; //nome das cidades
    printf("\nDe qual cidade deseja partir?\n0 a %d ", n - 1);
    scanf("%d", &i);
    int v = i; //cidade inicial tem que ser a final
    float tmp[n];
    for (k = 0; k < n; k++) {
        tmp[k] = distancia[i][k]; //vetor de distancias temporarias
        distancia[k][i] = 0; //zerando a coluna da cidade de partida 
    }
    while (todas < n) {
        vetCam[todas] = cid[i].nome;
        todas++;

        menorValor = 1000;
        for (j = 0; j < n; j++) {
            if ((distancia[i][j] < menorValor) && (distancia[i][j] != 0)) {
                xMin = i;
                yMin = j;
                menorValor = distancia[i][j];
            }
        }
        i = yMin;
        caminho[xMin][yMin] = distancia[xMin][yMin];
        if (n > todas + 1) {
            for (k = 0; k < n; k++) {
                distancia[k][i] = 0;
            }
        } else {
            caminho[i][v] = tmp[i];
        }
    }
    printf("\nCAMINHOS\n\n");
    for (i = 0; i < n; i++) {
        printf("\t%c", letra + i);
    }
    printf("\n\n");
    for (i = 0; i < n; i++) {
        printf("%c\t", letra + i);
        for (j = 0; j < n; j++) {
            printf("%.2f\t", caminho[i][j]);
        }
        printf("\n\n");
    }
    for (k = 0; k < n; k++) {
        printf("%c --> ", vetCam[k]);
    }
    vetCam[n - 1] = cid[v].nome;
    printf("%c", vetCam[n - 1]);
    printf("\n\n");
    return 0;
}

 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×