C Question
Calculating distances
An exercise asked me to read an input archive like the following one:
4
1 10
4 4
5 1
2 0
Where the first number (4) represents the number of cities and each line below it represents a city with its coordinates
(x,y)typedef struct
{
int x;
int y;
} Cidade;
This part of the exercise I have already done and it's ok. Next step, I need to print in an output archive all the possible routes for these cities and calculate the route's total distance, remembering that the last one should be the starting point. For this, I made a permutation function that makes it for me. The function is this:
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;
if(inicio == termino)
{
for(i = 0; i < termino; i++)
fprintf(saida, "%d\t", sequencia[i]+1);
fprintf(saida, "= %f\n", Distancia(C, termino));
}
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));
}
}
}
With this input archive, I get the following output one:
24
1 2 3 4 = 23.032759
1 2 4 3 = 23.032759
1 3 2 4 = 23.032759
1 3 4 2 = 23.032759
1 4 3 2 = 23.032759
1 4 2 3 = 23.032759
2 1 3 4 = 23.032759
2 1 4 3 = 23.032759
2 3 1 4 = 23.032759
2 3 4 1 = 23.032759
2 4 3 1 = 23.032759
2 4 1 3 = 23.032759
3 2 1 4 = 23.032759
3 2 4 1 = 23.032759
3 1 2 4 = 23.032759
3 1 4 2 = 23.032759
3 4 1 2 = 23.032759
3 4 2 1 = 23.032759
4 2 3 1 = 23.032759
4 2 1 3 = 23.032759
4 3 2 1 = 23.032759
4 3 1 2 = 23.032759
4 1 3 2 = 23.032759
4 1 2 3 = 23.032759
Where the first number (24) represents all possible routes and each line below it contains the cities' index+1. The float number at its end is the distance of each route, which ones I'm supposed to compare at the end of the program and tell the shortest path. But I'm getting this result (which is wrong): All distances of all routes have the same value. The function I used to calculate these distances is shown below:
float Distancia(Cidade *C, int numeroCidade)
{
int i;
float total = 0;
for(i = 0; i < numeroCidade; i++)
{
if(i == numeroCidade-1)
{
int distanciaX = pow(C[i].x - C[0].x, 2);
int distanciaY = pow(C[i].y - C[0].y, 2);
total = total + sqrt(distanciaX + distanciaY);
}
else
{
int distanciaX = pow(C[i].x - C[i+1].x, 2);
int distanciaY = pow(C[i].y - C[i+1].y, 2);
total = total + sqrt(distanciaX + distanciaY);
}
}
return total;
}
I would like to know if there is something wrong and why the calculated distances have the same value. Is there a better way to calculate it?
Recommended for you: Get network issues from WhatsUp Gold. Not end users.
Answer Source
Your Distancia function is currently going through your list of cities each time, with the same numeroCidade, so it always gets the same results.
What you want it to have it go through your sequence of cities. Your function should look something like this. (I'll leave part of it to you to finish, though.)
float Distancia(Cidade *c, int numeroCidade, int* sequencia)
{
int i;
float total = 0;
float distance;
for (i = 0; i < numeroCidade; i++)
{
/* distance from one city in the sequence to the next = ... ? */
float = float + distance;
}
return float;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download