PDA

View Full Version : having difficulty with this problem



Unregistered
03-24-2002, 02:02 PM
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?



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



do I need to use some form of nested loop or is there some simple formula to solve this?

taylorguitarman
03-24-2002, 03:00 PM
This should help you out.
http://www.math.ilstu.edu/~day/courses/old/305/contenttotalarrangements.html#triangle

Unregistered
03-24-2002, 06:17 PM
ok, how do I solve this problem using Pascal's Triangle algorithm?

$null
03-24-2002, 07:35 PM
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

$null
03-24-2002, 07:41 PM
assuming i understand your example this is how it would be done :P



____________
| 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

Unregistered
03-28-2002, 12:50 PM
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.




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

taylorguitarman
03-28-2002, 01:32 PM
Here's a link with an explanation (at the bottom of the page):
http://www-personal.engin.umich.edu/~tpkelly/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.

Unregistered
03-28-2002, 11:09 PM
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.