当前位置：首页 > news >正文

【C++】P5732 【深基5.习7】杨辉三角

news 2025/1/8 2:22:23

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯题目描述
- 输入输出格式
- - 输入
  - 输出
- 输入输出样例
💯我的实现方法
- 实现解析
- 实现的优点
- 改进空间
💯老师的实现方法
- 实现解析
- 优缺点对比
💯优化与扩展
- 方案 1：使用一维数组
- 优点
- 方案 2：只使用一个数组
- 优点
💯总结

在这里插入图片描述

💯前言

杨辉三角，又称帕斯卡三角，是数学中的一个经典模型，它不仅具有简单的构造规律，而且在数学和计算机科学中有着广泛的应用。例如，杨辉三角可以用于计算组合数、展开二项式、递归问题等。在编程学习中，杨辉三角是一个非常适合用来练习数组、循环、条件判断和动态规划的例题。
本文以一道洛谷题目 P5732 为切入点，结合代码分析，详细讲解如何构造杨辉三角，并对比了不同的实现方式，包括初学者的实现和优化的写法。最后，还探讨了内存优化和动态数组的使用。
C++ 参考手册

💯题目描述

P5732 【深基5.习7】杨辉三角
在这里插入图片描述
题目要求实现一个程序，输入一个整数 $n$ （ $\leq n \leq 20$ ），输出杨辉三角的前 $n$ 行。具体规则如下：

杨辉三角的每一行的开头和结尾都是 1；
每个非首尾的数字等于上一行相邻两个数字之和；

输入输出格式

输入

无（直接读取用户输入的 $n$ ）。

输出

无（直接打印杨辉三角的前 $n$ 行）。

输入输出样例

输入：

输出：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

💯我的实现方法

首先，让我们来看我对该题目的实现代码：

#include <iostream>
using namespace std;int main()
{int n;cin >> n;int arr[n][n];for (int i = 0; i < n; i++){arr[i][0] = 1;arr[i][i] = 1;for (int j = 1; j < i; j++){arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];}}for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){cout << arr[i][j] << " ";}cout << endl;}return 0;
}

在这里插入图片描述

实现解析

二维数组的声明：
```
int arr[n][n];
```
- 用二维数组 arr 来存储杨辉三角的每个数值，其中第 $i$ 行的前 $i + 1$ 个元素是有效的。
- 这种实现的缺点是多余的内存浪费：实际上，每一行需要存储的元素个数等于行号，而多余的部分（右侧无效的元素）不会被使用。
杨辉三角的构造规则：
- 首尾元素：
```
arr[i][0] = 1;
arr[i][i] = 1;
```
  每一行的第一个和最后一个元素始终为 1。
- 中间元素：
```
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
```
  每个非首尾元素等于上一行左上方和正上方两个元素之和。

输出部分：

使用两层循环，逐行打印数组中有效的元素：

for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {cout << arr[i][j] << " ";}cout << endl;
}

实现的优点

逻辑清晰：按照杨辉三角的定义逐步构造，代码结构简单明了。
动态规划思想：当前行依赖于上一行，避免了重复计算。

改进空间

空间浪费：二维数组中有许多无效的元素（右侧未使用的部分）。
灵活性较低：使用固定大小的二维数组 arr[n][n]，当 $n$ 较大时可能导致栈溢出。

💯老师的实现方法

接下来，让我们分析老师提供的代码：

#include <iostream>
using namespace std;const int N = 25;
int arr[N][N];int main()
{int n = 0;cin >> n;for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){if (j == 0 || i == j)arr[i][j] = 1;if (i >= 2 && j >= 1)arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];cout << arr[i][j] << " ";}cout << endl;}return 0;
}

在这里插入图片描述

实现解析

全局数组的使用：
```
const int N = 25;
int arr[N][N];
```
- 老师直接在全局中声明了一个最大容量为 $25\times25$ 的二维数组，避免了栈空间不足的问题。
- 这种实现方法适合小规模问题，但对于大规模问题（如 $n > 25$ ）无法扩展。
优化的构造规则：
- 使用条件判断处理首尾元素和中间元素：
```
if (j == 0 || i == j)arr[i][j] = 1;
if (i >= 2 && j >= 1)arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
```
  这种写法简洁高效，避免了不必要的赋值操作。
输出部分的优化：
- 直接在构造数组的同时输出每个元素：
```
cout << arr[i][j] << " ";
```
  这种方法节省了额外的循环遍历时间。

优缺点对比

优点：
- 使用全局数组避免栈溢出。
- 通过条件判断简化了逻辑，减少了多余的赋值操作。
- 构造和输出合并，代码更加紧凑。
缺点：
- 与我的实现一样，存在空间浪费问题。
- 不够灵活，无法支持动态规模的输入。

💯优化与扩展

为了进一步提高代码的效率和灵活性，我们可以考虑以下优化方案：

方案 1：使用一维数组

杨辉三角每一行只依赖于上一行的结果，因此可以用一维数组代替二维数组，从而节省空间。

优化代码如下：

#include <iostream>
#include <vector>
using namespace std;int main()
{int n;cin >> n;vector<int> prev, curr;for (int i = 0; i < n; i++) {curr.resize(i + 1);curr[0] = curr[i] = 1; // 首尾元素置为1for (int j = 1; j < i; j++) {curr[j] = prev[j - 1] + prev[j]; // 中间元素计算}prev = curr; // 保存当前行，用于下一行计算for (int num : curr) cout << num << " ";cout << endl;}return 0;
}

在这里插入图片描述

优点

节省空间：只需要两个一维数组存储当前行和上一行。
动态性强：使用 vector，可以支持任意大小的输入。

方案 2：只使用一个数组

进一步优化空间，可以只使用一个数组，同时更新当前行和上一行的值。

优化代码如下：

#include <iostream>
#include <vector>
using namespace std;int main()
{int n;cin >> n;vector<int> arr(n, 0);for (int i = 0; i < n; i++) {arr[i] = 1;for (int j = i - 1; j > 0; j--) {arr[j] += arr[j - 1];}for (int k = 0; k <= i; k++) {cout << arr[k] << " ";}cout << endl;}return 0;
}