recursion, find distance between multiple cities, help pls

Page 1 of 1

3 Replies - 5964 Views - Last Post: 24 August 2009 - 03:37 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=122042&amp;s=9ffebc58328d1ffb69a1bcd951ff89a0&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 snssewell

Reputation: 0
• Posts: 16
• Joined: 15-January 08

recursion, find distance between multiple cities, help pls

Posted 24 August 2009 - 02:01 PM

I have a project that should prompt the user to enter as many cities as he likes with x and y coordinates. When he is done entering cities the program should use recursion to pick each city from the list and calculate the distance. So lets say the user enters 3 cities.

New York 10, 15
Las Vegas 33, 55
Denver 22, 44

I need to calculate the distance from New York to Las Vegas and from Las Vegas to Denver, then add it all up and display it.

Here are the actual instructions: Create a Java program that prompts the user for a list of cities, where each city has a name and x and y coordinates. After all cities have been entered, the program should use a recursive algorithm to print the length of all possible routes that start at the first city entered and end at the last city entered, and visit every city in the list. For each route, the program should print the name of each city visited, followed by the length of the route.

As for now I am just trying to get it to calculate ONE route. I will worry about the all possible routes later.
I know the code is very elementary but I am just trying to get it to work before I make it all fancy.

Can anyone point me in the right direction? If you have any suggestions on how to solve this a different way please let me know. My brain is smoking right now.
Here is what I have so far:

``` import java.io.*;
import java.util.*;

class findRoutesMain
{
public static void main(String[] args)
{
Scanner scanner = new Scanner (System.in);

String city = "";
double x = 0;
double y = 0;
int choice = 0;

// First run to enter the starting location.
System.out.println("Enter the name of the city:");
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

System.out.println();
System.out.println("Pick one of the following choices:");
System.out.println(" 1. Enter another city");
System.out.println(" 2. Enter destination");
System.out.println(" 3. Exit");

System.out.println();
choice = scanner.nextInt();

while(choice == 1)
{
switch(choice)
{
case 1:
System.out.println("Enter the name of the city:");
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

System.out.println();
System.out.println("Pick one of the following choices:");
System.out.println(" 1. Enter another city");
System.out.println(" 2. Enter destination");
System.out.println(" 3. Exit");

System.out.println();
choice = scanner.nextInt();

break;

case 3:
// Exit
System.out.println("Good bye");
System.exit(0);
break;

}// end switch
}// end loop

// Enter final destination
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

// Compute the distance between all the cities recursively, print all cities, and the total distance
// between all cities. Not Sure How....?????

double distance = 0;
double endX = 0;
double startX = 0;
double endY = 0;
double startY = 0;
distance = Math.sqrt((endX-startX)*(endX-startX) + (endY-startY)*(endY-startY));

}// end main
}//end class

```

PS: Someone had posted a question about this project back in June which I found when I did a search, but it did not help me any so I thought I post it again. Thanks in advance.

Is This A Good Question/Topic? 0

Replies To: recursion, find distance between multiple cities, help pls

#2 syfran

• D.I.C Lover

Reputation: 83
• Posts: 1,103
• Joined: 12-July 09

Re: recursion, find distance between multiple cities, help pls

Posted 24 August 2009 - 02:56 PM

Whats with all the recursion posts lately? did all the teachers decide to assign them all at once?

I would suggest a function similar to this :
```public void findDistance(ArrayList cities, destination, current, distance) {

if( cities.empty() )
print distance + distance to dest
return;
for x in cities
findDistance(cities.remove(x),destination, x, distance + distanceToX);

}
```

Edit: maybe not exactly like that... give me a couple seconds to rewrite the pseudo code
Something like that should work

This post has been edited by syfran: 24 August 2009 - 03:03 PM

#3 snssewell

Reputation: 0
• Posts: 16
• Joined: 15-January 08

Re: recursion, find distance between multiple cities, help pls

Posted 24 August 2009 - 03:30 PM

syfran, on 24 Aug, 2009 - 01:56 PM, said:

Whats with all the recursion posts lately? did all the teachers decide to assign them all at once?

I would suggest a function similar to this :
```public void findDistance(ArrayList cities, destination, current, distance) {

if( cities.empty() )
print distance + distance to dest
return;
for x in cities
findDistance(cities.remove(x),destination, x, distance + distanceToX);

}
```

Edit: maybe not exactly like that... give me a couple seconds to rewrite the pseudo code
Something like that should work

Ok so I am trying to follow here.
(ArrayList cities, destination, current, distance)
I am a little confused. ArrayList cities is the list of city names right? But I am not quite sure about destination, current, and distance. I guess its still a bit over my head. But I am trying to understand this recursion stuff. Let me take a step back. If all I wanted to do is access each city in the City List (just the names) and print them. How would I do that? I guess my main problem for now is how to access a list using recursion. I have found a few examples but none of them use data from a list.

#4 syfran

• D.I.C Lover

Reputation: 83
• Posts: 1,103
• Joined: 12-July 09

Re: recursion, find distance between multiple cities, help pls

Posted 24 August 2009 - 03:37 PM

Recursion is calling a function from within itself, in this case findCities.

Destination is the destination city. current is the current city, and distance is how far you have traveled along the current route.