【例5.11】杨辉三角形

GitHub跳转原题关系图返回列表

用二维数组和递推公式计算并打印杨辉三角形的前 $n$ 行,强调对输出格式的精准控制。

OJ: roj

题目 ID: 5045

难度:入门

标签:基础算法递推数组

创建: 2026-10-08 20:56

更新: 2026-10-08 20:56

形式化题目

输入一个整数 nn(2≤n≤202 \le n \le 20)。 输出杨辉三角形的前 nn 行。 其中第 ii 行(1≤i≤n1 \le i \le n)有恰好 ii 个数字,表示组合数 C(i−1,j−1)C(i-1, j-1)(1≤j≤i1 \le j \le i)。 在同一行内,数字之间恰好用一个空格隔开,行末没有多余的空格。

  • 第 ii 行第 jj 列的值记为 a[i][j]a[i][j]
  • 边界条件:对所有的 i≥1i \ge 1,有 a[i][1]=1a[i][1] = 1、a[i][i]=1a[i][i] = 1
  • 递推关系:对 i≥3i \ge 3 且 2≤j≤i−12 \le j \le i-1,有 a[i][j]=a[i−1][j−1]+a[i−1][j]a[i][j] = a[i-1][j-1] + a[i-1][j]

正解

思路

根据杨辉三角形的定义,第 ii 行由 ii 个数字组成,第一个数字和最后一个数字都是 1,中间的数字等于上一行对应位置的相邻两个数字之和。

可以直接使用二维数组 a[i][j]a[i][j] 表示第 ii 行第 jj 列的数字。

  1. 初始化:对于所有的行 ii,将每行的首列设为 1,即 a[i][1]=1a[i][1] = 1。
  2. 递推:对于第 ii 行(i≥2i \ge 2)的第 jj 个数字(2≤j≤i2 \le j \le i),可以由前一行(第 i−1i-1 行)的第 j−1j-1 个数字和第 jj 个数字相加得到,即 a[i][j] = a[i-1][j-1] + a[i-1][j]。
    • 注意:如果我们将二维数组声明在全局域使其默认初始化为 0,当 j=ij = i 时,a[i−1][i]a[i-1][i] 恰好为 0,那么 a[i][i]=a[i−1][i−1]+a[i−1][i]=1+0=1a[i][i] = a[i-1][i-1] + a[i-1][i] = 1 + 0 = 1,这使得每行的最后一个数字由递推自然得到。
  3. 输出格式:遍历前 nn 行输出结果。在一行中,只有在输出第一个数字之后才输出空格,这样可以保证每一行的数字之间恰有一个空格,而行尾没有多余的空格。
  4. 数据类型:当 n=20n = 20 时,最大的数字是 C(19,9)=92378C(19,9) = 92378。这个数值远小于 int 的最大值 21474836472147483647,因此普通的 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 到 nn,内层循环从 1 到 ii,总计执行了大约 n22\frac{n^2}{2} 次操作;输出的过程同样执行了约 n22\frac{n^2}{2} 次操作。因此时间复杂度为 O(n2)\mathcal{O}(n^2)。当 n≤20n \le 20 时,计算次数不到 400,可以忽略不计。
  • 空间复杂度:由于需要保存整个杨辉三角形的前 nn 行,我们需要一个规模至少为 21×2121 \times 21 的二维数组。所以空间复杂度为 O(n2)\mathcal{O}(n^2)。考虑到 nn 很小,这部分内存占用极少。

总结

  • 杨辉三角的递推关系与等价形式:第 ii 行第 jj 个数即组合数 (i−1j−1)\binom{i-1}{j-1}。其递推关系为 C(i,j)=C(i−1,j−1)+C(i−1,j)C(i,j) = C(i-1,j-1) + C(i-1,j),边界为 C(i,1)=C(i,i)=1C(i,1) = C(i,i) = 1。
  • 防止未初始化的脏数据:在 C++ 中把数组定义在全局变量能够自动清零,这让 j=ij=i 时递推边界自动补上 0,从而使每行末尾的 a[i][i]a[i][i] 自动等于 1,简化了额外的判断逻辑。
  • 数值范围与边界:n≤20n \le 20 最大数为 C(19,9)=92378C(19,9) = 92378,完全在 int 范围内(但我们遵循规范使用了 long long)。题面写 2≤n≤202 \le n \le 20,评测数据中也确实无 n=1n=1 (属于题面未定义情形)。
  • 题面自相矛盾的裁决:题目【题目描述】中有一段带前导空格的代码块(形成一个对称的等腰三角形),这是为了帮助读者理解的视觉示意图。紧接着的下一块无前导空格、左对齐的形式,才是真正的输出格式,一切必须以真实数据为准。
  • 换行符不一致陷阱:题面中无前导空格的样例代码块本身带有 CRLF 换行符(这在文本处理时很少见),但评测数据的行尾是 LF 格式。如果基于样例去做逐字节对比或硬编码,容易发生由于换行符导致的误报错误。必须做归一化处理。
  • 输出格式的精确要求与反事实验证:本题对格式要求极为苛刻。下面给出了 5 种不符合严格要求(无前导空格、分隔符恒为单空格、行尾无空格、末尾单 \n、无多余空行)的写法在真实评测数据上的失败情况,生动说明了为什么代码必须要“一丝不苟”地控制格式:
变体写法 结果
原版严格控制格式 ✅ 10/10 通过
A. 加前导空格对齐 ❌ 10/10 全败,发生偏移
B. 行尾保留多余空格 ❌ 10/10 全败,发生偏移
C. 两数间用两个空格分隔 ❌ 10/10 全败,发生偏移
D. 在末尾追加多余空行 ❌ 10/10 全败,发生偏移
E. 最后一行结尾不换行 ❌ 10/10 全败,发生偏移