首页python杨辉三角蓝桥

python杨辉三角蓝桥

时间: 2025-03-05 17:39:56 浏览: 44

### Python 实现杨辉三角的蓝桥杯题目解法 #### 使用组合数计算方法一种高效的方法是通过组合数来构建杨辉三角。由于每一项都可以表示为组合数 C(n, k)，可以直接调用 `math.comb` 函数完成计算。 ```python from math import comb def pascals_triangle_combination(rows): result = [] for row_num in range(rows): # 利用组合公式C(n,k)=n!/(k!(n-k)!)生成每行数据 row = [comb(row_num, col) for col in range(row_num + 1)] result.append(row) return result ``` 这种方法简洁明了，适合处理较小规模的数据集[^2]。 #### 动态规划迭代算法考虑到性能优化以及内存占用，在实际竞赛中更推荐采用动态规划的方式逐层构造： ```python def pascals_triangle_dp(numRows): if numRows == 0: return [] triangle = [[1]] for i in range(1, numRows): prev_row = triangle[-1] new_row = [1] * (len(prev_row)+1) for j in range(1, len(new_row)-1): new_row[j] = prev_row[j-1]+prev_row[j] triangle.append(new_row) return triangle ``` 该方案不仅实现了完整的杨辉三角结构，而且遵循了其基本性质——每个数字等于上一行相邻两数值相加的结果[^4]。 #### 对称性剪枝技巧针对特定场景下的效率提升需求，可利用杨辉三角左右对称的特点仅保存并输出左侧部分即可满足要求: ```python def half_pascals_triangle(numRows): full_triangle = pascals_triangle_dp(numRows) half_result = [] for row in full_triangle: mid_point = len(row)//2+1 trimmed_row = row[:mid_point] half_result.append(trimmed_row) return half_result ``` 上述代码片段展示了如何基于前两种方法进一步简化存储空间的需求[^3]。

阅读全文