7 Replies - 1376 Views - Last Post: 07 September 2011 - 10:30 PM Rate Topic: -----

#1 NoDice  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-September 11

Java recursion project

Posted 07 September 2011 - 06:47 PM

I am working on a project that is supposed to accept 5 city inputs with x and y coordinates from a user and then using recursion find the distances between cities on the path and the total distance of the path, it should do this for each possible pathway between City A and and E (which are constant). I understand the theory of how to do this when I picture it like a tree (which is why I posted that .jpg) Anyway I have seen similar projects in the forums and between what I know and some of the other threads this is what I have come up with so far. Right now I am mainly looking for some help on possibly forming some pseudo code so I can better understand how to make this happen with coding, at the bottom is a failed attempt at a total distance method, I had one that worked but I was using parallel arrays and rewrote everything else to use a class instead.

I have actually lurked here quite a bit in the past to find help with issues but this time I actually felt like asking for myself here is my code so far...
import java.util.*;
import java.io.*;

class travel
{
	private static class City
	//defines inner class object City
	{
		private int x, y;// variables declared for coordinates
		private String name;// variable declared for city name

	
		public City()//Default constructor
		{}
		public City(int x, int y, String n)
		/*creats custom constructor to allow me to pass values while creating object
		**I probably don't need this but here it is
		*/
		{
			this.x = x;
			this.y = y;
			this.name = n;
			
		}
		public int getX(){return x;}
		//method to get x
		
		public int getY(){return y;}
		//method to get y
		
		public String getNAME(){return name;}
		//method to get name
			
		public void setX(int x){this.x = x;}
		//method sets x
		
		public void setY(int y){this.y = y;}
		//method sets y
		
		public void setNAME(String n){this.name = n;}	
		//method sets name
	}
	public static void main(String[] args)
	{
		City[] Cities;//set up an array
		Cities = new City[5];// limit length of array
		
		//creat 5 instances of the City class		
		City C1 = new City();
		City C2 = new City();
		City C3 = new City();
		City C4 = new City();
		City C5 = new City();
		
		//Fill the array with City objects
		Cities[0] = C1;
		Cities[1] = C2;
		Cities[2] = C3;
		Cities[3] = C4;
		Cities[4] = C5;
				
		travel startup = new travel(Cities);		
	
	}
	public travel (City[] AA)
	{
		getCities(AA);// call method to get yser input and set objects' attributes accordingly
		
		//Call some recursion method???
	}
	public void getCities(City[] AA)
	{
		Scanner scan = new Scanner(System.in);//set up a scanner call	
		int i, x, y;
		String n, trash; 
		
		for (i=0; i < 5;i++)//this sets the city object name and coordinates as per user input
		{
			System.out.println("City name.");
			System.out.println("");
			n = scan.nextLine();
			AA[i].setNAME(n);
			System.out.println("X coordinates.");
			System.out.println("");
			x = scan.nextInt();
			AA[i].setX(x);
			trash = scan.nextLine();
			System.out.println("Y coordinates.");
			System.out.println("");
			y = scan.nextInt();
			trash = scan.nextLine();
			AA[i].setY(y);
			System.out.println("You entered: " + n + " Coordinates X:" + x + " Y:" + y + ".");
			System.out.println("");
						
		}
		for (i=0; i < 5;i++)//This is just to test that I am setting each object correctly
		{
			n = AA[i].getNAME();
			x = AA[i].getX();
			y = AA[i].getY();
			System.out.println(n + " at X:" + x + " Y:" + y);
		}
				
	}
	/*********************FAIL**************
	public double totalDistance(City[] AA)
	{
		int i =0;
		double xSub = AA[i].getX() - AA[i-1].getX();
		double ySub = AA[i].getY() - AA[i-1].getY();
		double distance = Math.pow(xSub, 2) + Math.pow(ySub, 2); 
		distance = Math.round(Math.sqrt(distance)); 
		System.out.println("Distance From " + AA[i].getNAME() + " to " + AA[i-1].getNAME() + " is " + distance + " miles.");
		if (i == 1)
		{ 
			return distance; 
		} 
		else
		{ 
			return distance+totalDistance(City[] AA, i-1);
		} 
	}*/
}

Attached image(s)

  • Attached Image


Is This A Good Question/Topic? 0
  • +

Replies To: Java recursion project

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,603
  • Joined: 27-December 08

Re: Java recursion project

Posted 07 September 2011 - 07:01 PM

What exactly are you trying to do with this information? Find the shortest path between two Cities for a plane trip? Just use Dijkstra's algorithm.

More or less, you can use a breadth-first or depth-first traversal though.

Some pseudo-code for depth-first traversal.
for each vertex from i = 0 to length-1
   for each child vertex as x in vertex[i]
        establish distance from vertex[i] to x
        recurse for x


Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7293
  • View blog
  • Posts: 12,132
  • Joined: 19-March 11

Re: Java recursion project

Posted 07 September 2011 - 07:07 PM

Okay: to begin with, why don't you spell out in words where you think you ought to start with this.

Forget the input for the moment, let's suppose we know that we have the direct paths:

A to B (5)
A to C (24)
B to D (12)
B to E (16)
C to E (7)
D to E (2)

I just pulled those out of my hat, they don't really mean anything. They're just there to give us data to talk about. (that is, I might change those later if I feel like it)

To start with, what is the best way to represent these to make them easy to talk about? Your tree structure is one way, but it might be simpler to put them into a matrix, where the intersection of two points represents the shortest known distance between the two points.


To start with, your matrix looks like this:
  
  A B C D E
A X X X X X 
B X X X X X 
C X X X X X 
D X X X X X 
E X X X X X 



(X represents "infinite distance" or "no known path as yet")

You can start by filling in the data that's already been given to you, and then see if you get any ideas on how to proceed. I suppose that step zero would be to fill in the points (A,A), (B,B), etc: you know that distance is zero. And you may assume for this problems that all paths are two-way, so really only half of the graph matters.

(yes, this does lead you to a solution, I promise! :) )

[EDIT: Or you could look up the known solution, if you want the work done for you...)

This post has been edited by jon.kiparsky: 07 September 2011 - 07:08 PM

Was This Post Helpful? 1
  • +
  • -

#4 NoDice  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-September 11

Re: Java recursion project

Posted 07 September 2011 - 07:23 PM

I did not really see a known solution and I need to actually learn something so I want to try to do as much of the work as I can manage.I am not trying to find a single path I am trying to find all paths, of any 5 cities a user puts in with X and Y coordinates.

so I am trying to find the distances between each city and the total of the following 6 paths

A B C D E
A B D C E
A C B D E
A C D B E
A D C B E
A D B C E

@macosxnerd101 is that basically going down each node of the tree and then back up like backtracking recursion?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,603
  • Joined: 27-December 08

Re: Java recursion project

Posted 07 September 2011 - 07:25 PM

Yes. That's it exactly.

Also, not sure if you'll find this relevant/helpful, but I figured I'd link it in case you did. I have a tutorial on trees, stacks, and recursion. Hopefully it helps some. :)
Was This Post Helpful? 0
  • +
  • -

#6 NoDice  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-September 11

Re: Java recursion project

Posted 07 September 2011 - 07:30 PM

Okay, thanks I'll give the tutorial a look and see if I can build some code off that psuedo code. I'm sure I'll be back :)
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7293
  • View blog
  • Posts: 12,132
  • Joined: 19-March 11

Re: Java recursion project

Posted 07 September 2011 - 07:54 PM

Okay, that's a similar problem, to the shortest path, so it's worth either solving that one or reading up on Dijkstra's algorithm for the approach, but it won't be just a simple modification.

The trick with recursion, I've always found, is to work it out backwards. This makes sense, really: look at the simplest case first, and work your way out from there.

The other trick with a problem like this is finding the right visualization. You should give some thought to how you're going to represent the problem, either in your head or on paper, before you try to write any code for it. The matrix that works well for finding the shortest path is less effective for finding all of the paths: you'll have to come up with another way of conceptualizing the problem.

Good luck - I look forward to seeing what you come up with.
Was This Post Helpful? 0
  • +
  • -

#8 NoDice  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 07-September 11

Re: Java recursion project

Posted 07 September 2011 - 10:30 PM

Hrm I don't know it seems to me that to properly navigate my objects like I want I would need to set up a tree unless I am missing something, to be honest I am not sure I fully understand macosxnerd101's psudeo code, So now I am thinking about trying to generate permutations of the middle three and do my math function on each permutation. I am looking at this source code: http://www.merriampark.com/perm.htm for some ideas and this is how I plan on pull my middle out.
	public void permCity(City[] AA)
	{
	
		City[] BB;//set up an array
		BB = new City[3];// limit length of array
		int i;
		for (i=0; i < 4; i++)//this takes the middle three cities and places them in thier own array
		{
			BB[i] = AA[i+1];
		}

	//permutation recursion goes here
				
	}



Meh, I am tired I'll have to work on this some more tomorrow.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1