数据结构杨辉三角
时间: 2023-06-30 12:19:33 浏览: 58
杨辉三角是一种数学图形,它由数字组成,数字在三角形的第一行和最后一行都是1,其他位置上的数字是它正上方和左上方的两个数字之和。杨辉三角的一些性质被广泛应用于组合数学、概率论、统计学等领域。
杨辉三角的生成方式非常简单,可以用递推的方法实现。设杨辉三角的第i行第j个元素为S(i,j),则有:
S(i,j)=S(i-1,j-1)+S(i-1,j)
边界条件为:S(i,1)=S(i,i)=1
下面是用Python实现杨辉三角的代码:
```python
def generate_pascal_triangle(n):
triangle = [[1]]
for i in range(1, n):
row = [1]
for j in range(1, i):
row.append(triangle[i-1][j-1] + triangle[i-1][j])
row.append(1)
triangle.append(row)
return triangle
# 输出前10行杨辉三角
triangle = generate_pascal_triangle(10)
for row in triangle:
print(row)
```
输出结果如下:
```
[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]
```
这段代码中,我们定义了一个generate_pascal_triangle函数来生成杨辉三角。在函数内部,我们使用了一个二维列表triangle来存储杨辉三角的每一行,初始时只有第一行为[1]。然后我们循环生成每一行的元素,依据杨辉三角的递推公式,计算每个元素的值。最后将每一行的元素添加到triangle中,并返回triangle即可。
在主函数中,我们调用generate_pascal_triangle函数并输出前10行杨辉三角。
杨辉三角的生成方法简单而优雅,也是算法初学者学习递推算法的好例子。