We are given 10 cities with latitudes x and longitudes y, and we have to figure out what order visited will give us the shortest distance traveled. We have to:
1. Create a function that returns an array of a random permutation 1-10 (this will help randomize which cities we visit in what order). I made this called randPerm. [THIS WORKS PERFECTLY].
2. Write a function that prints out the cities in the order specified by the permutation. I made this called printInGivenOrder. [THIS PRINTS OUT ALL 0's, DOESN'T WORK]
3. Write a function that generates random order of the cities and searches for the one with the smallest total distance. [ALSO DOESN'T WORK]
Here is what I have so far:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct City
{
float name;
float x;
float y;
};
void randPerm(int N, int perm[])
{
srand(time(NULL));
int i;
for(i=0;i<N;i++)//initalize numbers
{
perm[i] = i;
}
for(i=0;i<N;i++)
{
int n=rand() % N;
if(perm[n]<0) //not unique, try again
--i;
else {
printf("%d\n", perm[n]); //got one
perm[n]=-1; //mark that index taken,
} //thus marking that number
}
}
void printInGivenOrder(struct City cityArray[], int perm[])
{
int i,num;
printf("\nOrder of Cities:\n");
for(i=0;i<10;i++)
{
num=perm[i];
printf("%d\n", cityArray[num].name);
}
}
float getTotalDistGivenPerm(int N, struct City cityArray[], int perm[])
{
int i;
int index1,index2;
float distance,totaldist=0, a1,a2,b1,b2,x,y;
for(i=1;i<N;i++)
{
index1 = perm[i];
index2 = perm[i-1];
a1=cityArray[index1].x;
a2=cityArray[index1].y;
b1=cityArray[index2].x;
b2=cityArray[index2].y;
x=69.1*(a1-b1); //this is just a formula i found online to
y=53.0*(a2-b2); //calculate latitude and longitude and convert
distance=sqrt(x*x + y*y); //to distance
totaldist=totaldist+distance;
}
return totaldist;
}
int main()
{
struct City cityArray[10];
cityArray[0].name=1; //"Ann Arbor";
cityArray[0].x=42.28;
cityArray[0].y=-83.75;
cityArray[1].name=2;// "Austin";
cityArray[1].x=30.25;
cityArray[1].y=-97.75;
cityArray[2].name=3;// "Boston";
cityArray[2].x=42.36;
cityArray[2].y=-71.06;
cityArray[3].name=4;// "Chicago";
cityArray[3].x=41.88;
cityArray[3].y=-87.63;
cityArray[4].name=5;// "Detroit";
cityArray[4].x=42.33;
cityArray[4].y=-83.05;
cityArray[5].name=6;// "Lansing";
cityArray[5].x=42.73;
cityArray[5].y=-84.55;
cityArray[6].name=7;// "Las Vegas";
cityArray[6].x=36.18;
cityArray[6].y=-115.14;
cityArray[7].name=8;// "Los Angeles";
cityArray[7].x=34.05;
cityArray[7].y=-118.25;
cityArray[8].name=9;// "Miami";
cityArray[8].x=25.79;
cityArray[8].y=-80.22;
cityArray[9].name=10;// "Seattle";
cityArray[9].x=47.61;
cityArray[9].y=-122.33;
int number=10;
int array[10];
randPerm(number, array);
printInGivenOrder(cityArray, array);
float finalDistancefromPerm= getTotalDistGivenPerm(number, cityArray, array);
printf("\n %f", finalDistancefromPerm);
return 0;
}
My 3 biggest problems:
1. How do I enter the name of the city into the structure instead of just 1-10? If I chance int name to char name[50] in the structure and enter the name instead, it gives me an error.
2. Why doesn't my printInGivenOrder function print out the names (or numbers 1-10 right now until I figure out how to use the names of the cities) in the order of the permutation? All it prints out is all 0's
3. What am I doing wrong in my last function? It also only prints out 1 zero.
I know my code is kind of sloppy right now, sorry for the inconvenience, but any help would greatly be appreciated! Thanks!