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.