having difficulty with this problem

This is a discussion on having difficulty with this problem within the A Brief History of Cprogramming.com forums, part of the Community Boards category; okay, I am doing this problem my friend gave me as a challenge and I want to convert it into ...

  1. #1
    Unregistered
    Guest

    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?

  2. #2
    Fingerstyle Guitarist taylorguitarman's Avatar
    Join Date
    Aug 2001
    Posts
    564
    Last edited by taylorguitarman; 03-24-2002 at 02:05 PM.
    If a tree falls in the forest, and no one is around to see it, do the other trees make fun of it?

  3. #3
    Unregistered
    Guest
    ok, how do I solve this problem using Pascal's Triangle algorithm?

  4. #4
    $null
    Guest
    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

  5. #5
    $null
    Guest
    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

  6. #6
    Unregistered
    Guest
    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

  7. #7
    Fingerstyle Guitarist taylorguitarman's Avatar
    Join Date
    Aug 2001
    Posts
    564
    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.
    Last edited by taylorguitarman; 03-28-2002 at 12:43 PM.
    If a tree falls in the forest, and no one is around to see it, do the other trees make fun of it?

  8. #8
    Unregistered
    Guest
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21