DaniWeb Forum Index > Software Development > C++

C++ RSS

Need help with recursion and arrays

•

Join Date: Feb 2002

Posts: 12,024

Reputation: cscgal is a glorious beacon of light

Solved Threads: 126

cscgal

Offline

The Queen of DaniWeb

Need help with recursion and arrays

Nov 14th, 2004

Hey everyone. I actually have a homework assignment that is due Tuesday afternoon that I've been struggling all weekend with. The assignment is located at: http://cs.hofstra.edu./~cscsxd/hofst.../Recursion.cpp

As you can see, the function we have to write is:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
				   int r[][6], int a[][6])
{
	// please fill in your code here and remove the statement return -1;
	// return -1;
}
int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy, 
				   int r[][6], int a[][6])
{
	// please fill in your code here and remove the statement return -1;
	// return -1;
}

I understand the algorithm to use in the sense that I can explain it on paper. But I am confused how to actually translate it into code given the professor's function prototype. What exactly are we returning as a pointer to an integer? Are we making changes to the two arrays that are passed in with each iteration?

From what I see, we are doing ...

Initially pass in 1,1 to start and 5,5 to end with both arrays
Try going to 1,2 and to 2,1, and decide which is better
After picking the one that is better, recursively go back to 1,1->1,2->1,3 or 2,2 ... and the same for the other coordinate ...

Oh wait, I'm screwed up again. Maybe I don't understand this at all

It would be fantastic if someone could give me a hand with this, because I'm very confused. Thanks!

Dani the Computer Science Gal

Follow my Twitter feed! twitter.com/daniweb

•

Join Date: Sep 2004

Posts: 7,540

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Need help with recursion and arrays

Nov 15th, 2004

>What exactly are we returning as a pointer to an integer?
The shortest path, basically an array of x,y pairs.

>Are we making changes to the two arrays that are passed in with each iteration?
No, those arrays simply tell you what the distance between two points is.

>Try going to 1,2 and to 2,1, and decide which is better
Or you could walk each path in turn and collect the total distances. Then simply choose the shortest path from that collection. I'll leave it up to you to figure out if that's a good solution or not.

I'm here to prove you wrong.

•

Join Date: Feb 2002

Posts: 12,024

Reputation: cscgal is a glorious beacon of light

Solved Threads: 126

cscgal

Offline

The Queen of DaniWeb

Re: Need help with recursion and arrays

Nov 17th, 2004

Hey there Narue. I spoke to my professor and it appears the reason I was stumped was because I misread the question!! It turns out we don't have to use recursion afterall! I have also opted to solve the problem in a similar way as you described (collecting distances one row at a time.) I'm working on the problem right now, and I'll have something that I can show here in about an hour.

Dani the Computer Science Gal

Follow my Twitter feed! twitter.com/daniweb

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 10

Chainsaw

Offline

Unprevaricator

Re: Need help with recursion and arrays

Nov 18th, 2004

We don't do your homework for you.

HA HA HA HA HA :-)

(Sorry, I couldn't resist)

•

Join Date: Nov 2004

Posts: 6,145

Reputation: jwenting is just really nice

Solved Threads: 212

jwenting

Offline

duckman

Re: Need help with recursion and arrays

Nov 18th, 2004

Muaha. Dani didn't ask for anyone to do her homework, only for hints to get started

Anyway, it's now almost 6 hours later and still nothing to show?

•

Join Date: Feb 2002

Posts: 12,024

Reputation: cscgal is a glorious beacon of light

Solved Threads: 126

cscgal

Offline

The Queen of DaniWeb

Re: Need help with recursion and arrays

Nov 20th, 2004

Sorry, I have just been so busy I haven't had a chance to update this thread. I'm attaching what I have so far. It works up until the point where it populates the array that the function returns. In other words, it correctly computes the shortest path and prints it out as it goes. But then it screws up filling the data it computed into the array. At this point I'm just looking for some help finishing it up

I'm pretty sure it's just a one-line typo somewhere in my last loop. If you run the file you should see what I'm talking about. Unfortunately, for some reason, I can get the thing to compile on my Windows machine in VS.NET but not by using gcc on my mac

I think it's just some quirk.

Attached Files

Recursion.cpp (8.8 KB, 15 views)

Dani the Computer Science Gal

Follow my Twitter feed! twitter.com/daniweb

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 10

Chainsaw

Offline

Unprevaricator

Re: Need help with recursion and arrays

Nov 20th, 2004

I see a couple of things, though I can't claim to understand what is being attempted (heck, back in 1977 when I took CS classes, rectangles only had 3 sides! What we would have GIVEN for a 4-sided rectangle! You kids today... )

1) shortest_path is allocated at 8 ints (0.7) but you use 9 positions; n ends up as 9 (so 0..8 are filled in). Not exactly sure why, but....

2) you don't compute paths indexes 0 or 1 (0,0 0,1 1,0 1,1), yet you reference them when building shortest_path! Because you decrement the x or y value before fetching it to fill in shortest_path, you decrement x or y down to 0.

I moved setting shortest_path to the TOP of the while loop, and that seemed to help, but you still have to fix the setting of paths[] so it fills in the first entry (1,n and n,1)

(oh, and VC++ bitches about declaring x more than once)

(note: at some point you'll want to delete [] shortest_path in main())

(note: in cases where you use a simple 2 dimension array like this and don't want to add the complexity of a class or ugly macros, pick some size that is "larger than you'll ever need" (you picked 10 that might be fine), and then add asserts to make sure you don't blow the size. Here's an example:

static const int kArraySize = 10; // Naru would complain about static being deprecated, but heck this is my example code! :=)

assert( (endx < kArraySize) && (endy < kArraySize) ); // if this fires, kArraySize may need to be bumpped up!

int distance[ kArraySize ][ kArraySize ];

•

Join Date: Feb 2002

Posts: 12,024

Reputation: cscgal is a glorious beacon of light

Solved Threads: 126

cscgal

Offline

The Queen of DaniWeb

Re: Need help with recursion and arrays

Nov 20th, 2004

Hey there Chainsaw. Thanks for the comments. As for deleting shortest_path in main ... the professor actually wrote that part. It was only our job to fill in the actual function. Also, since this program was mainly just to make sure we understood the algorithm, I'm not concerning myself with the technicalities of dynamically generating the array. But, yes, I used a size of [10][10] because that is larger than I ever plan on needing.

I'm actually confused what you mean where you say that I'm never computing the path indexes?

Dani the Computer Science Gal

Follow my Twitter feed! twitter.com/daniweb

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 10

Chainsaw

Offline

Unprevaricator

Re: Need help with recursion and arrays

Nov 20th, 2004

Here's a snippet of your code:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
	for (y=starty+1; y<=endy; y++)	// go down each column
	{
		for (x=startx+1; x<=endx; x++)	// go across each row
		{
			int distance_up = distance[x][y-1] + a[x][y-1];			// calculate weight to get to (x,y) from coordinate below it
			int distance_right = distance[x-1][y] + r[x-1][y];		// calculate weight to get to (x,y) from coordinate to left of it
			if (distance_up < distance_right)	// it's better to move up
			{
				distance[x][y] = distance_up;		// populate our distance array
				path[x][y] = 1;						// populate our path array
				cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
			else								// it's better to move right
			{
				distance[x][y] = distance_right;	// populate our distance array
				path[x][y] = 0;						// populate our path array
				cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
		}
	}
	for (y=starty+1; y<=endy; y++)	// go down each column
	{
		for (x=startx+1; x<=endx; x++)	// go across each row
		{
			int distance_up = distance[x][y-1] + a[x][y-1];			// calculate weight to get to (x,y) from coordinate below it
			int distance_right = distance[x-1][y] + r[x-1][y];		// calculate weight to get to (x,y) from coordinate to left of it
			if (distance_up < distance_right)	// it's better to move up
			{
				distance[x][y] = distance_up;		// populate our distance array
				path[x][y] = 1;						// populate our path array
				cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
			else								// it's better to move right
			{
				distance[x][y] = distance_right;	// populate our distance array
				path[x][y] = 0;						// populate our path array
				cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
			}
		}
	}

x and y both go from 2..5 They skip 1! So path[1][y] and [x][1] values (10 total) are all random.

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 10

Chainsaw

Offline

Unprevaricator

Re: Need help with recursion and arrays

#10

Nov 20th, 2004

And I wasn't advocating more complicated arrays, but you had this comment in the code:

// I could find no easy way to dynamically create a 2D array in C++

So I couldn't resist opening my big mouth about it. :-)