用二维数组和递推公式计算并打印杨辉三角形的前 $n$ 行,强调对输出格式的精准控制。
OJ: roj
题目 ID: 5045
难度:入门
标签:基础算法递推数组
创建: 2026-10-08 20:56
更新: 2026-10-08 20:56
形式化题目
输入一个整数
- 第
行第 列的值记为 - 边界条件:对所有的
,有 、 - 递推关系:对
且 ,有
正解
思路
根据杨辉三角形的定义,第
可以直接使用二维数组
- 初始化:对于所有的行
,将每行的首列设为 1,即 。 - 递推:对于第
行( )的第 个数字( ),可以由前一行(第 行)的第 个数字和第 个数字相加得到,即 a[i][j] = a[i-1][j-1] + a[i-1][j]。- 注意:如果我们将二维数组声明在全局域使其默认初始化为 0,当
时, 恰好为 0,那么 ,这使得每行的最后一个数字由递推自然得到。
- 注意:如果我们将二维数组声明在全局域使其默认初始化为 0,当
- 输出格式:遍历前
行输出结果。在一行中,只有在输出第一个数字之后才输出空格,这样可以保证每一行的数字之间恰有一个空格,而行尾没有多余的空格。 - 数据类型:当
时,最大的数字是 。这个数值远小于 int的最大值,因此普通的 32 位整型( int)即可。但在具体工程实现中通常按项目统一规范使用 64 位整数(long long)。
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 20:37
# update_at: 2026-10-08 20:37
import sys
def rows_of_pascal(n: int) -> list[list[int]]:
"""按 a[i][j] = a[i-1][j-1] + a[i-1][j] 递推构造杨辉三角前 n 行。"""
rows = [[1]]
for i in range(1, n):
prev = rows[-1]
rows.append([1] + [prev[j] + prev[j + 1] for j in range(i - 1)] + [1])
return rows
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
# 每行数之间恰一个空格,行末无多余空格;print 末尾补的那个 \n 就是换行
print('\n'.join(' '.join(map(str, row)) for row in rows_of_pascal(n)))
if __name__ == "__main__":
solve()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 20:37
* update_at: 2026-10-08 20:37
*/
// main.cpp:打印杨辉三角形的前 n 行(2<=n<=20)。
// 用递推 a[i][j] = a[i-1][j-1] + a[i-1][j] 建表,按题面要求每行各数之间用一个空格隔开。
#include <iostream>
typedef long long ll;
// a[i][j] = 第 i 行第 j 个数 = C(i-1, j-1)。全局数组自动清零,使 a[i-1][i] 为 0,
// 于是 a[i][i] = a[i-1][i-1] + 0 = 1,每行末尾的 1 由递推自然得到。
ll a[25][25];
void solve() {
ll n;
if (!(std::cin >> n)) {
return;
}
for (ll i = 1; i <= n; i++) {
a[i][1] = 1; // 每行第一个数恒为 1
for (ll j = 2; j <= i; j++) {
a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
}
}
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= i; j++) {
if (j > 1) {
std::cout << ' '; // 数之间恰一个空格,行末不留多余空格
}
std::cout << a[i][j];
}
std::cout << "\n";
}
}
int main() {
solve();
return 0;
}复杂度
- 时间复杂度:计算并填充二维数组的过程嵌套了两次循环,外层循环从 1 到
,内层循环从 1 到 ,总计执行了大约 次操作;输出的过程同样执行了约 次操作。因此时间复杂度为 。当 时,计算次数不到 400,可以忽略不计。 - 空间复杂度:由于需要保存整个杨辉三角形的前
行,我们需要一个规模至少为 的二维数组。所以空间复杂度为 。考虑到 很小,这部分内存占用极少。
总结
- 杨辉三角的递推关系与等价形式:第
行第 个数即组合数 。其递推关系为 ,边界为 。 - 防止未初始化的脏数据:在 C++ 中把数组定义在全局变量能够自动清零,这让
时递推边界自动补上 0,从而使每行末尾的 自动等于 1,简化了额外的判断逻辑。 - 数值范围与边界:
最大数为 ,完全在 int范围内(但我们遵循规范使用了long long)。题面写,评测数据中也确实无 (属于题面未定义情形)。 - 题面自相矛盾的裁决:题目【题目描述】中有一段带前导空格的代码块(形成一个对称的等腰三角形),这是为了帮助读者理解的视觉示意图。紧接着的下一块无前导空格、左对齐的形式,才是真正的输出格式,一切必须以真实数据为准。
- 换行符不一致陷阱:题面中无前导空格的样例代码块本身带有 CRLF 换行符(这在文本处理时很少见),但评测数据的行尾是 LF 格式。如果基于样例去做逐字节对比或硬编码,容易发生由于换行符导致的误报错误。必须做归一化处理。
- 输出格式的精确要求与反事实验证:本题对格式要求极为苛刻。下面给出了 5 种不符合严格要求(无前导空格、分隔符恒为单空格、行尾无空格、末尾单
\n、无多余空行)的写法在真实评测数据上的失败情况,生动说明了为什么代码必须要“一丝不苟”地控制格式:
| 变体写法 | 结果 |
|---|---|
| 原版严格控制格式 | ✅ 10/10 通过 |
| A. 加前导空格对齐 | ❌ 10/10 全败,发生偏移 |
| B. 行尾保留多余空格 | ❌ 10/10 全败,发生偏移 |
| C. 两数间用两个空格分隔 | ❌ 10/10 全败,发生偏移 |
| D. 在末尾追加多余空行 | ❌ 10/10 全败,发生偏移 |
| E. 最后一行结尾不换行 | ❌ 10/10 全败,发生偏移 |