Given two points (x0,y0) and (x1,y1) on the x-y plane. In a north-east
path from (x0,y0) to (x1,y1), one may walk only to the north (up) and to
the east (right). Write a program to count the number of northeast paths
from one point to another.
any ideas how to start this ???
Post an example with real numbers. What if the northeast parth is not the best solution?
(0, 0) <-----> (10, 0)
In the example above, you do not need to walk northeast. Just walk east!
Kuphryn
You're not finding the best path, you're counting the number of paths.
In your example it would return 1.
If it was going from (0, 0) to (2, 2), it would be 6 different paths.
A non-recursive way to calculate it would be:Code:NNEE NENE NEEN ENEN ENNE EENN
And if deltaX or deltaY is 0, the result is always 1.Code:(deltaX + deltaY)! / (deltaX! * deltaY!)
Last edited by XSquared; 06-05-2003 at 03:09 PM.
Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah
You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie
I dont know .. that is what he gave us to work with ... I have no idea what any of the code should look like though ... any suggestions?
Here's some pseudocode for the recursive function to get you started:
Code:function recurse takes 2 parameters( x and y ) declare a variable to hold the number of possibilities = 0 if the x and y coordinates are the final coordinates then return 1 end if if the x coordinate is not the same as x2 then call the function again, with x+1 and y as the parameters add the return value to the number of possibilities end if if the y coordinate is not the same as y2 then call the function again, with x and y+1 as the parameters add the return value to the number of possibilities end if return the number of possibilities end function
Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah
You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie
OK .. i understand what you are saying here .. but what is the actual code for the if statement ?? I am new to recursion .. any help is GREATLY APPRECIATED!!!
I find that creating recursive functions can be VERY unstable and put a heavier load on the processor depending on what your calculating, so always make sure that a recursive function is the best method for what you are doing.
"What are you after - the vague post of the week award?" - Salem
IPv6 Ready.
Travel the world, meet interesting people...kill them.
Trying to fix or change something, only guaruntees and perpetuates its existence.
I don't know about angels, but it is fear that gives men wings.
The problem with wanting something is the fear of losing it, or never having it. The thought makes you weak.
E-Mail Xei
Yeah, the call stack on recursive functions can sometimes be absurd.
Often recursive methods are used in teaching (as they do involve very important principles), but are avoided for the reasons Xei mentioned. Unless you know that the depth of recursion will be fairly low, I'd try to avoid it in practice.
Try to work out the code from XSquared's pseudocode. If your still having problems, post what you have so we can help.
Cheers
The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.
