 |  |  |  |  |  |  |  |
Need help with recursion and arrays
Please support our C++ advertiser: Intel Parallel Studio Home
 |
•
•
Join Date: Feb 2002
Posts: 12,035
Reputation: 
Solved Threads: 128
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:
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!
As you can see, the function we have to write is:
C++ Syntax (Toggle Plain Text)
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! 
>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.
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,035
Reputation:
Solved Threads: 128
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.
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?
Anyway, it's now almost 6 hours later and still nothing to show?
•
•
Join Date: Feb 2002
Posts: 12,035
Reputation:
Solved Threads: 128
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.
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. 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 ];
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,035
Reputation:
Solved Threads: 128
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?
I'm actually confused what you mean where you say that I'm never computing the path indexes?
Here's a snippet of your code:
x and y both go from 2..5 They skip 1! So path[1][y] and [x][1] values (10 total) are all random.
C++ Syntax (Toggle Plain Text)
|
Similar Threads
- help with recursion (C++)
Other Threads in the C++ Forum
- Previous Thread: Program for tollbooth simulation needed
- Next Thread: Tower Of Hanoi
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C++ Posts
- Today's Posts
- Unanswered Threads
api array based beginner binary c++ c/c++ calculator char char* class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news node numbertoword output parameter pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
