having difficulty with this problem

Printable View

03-24-2002
Unregistered

having difficulty with this problem

okay, I am doing this problem my friend gave me as a challenge and I want to convert it into code but it almost seems impossible to convert this problem into code to get the solution. any help or suggestions?

here is the problem:
we start from [start] and have to reach the destination [end] only by moving up and right. I cannot move down or left. how many different solutions are there?

Code:

____________ | end | | | | | | | | | | | | | | | __________| start

do I need to use some form of nested loop or is there some simple formula to solve this?
03-24-2002
taylorguitarman

This should help you out.
http://www.math.ilstu.edu/~day/cours....html#triangle
03-24-2002
Unregistered

ok, how do I solve this problem using Pascal's Triangle algorithm?
03-24-2002
$null

Quote:

Originally posted by Unregistered
ok, how do I solve this problem using Pascal's Triangle algorithm?

this is how it is done...

if you can move Right 8 times and Up 5 times you would do this

(8!*5!)/(8*5)

where 8! would be 8*7*6*5*4*3*2*1

that will give you the number of possible paths :P

hmmm thank god for calculus class hehe
03-24-2002
$null

assuming i understand your example this is how it would be done :P

Code:

____________ | end | 4| | | | 3| | | | 2| | | | 1| | 1__2_3__4_| start

im assuming from the diagram you can move Right 4 times and Up 4 times so the answer would be

(4!*4!)/(4*4) and therefore the answer would be 36 possible paths
03-28-2002
Unregistered

are you sure that is correct?

I just drew a chart using Pascal's Triangle algorithm and it turns out to be 70. (there are 5 rows and 5 columns by the way). I think the algorithm uses a combination. I don't understand how to turn this problem into code... or is it even possible? I only have a limited knowledge in math.

Code:

here is the diagram I made to solve this problem: 01 01 01 01 02 01 01 03 03 01 01 04 06 04 01 01 05 10 10 05 01 01 06 15 20 15 06 01 01 07 21 35 35 21 07 01 01 08 29 56 70 56 29 08 01 since it is a 5 * 5 square, I simplified the diagram (the square is rotated 45 degrees) 01 01 01 01 02 01 01 03 03 01 01 04 06 04 01 05 10 10 05 15 20 15 35 35 70
03-28-2002
taylorguitarman

Here's a link with an explanation (at the bottom of the page):
http://www-personal.engin.umich.edu/...592/node3.html

Summary: total paths = C( 2n - 2, n - 1 )
Edit: (using only norths and easts)

Here's your equation in expanded form so you can code it:
C( n, r ) = n! / ( r! * ( n - r )! )

in a k x k grid, the n would be ( 2k - 2 ) and the r would be ( k - 1 )
so a 5 x 5 becomes
C( 8, 4 ) = 70

Note: if you're interested in more stuff like this check out discrete mathematics or combinatorics. I think most CS degrees require taking a class in it. Pretty useful stuff in CS especially networking.
03-28-2002
Unregistered

thanks, taylorguitarman. I never knew this stuff was related to networking at all. anyway, I just finished the program but wasted a lot of time doing this even though I answered the problem already.