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

Question

我感興趣的是找到第三排帕斯卡三角形（不是一個特定的元素，但整個行本身）。什麼是最有效的方法呢？

我考慮構建通過累加該行中的對應元件的三角形常規方式上方將採取：

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

注意，您可以從以前的值計算下一個值，只用一個數字multipyling，然後由另一數目來。

這可以在一個循環中完成。示例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; 
} 

Answer 4

這裏是去浪實現了快速的例子，從行的外邊緣計算和運作它的方式向中間分配兩個值與單一的計算...

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] 

Answer 5

最有效的方法來計算楊輝三角的一排是通過卷積。首先，我們選擇第二行（1,1）作爲內核，然後爲了獲得下一行，我們只需要將curent行與內核進行卷積。

因此，與第二行內核的卷積給出了第三排[1 1]*[1 1] = [1 2 1]，卷積與第三行給出第四[1 2 1]*[1 1] = [1 3 3 1]等

這是朱莉婭 - 郎功能（MATLAB非常simular）：

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 

Answer 6

一種簡單的方法來計算它是通過注意到下一行的元件可與前行中的兩個連續的元素的總和來計算。

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

例如6 = 5 + 1，15 = 5 + 10，1 = 1 + 0和20 = 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) 

Answer 7

在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]

Answer 8

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

步驟2：由於每個第X個行有列的X數目。所以我們這麼說;最後一列X大於或等於X個行，則返回圖1

第3步：否則，我們就在當前之前得到列的重複帕斯卡的總和和當前行之前的行;以及該列和該行之前的行的pascal。

祝你好運。

Answer 9

這是使用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` 

Answer 10

我用的Ti-84 + 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–>L1(R+1) 
:End 
:Disp L1 

這是我能想到的最快的方式做到這一點編程（與TI 84），但如果你的意思是要能夠使用筆和紙計算行，然後只是繪製出三角因爲做事實是一種痛苦！

Answer 11

下面是一個爲O​​（n）在Python空間複雜度的解決方案：

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