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.

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.

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)

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.