我对寻找帕斯卡三角形的第n行感兴趣(不是一个特定的元素,而是整个行本身)。最有效的方法是什么?
我考虑了构建三角形的传统方法,通过对上一行中相应元素求和,这将需要:
1 + 2 + .. + n = O(n^2)
另一种方法可以是使用特定元素的组合公式:
c(n, k) = n! / (k!(n-k)!)
对于行中的每个元素,我猜想这种方法可能需要比前一种方法更长的时间,取决于计算组合的方式。有什么想法吗?
我对寻找帕斯卡三角形的第n行感兴趣(不是一个特定的元素,而是整个行本身)。最有效的方法是什么?
我考虑了构建三角形的传统方法,通过对上一行中相应元素求和,这将需要:
1 + 2 + .. + n = O(n^2)
另一种方法可以是使用特定元素的组合公式:
c(n, k) = n! / (k!(n-k)!)
>>> 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)
。
const pascal = n => {
let line = [1];
for (k in _.range(n)) {
line.push(line[k] * (n-k) / (k+1));
}
return line;
};
有人知道为什么吗? - Nima Mehanianrange(n // 2)
和 return line + line[(n - 1) // 2::-1]
,这段代码的运行速度将会快两倍(使用 timeit
进行计时)。 - Harvey单行计算如下:
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
最有效的方法是:
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;
}
row.resize(n+1)
。 - DarkZerosrow[i-1]
乘以 (n-i+1)/i
? - user248884这是一个用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我会在Shane的出色工作基础上为R解决方案进行补充建设。非常感谢你,Shane!他生成三角形的代码如下:
pascalTriangle <- function(h) {
lapply(0:h, function(i) choose(i, 0:i))
}
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。一切都很好!
[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)
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:否则,我们得到当前列前一列和当前行前一行的重复帕斯卡之和;以及该列和当前行前一行的帕斯卡。祝好运。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]
。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))
1 + 2 + .. + n = n*(n + 1)/2
,这仍然是**n^2
**。 - Joseph Wood这是使用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`
C(n,k-1)
等时,可能有一种简单的方法来计算C(n,k)
。 - none