蓝桥杯杨辉三角

### 蓝桥杯 杨辉三角 题目 解法 #### 使用二维数组实现杨辉三角 一种常见的方式是通过二维数组存储并计算杨辉三角中的每一项。这种方法直观易懂，适合初学者理解杨辉三角的结构及其生成逻辑。对于第 `i` 行和第 `j` 列的位置 `(i, j)` 的值可以通过前一行的数据得出： \[ \text{triangle}[i][j] = \text{triangle}[i-1][j-1] + \text{triangle}[i-1][j] \] 此方法的时间复杂度较高，但由于蓝桥杯题目通常涉及较小规模输入，因此可以接受[^2]。 ```python def generate_pascals_triangle(n): triangle = [[0 for _ in range(i+1)] for i in range(n)] for i in range(n): triangle[i][0] = 1 # 每行的第一个元素为1 triangle[i][-1] = 1 # 每行的最后一个元素为1 for j in range(1, i): # 计算中间的值 triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] return triangle n = 5 result = generate_pascals_triangle(n) for row in result: print(row) ``` --- #### 只保存左半部分优化空间 由于杨辉三角具有对称性，仅需保存左侧的有效数据即可减少内存消耗。这一特性使得我们可以进一步降低算法的空间复杂度至 \(O(\frac{n^2}{2})\) 或更低[^1]。 ```python def half_pascals_triangle(n): triangle = [] for i in range(n): current_row = [1] * (i + 1) for j in range(1, i//2 + 1): val = triangle[i-1][j-1] + triangle[i-1][j] current_row[j] = val if j != i - j: # 对于非完全对称的部分填充右侧 current_row[-j-1] = val triangle.append(current_row[:len(current_row)//2 + 1]) return triangle half_result = half_pascals_triangle(5) print(half_result) ``` --- #### 动态规划与双数组交替更新 另一种高效的解决方案是采用两个一维数组分别表示当前层和下一层的状态，并动态更新这些数组的内容。这种方式不仅节省了大量不必要的存储开销，还能够显著提升程序运行效率[^4]。 ```java public class YangHuiTriangle { public static void main(String[] args) { int n = 5; long[] array1 = new long[n]; long[] array2 = new long[n]; for(int i=0; i<n; ++i){ array2[0]=array2[i]=1; for(int j=1; j<i; ++j){ array2[j] = array1[j-1]+array1[j]; } System.arraycopy(array2, 0, array1, 0, n); // 输出当前行的结果 for(long num : array2){ System.out.print(num+" "); } System.out.println(); } } } ``` --- #### 结合实际比赛需求调整策略 在竞赛环境中，除了考虑时间与空间性能外，还需要注意边界条件以及可能的大整数溢出等问题。例如，在某些情况下需要使用高精度库或者模运算处理大数值情况下的结果输出[^3]。 ---