46

我有兴趣找到帕斯卡三角形的第 n 行（不是特定元素，而是整行本身）。最有效的方法是什么？

我考虑了通过总结上面行中的相应元素来构造三角形的传统方法，这将采取：

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

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

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

对于行中的每个元素，我猜前一种方法会花费更多时间，具体取决于计算组合的方式。有任何想法吗？

4

14 回答 14

109 
>>> 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).

于 2013-03-22T21:48:22.487 回答
13

单行可以计算如下：

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
.....

请注意，您可以从前一个值计算下一个值，只需乘以一个数字，然后除以另一个数字。

这可以在一个循环中完成。示例蟒蛇。

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
于 2013-03-22T21:48:34.497 回答
9

最有效的方法是：

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;
}
于 2013-11-08T10:23:24.920 回答
3

这是一个在 go-lang 中实现的快速示例，它从一行的外边缘计算，并通过一次计算向中间分配两个值...

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]
于 2015-11-14T18:20:43.693 回答
2

计算它的一种简单方法是注意下一行的元素可以计算为前一行中两个连续元素的总和。

[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

例如6 = 5 + 1,和。15 = 5 + 10_ 这给出了一个简单的算法来计算前一行的下一行。1 = 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)
于 2015-11-30T07:30:26.577 回答
2

在 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 步：否则，我们得到当前列之前的列和当前列之前的行的重复帕斯卡之和；以及该列的帕斯卡和当前行之前的行。

祝你好运。

于 2016-11-11T22:06:42.393 回答
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

输出

所以，最后，假装我有一个高尔顿板问题。我面临着找出聚集在中心的豆子百分比的任意挑战：比如，10 到 15 箱（25 箱中）。

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

结果是0.7704771。都好！

于 2019-05-30T13:19:45.570 回答
0

计算帕斯卡三角形中一行的最有效方法是通过卷积。首先，我们选择第二行 (1,1) 作为内核，然后为了获得下一行，我们只需要将当前行与内核进行卷积。

所以内核与第二行的[1 1]*[1 1] = [1 2 1]卷积得到第三行，与第三行的卷积得到第四行[1 2 1]*[1 1] = [1 3 3 1]，依此类推

这是 julia-lang 中的一个函数（与 matlab 非常相似）：

function binomRow(n::Int64)
baseVector = [1] #the first row is equal to 1. 
kernel = [1,1]   #This is the second row and a kernel. 
row = zeros(n)
for i = 1 : n
    row = baseVector 
    baseVector = conv(baseVector, kernel) #convoltion with kernel
end
return row::Array{Int64,1}
end
于 2015-11-19T17:31:13.933 回答
0

在 Ruby 中，以下代码将打印出您想要的帕斯卡三角形的特定行：

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]

于 2016-09-20T19:25:39.897 回答
0

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

`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`
于 2017-01-20T10:38:23.010 回答
0

我用的是 Ti-84 Plus CE

第6行中->的使用是储值按钮

Forloop syntax is 
:For(variable, beginning, end [, increment])
:Commands
:End

nCr syntax is 
:valueA nCr valueB

列表索引从 1 开始，所以我将它设置为 R+1

N= row
R= column

PROGRAM: PASCAL
:ClrHome
:ClrList L1
:Disp "ROW
:Input N
:For(R,0,N,1)
:N nCr R–&gt;L1(R+1)
:End
:Disp L1

这是我在编程中能想到的最快方法（使用 ti 84），但如果您的意思是能够使用笔和纸计算行，那么只需画出三角形，因为做因式很痛苦！

于 2017-05-04T03:00:06.463 回答
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))
于 2018-01-11T20:04:07.107 回答
0

要找到第 n 行 -

int res[] = new int[n+1];
res[0] = 1;
for(int i = 1; i <= n; i++)
   for(int j = i; j > 0; j++)
      res[j] += res[j-1];
于 2020-05-02T04:36:00.487 回答
0 
class Solution{
    public:
    
    int comb(int n,int r){
        long long c=1;
        for(int i=1;i<=r;i++) {   //calculates n!/(n-r)!
            c=((c*n))/i;  n--;
        }
        return c;
    }

    vector<int> getRow(int n) {  
        vector<int> v;
        for (int i = 0; i < n; ++i)
            v.push_back(comb(n,i));
        return v;
    }
};

超过 100% 提交 leet 代码https://leetcode.com/submissions/detail/406399031/

于 2020-10-09T03:40:39.427 回答