蓝桥杯杨辉三角python

### 蓝桥杯 杨辉三角 Python 实现 解题思路 杨辉三角是一种经典的组合数学结构，在蓝桥杯比赛中经常作为考察选手编程能力和逻辑思维的经典题目之一。以下是基于已有资料和专业知识总结的解题方法。 #### 1. 题目背景与定义 杨辉三角是一个由数字排列成的三角形数表，其中每一行的第一个和最后一个数字都是 `1`，其他位置上的数字等于其正上方两个数字之和[^2]。 具体来说，如果用二维数组表示杨辉三角，则有如下关系： \[ C(n,k) = C(n-1, k-1) + C(n-1, k) \] #### 2. 使用列表生成杨辉三角 可以通过嵌套列表的方式存储每层的结果，并逐步构建完整的杨辉三角。以下为一种常见的实现方式： ```python def generate_yanghui_triangle(num_rows): triangle = [] for i in range(num_rows): row = [None] * (i + 1) row[0], row[-1] = 1, 1 # 每一行首尾均为1 for j in range(1, i): row[j] = triangle[i-1][j-1] + triangle[i-1][j] triangle.append(row) return triangle num_rows = 5 result = generate_yanghui_triangle(num_rows) for row in result: print(row) ``` 上述代码通过逐层迭代完成杨辉三角的生成，时间复杂度为 \(O(n^2)\)[^3]。 #### 3. 利用对称性优化空间占用 由于杨辉三角具有对称性质，可以仅保存左半部分的数据来减少内存消耗。这种方法特别适用于大尺寸的杨辉三角计算场景。 ```python def optimized_yanghui_triangle(num_rows): half_triangle = [[1]] for i in range(1, num_rows): current_row = [1] previous_row = half_triangle[-1] for j in range(len(previous_row)-1): current_row.append(previous_row[j] + previous_row[j+1]) current_row.append(1) half_triangle.append(current_row[:len(current_row)//2 + 1]) # 只保留左侧 full_triangle = [] for idx, row in enumerate(half_triangle): mirrored_part = row[:-1].copy() mirrored_part.reverse() # 构造右侧镜像部分 full_triangle.append(row + mirrored_part) return full_triangle num_rows = 5 optimized_result = optimized_yanghui_triangle(num_rows) for row in optimized_result: print(row) ``` 此版本利用了杨辉三角的对称特性，减少了不必要的重复计算。 #### 4. 动态规划求特定项值 某些情况下可能只需要获取某一层或者某个具体的数值而无需整个三角形。此时可采用动态规划的思想单独处理目标数据点。 假设要查找第 n 行第 m 列的值（索引从零开始），则可以直接应用组合公式 \(C_n^m\) 计算得出结果而不必显式构造整张表格。 ```python from math import comb def get_value_in_yanghui_triangle(n, m): if m < 0 or m > n: raise ValueError("Invalid index") return comb(n, m) print(get_value_in_yanghui_triangle(5, 2)) # 输出对应位置的值 ``` 这里调用了标准库中的 `comb()` 函数简化操作过程。 --- ###