如何有效地计算pascal三角形中的行？

Question

我有兴趣找到第n行pascal三角形(不是特定元素,而是整行本身).最有效的方法是什么？

我想到了通过总结上面行中相应元素来构造三角形的传统方法:

1 + 2 + .. + n = O(n^2)

另一种方法可能是使用特定元素的组合公式:

c(n, k) = n! / (k!(n-k)!)

对于行中的每个元素,我认为根据计算组合的方式,前一种方法需要更多时间.有任何想法吗？

Answer 1

>>> def pascal(n):
...   line = [1]
...   for k in range(n):
...     line.append(line[k] * (n-k) / (k+1))
...   return line
... 
>>> pascal(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

这使用以下标识:

C(n,k+1) = C(n,k) * (n-k) / (k+1)

因此,您可以C(n,0) = 1使用此标识开始,然后使用此标识计算其余行,每次将前一个元素乘以(n-k) / (k+1).

Answer 2

单行可以计算如下:

First compute 1.               -> N choose 0
Then N/1                       -> N choose 1
Then N*(N-1)/1*2               -> N choose 2
Then N*(N-1)*(N-2)/1*2*3       -> N choose 3
.....

请注意,您可以通过将一个数字乘以一个数字然后除以另一个数字来计算前一个值的下一个值.

这可以在单个循环中完成.示例python.

def comb_row(n):
   r = 0
   num = n
   cur = 1
   yield cur
   while r <= n:
      r += 1  
      cur = (cur* num)/r
      yield cur
      num -= 1

Answer 3

最有效的方法是:

std::vector<int> pascal_row(int n){
    std::vector<int> row(n+1);
    row[0] = 1; //First element is always 1
    for(int i=1; i<n/2+1; i++){ //Progress up, until reaching the middle value
        row[i] = row[i-1] * (n-i+1)/i;
    }
    for(int i=n/2+1; i<=n; i++){ //Copy the inverse of the first part
        row[i] = row[n-i];
    }
    return row;
}