EFI interview - 1

题目：打印一个Pascal's Triangle（也称杨辉三角）。

解开这个题目，至少有三种方法。前两个方法可以在Wikipedia上面得到启示：http://en.wikipedia.org/wiki/Pascal's_triangle

1. 利用二项式展开的方法，启示杨辉三角的每一个元素都是二项式(x+y)^n的系数，可以用下面的公式来计算：

值得注意的是，如果行数从0算起，那么杨辉三角每一行的列数都等于行数+1。



2. 任意一行的任意一个元素，其实都是其所在的行数、列数以及其前一个元素的某种组合（函数）。
This algorithm is an alternative to the standard method of calculating individual cells with factorials. Starting at the left, the first cell's value v0 is 1. For each cell after, the value is determined by multiplying the value to its left by a slowly changing fraction:






where r = row + 1, starting with 0 at the top, and c = the column, starting with 0 on the left. For example, to calculate row 5, r = 6. The first value is 1. The next value is 1 × 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 × 4/2 = 10. Then 10 × 3/3 = 10. Then 10 × 2/4 = 5. Then 5 × 1/5 = 1. Notice that the last cell always equals 1, the final multiplication is included for completeness of the series.



3. 利用杨辉三角的一个重要性质：底下一个元素是其上一层两个元素之和。下面的代码是MITBBS的网友speeddy提供：

int p1[20];
memset(p1, 0, 20*4);
p1[0] = 1;

for(int i=0; i<10; i++) {
  int next = 0;
  int prev = 0;

  for (int j = 0; j < i+1; j++) {
    if (j == 0) {
      p1[j] = 1;
      prev = 1;
    } else if (j == i) {
      p1[j] = 1;
    } else {
      next = p1[j];
      p1[j] += prev;
      prev = next;
    }
    cout << p1[j] << " ";
  }
  cout << endl;
}

result:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1