如何高效地计算帕斯卡三角形中的一行?

50

我对寻找帕斯卡三角形的第n行感兴趣(不是一个特定的元素,而是整个行本身)。最有效的方法是什么?

我考虑了构建三角形的传统方法,通过对上一行中相应元素求和,这将需要:

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

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

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

对于行中的每个元素,我猜想这种方法可能需要比前一种方法更长的时间,取决于计算组合的方式。有什么想法吗?

3
你提出的第一种方法是数学上的无稽之谈,所以肯定选择第二种。 - Pieter Geerkens
@ZiyaoWei 你可能是对的,但我还没有看到背后的直觉。当你知道 C(n,k-1) 等时,可能有一种简单的方法来计算 C(n,k) - none
@PieterGeerkens 我向您保证这不是一份作业,但如果您觉得它是,请忽略这个问题。 - none
只需展开组合数公式C(n,k),就很容易找到答案。 - zw324
@ZiyaoWei,公式在问题中不是已经展开了吗?你是在说另一种展开方式吗? - none
显示剩余4条评论
14个回答

118
>>> 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)


1
你能详细说明一下答案吗?结果看起来正确,时间复杂度似乎是O(n),但是这个算法是如何工作的呢? - none
71
@H2CO3:这是我写答案的最有效方法;-) - Omri Barel
2
这里有一个稍微详细的解释:http://en.wikipedia.org/wiki/Pascal%27s_triangle#Calculating_a_row_or_diagonal_by_itself - jm0
将其翻译成JS不起作用...const pascal = n => { let line = [1]; for (k in _.range(n)) { line.push(line[k] * (n-k) / (k+1)); } return line; };有人知道为什么吗? - Nima Mehanian
通过更改为 range(n // 2)return line + line[(n - 1) // 2::-1],这段代码的运行速度将会快两倍(使用 timeit 进行计时)。 - Harvey
显示剩余2条评论

14

单行计算如下:

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

你在谈论我在问题中提到的第二种方法。我没有看到你的回答与效率有任何关系。 - none
1
@gokcehan:不是。你检查过代码了吗?它基本上和你选择的答案一样! - Knoothe
现在我理解了这个算法,我看到这也是正确的答案。很抱歉,你得到了我的+1。 - none
1
@gokcehan:不用担心。我可能没有表达清楚(已经编辑了帖子以使其更加明确)。 - Knoothe

10

最有效的方法是:

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;
}

1
该行必须有n+1个元素,因此最后的“for”循环应该具有“i<=n”的条件。 - Bianca Daniciuc
我真的不记得这个算法了。但我猜你是对的,因为 row.resize(n+1) - DarkZeros
你为什么要将 row[i-1] 乘以 (n-i+1)/i - user248884
每个值都是前一个值乘以(n-i),再除以i。这来自于阶乘展开式,每个项与前一个项非常相似,在阶乘的下部分有1个额外/1个较少的项。 因此,对于第10行(如果您计算第0行,则为第9行),首先是10/1,然后是9/2,然后是8/3...等等。这样就产生了1、10、45、120、210、252。 - DarkZeros
当n为30时,即大数时,这个失败了。 - Adam Mendoza
1
你应该将变量增加到 "uint64_t",以便在第30行中具有足够大的数字范围。 - DarkZeros

4

这是一个用Go语言实现的快速示例,它从一行的外缘开始计算,然后逐步向中间赋值两个值,只需进行一次计算...

package main

import "fmt"

func calcRow(n int) []int {
    // row always has n + 1 elements
    row := make( []int, n + 1, n + 1 )

    // set the edges
    row[0], row[n] = 1, 1

    // calculate values for the next n-1 columns
    for i := 0; i < int(n / 2) ; i++ {
        x := row[ i ] * (n - i) / (i + 1)

        row[ i + 1 ], row[ n - 1 - i ] = x, x
    }

    return row
}

func main() {
    for n := 0; n < 20; n++ {
        fmt.Printf("n = %d, row = %v\n", n, calcRow( n ))
    }
}

运行20次的输出大约需要1/4毫秒时间...

n = 0, row = [1]
n = 1, row = [1 1]
n = 2, row = [1 2 1]
n = 3, row = [1 3 3 1]
n = 4, row = [1 4 6 4 1]
n = 5, row = [1 5 10 10 5 1]
n = 6, row = [1 6 15 20 15 6 1]
n = 7, row = [1 7 21 35 35 21 7 1]
n = 8, row = [1 8 28 56 70 56 28 8 1]
n = 9, row = [1 9 36 84 126 126 84 36 9 1]
n = 10, row = [1 10 45 120 210 252 210 120 45 10 1]
n = 11, row = [1 11 55 165 330 462 462 330 165 55 11 1]
n = 12, row = [1 12 66 220 495 792 924 792 495 220 66 12 1]
n = 13, row = [1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1]
n = 14, row = [1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1]
n = 15, row = [1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1]
n = 16, row = [1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1]
n = 17, row = [1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1]
n = 18, row = [1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1]
n = 19, row = [1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1]

为什么要将 row[i] 乘以 (n - i) / (i + 1)?这是一个二项式恒等式吗? - user248884

1

我会在Shane的出色工作基础上为R解决方案进行补充建设。非常感谢你,Shane!他生成三角形的代码如下:

pascalTriangle <- function(h) {
  lapply(0:h, function(i) choose(i, 0:i)) 
}

这将允许我们将三角形存储为列表。然后,我们可以索引任何所需的行。但是请在索引时添加 1 !例如,我将获取底部行:
pt_with_24_rows <- pascalTriangle(24)
row_24 <- pt_with_24_rows[25] # add one
row_24[[1]] # prints the row

output

所以,假设我有一个高尔顿板问题。 我面临的任意挑战是找出聚集在中心的豆子百分比:例如,第10到15个箱子(共25个)。

sum(row_24[[1]][10:15])/sum(row_24[[1]]) 

这段文本是关于编程的,保留了HTML标记:

计算结果为0.7704771。一切都很好!


1
一个简单的计算方法是注意到下一行的元素可以通过前一行的两个相邻元素之和来计算。
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

例如6 = 5 + 115 = 5 + 101 = 1 + 020 = 10 + 10。这提供了一个简单的算法来从前一行计算下一行。
def pascal(n):
    row = [1]
    for x in xrange(n):
        row = [l + r for l, r in zip(row + [0], [0] + row)]
    # print row
    return row

print pascal(10)

1
在Scala编程中:我会简单地这样做:
def pascal(c: Int, r: Int): Int = c match {
    case 0 => 1
    case `c` if c >= r => 1
    case _ => pascal(c-1, r-1)+pascal(c, r-1)
}

我会把它称为“内部调用”:
for (row <- 0 to 10) {
    for (col <- 0 to row)
        print(pascal(col, row) + " ")
    println()
}

结果为:

. 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 1 10 45 120 210 252 210 120 45 10 1

逐步解释如下:

步骤1:如果我们的列是第一列,我们始终返回数字1。

步骤2:由于每个第X行有X个列。因此我们说:如果最后一列X大于或等于第X行,则返回数字1。

步骤3:否则,我们得到当前列前一列和当前行前一行的重复帕斯卡之和;以及该列和当前行前一行的帕斯卡。祝好运。

1
关于计算第_n_行所需的时间和内存,您有什么评论吗?这与之前提出的方法相比如何?如果乘法比加法慢31倍,是否会有任何变化? - greybeard

0
在Ruby中,以下代码将打印出您想要的Pascal三角形的特定行:
def row(n)
  pascal = [1]
  if n < 1
    p pascal
    return pascal
  else
    n.times do |num|
      nextNum = ((n - num)/(num.to_f + 1)) * pascal[num]
      pascal << nextNum.to_i
    end
  end
  p pascal
end

在编程中,调用row(0)会返回[1],而调用row(5)会返回[1, 5, 10, 10, 5, 1]

0
这是一个Python中O(n)空间复杂度的解决方案:
def generate_pascal_nth_row(n):
    result=[1]*n
    for i in range(n):
        previous_res = result.copy()
        for j in range(1,i):
            result[j] = previous_res[j-1] + previous_res[j]
    return result

print(generate_pascal_nth_row(6))

这个程序为什么是O(n)的?我看到了两个for循环。如果你认为是因为第二个循环不是每次都执行n次,那我觉得不是这样的。可以看到:1 + 2 + .. + n = n*(n + 1)/2 ,这仍然是**n^2**。 - Joseph Wood
1
我提到了O(n)的“空间”。你是对的,时间复杂度是O(n^2)。 - prafi

0

这是使用VBA动态设计Pascal三角形的另一种最佳简单方法。

`1
11
121
1331
14641`

`Sub pascal()
Dim book As Excel.Workbook
Dim sht As Worksheet
Set book = ThisWorkbook
Set sht = book.Worksheets("sheet1")
a = InputBox("Enter the Number", "Fill")
For i = 1 To a
    For k = 1 To i
        If i >= 2 And k >= 2 Then
            sht.Cells(i, k).Value = sht.Cells(i - 1, k - 1) + sht.Cell(i-  1, k)
        Else
            sht.Cells(i, k).Value = 1
        End If
    Next k
Next i
End Sub`

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接