Thread: Pascal Triangle

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    11

    Pascal Triangle

    Code:
    #include <stdio.h>
    
    int main() {
    
      int pascaltri[11][11];
      int r, c;
    
      // Initialize beginning and end of each 
      // row to 1.
      for (r=0; r<11; r++) {
        pascaltri[r][0] = 1;
        pascaltri[r][r] = 1;
      }
    
      // Fill in the table.
      for (r=2; r<11; r++)
        for (c=1; c<r; c++)
          pascaltri[r][c] = pascaltri[r-1][c-1]+
                            pascaltri[r-1][c];
    
      // Loop through each row of the table.
      for (r=0; r<11; r++) {
    
        // Loop through each value of the row.
        for (c=0; c<=r; c++) 
          printf("%4d ", pascaltri[r][c]);
      
        // Go to the next line.
        printf("\n");
      }
    
      return 0;
    }
    I am trying to figure out how this works, it is the code to pascal's triangle. I understand I am making a 11x11 triangle and the reason a 1 appears upfront and at the end of each line. I don't understand the part that fills in the lines.
    Code:
      for (r=2; r<11; r++)
        for (c=1; c<r; c++)
          pascaltri[r][c] = pascaltri[r-1][c-1]+
                            pascaltri[r-1][c];
    For the first line this fills in , is it doing this?

    r=2 c=1
    [2-1][1-1]+[2-1][1]

    [1][0]+[1][1]

    Im not sure what it is doing with that information from there. Can someone explain Also how does this cause multiple entries? Like in row 3, there is two numbers it is entering in.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Think of pascaltri as a grid. Each box is either referencing the columns or the rows. This:

    pascaltri[ rows ][ cols ]

    So when you start with 11,11, you're making a grid of 11 rows by 11 columns. In C, arrays go from 0 to size -1, which in this case means you can access each column or row in ranges of:

    0, 1, 2, 3, ... 8, 9, 10

    So:

    for( r = 2 <--- row = 2

    And:

    for( c = 1 <-- column = 1

    And you can think of it as:

    grid[ row ][ column ] = value of grid[ row something else ][ column something else ] + value of grid[ row thishere ][ column thatthere ]


    The rest is just a matter of grabbing a piece of graph paper, and working through it.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    11
    Row 0 ---- 1
    Row 1 ---- 1 1
    Row 2 ---- 1 X 1
    Row 3 ---- 1 _ _ 1

    Okay so the first part of that is using r=2 c=1

    grid[2][1] which is referring to the slot I put as a bold X. How does this come out to two?
    [1][0]+[1][1] = 2 ?

    Ah doh I am being slow. Is the [1][0] referring to the value at the red color and [1][1] at the blue color? That seems like it would answer my question xD


    One last question:

    When it continue on, does it go to [3][1] then [3][2] then [4][1]?

    What I mean is, does it go back up to this code:
    Code:
    for (r=2; r<11; r++)
        for (c=1; c<r; c++)
    Add 1 to r. Followed by resetting c=1 because its indented in(?). Then it keeps adding 1 to c until it no longer satisfies c<r?

    It's the only way I see that making this work. Why then wouldn't r reset to 2 every time then? (Or am I more than lost)
    Last edited by illidari; 05-03-2010 at 09:29 PM.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The first for loop runs from r=2 through r=10, and stops when r=11 (not executing its contents--the inner loop). It never resets to r=2, because the outer loop isn't in a loop. The initializer only happens at the start of the loop, not every increment.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Triangle Function
    By w2look in forum C Programming
    Replies: 14
    Last Post: 11-13-2010, 02:31 PM
  2. Clipping a Triangle of Digits
    By towely in forum C++ Programming
    Replies: 3
    Last Post: 10-26-2009, 07:00 AM
  3. pascal triangle
    By ndukaa1 in forum C++ Programming
    Replies: 15
    Last Post: 10-05-2004, 10:40 PM
  4. Pascal triangle numbers generation~
    By bljonk in forum C Programming
    Replies: 6
    Last Post: 03-22-2002, 02:25 PM
  5. Pascal Triangle
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2002, 01:34 PM