帕斯卡三角(Pascal's Triangle)是一个三角形数组,其中每个数字是其上方两个数字之和。它的每一行代表二项式系数,常用于组合数学和概率论中。
帕斯卡三角有多种类型,包括:
def generate_pascals_triangle(num_rows):
triangle = []
for row_num in range(num_rows):
# The first and last row elements are always 1.
row = [None for _ in range(row_num + 1)]
row[0], row[-1] = 1, 1
# Each triangle element is equal to the sum of the elements
# above-and-to-the-left and above-and-to-the-right.
for j in range(1, len(row) - 1):
row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]
triangle.append(row)
return triangle
# 生成前5行的帕斯卡三角
num_rows = 5
pascals_triangle = generate_pascals_triangle(num_rows)
for row in pascals_triangle:
print(row)
原因:在初始化每一行时,使用了 None
来占位。
解决方法:初始化时使用 0
或直接使用列表推导式来避免空值。
def generate_pascals_triangle(num_rows):
triangle = []
for row_num in range(num_rows):
row = [1] * (row_num + 1)
for j in range(1, len(row) - 1):
row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]
triangle.append(row)
return triangle
原因:每次生成新行时都需要遍历上一行,效率较低。 解决方法:使用动态规划的思想,只保留必要的行数据。
def generate_pascals_triangle(num_rows):
if num_rows == 0:
return []
triangle = [[1]]
for row_num in range(1, num_rows):
row = [1]
last_row = triangle[-1]
for j in range(1, row_num):
row.append(last_row[j - 1] + last_row[j])
row.append(1)
triangle.append(row)
return triangle
通过以上方法,可以有效地生成和优化帕斯卡三角的输出。
领取专属 10元无门槛券
手把手带您无忧上云