PYTHON LESSON 114
杨辉三角的奥秘
掌握杨辉三角的递推规律，会用二维列表生成任意行，并理解“第 n 行第 m 个数 = C(n, m)”。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- row = [1] * (i + 1) 快速造出全 1 的行
- row[j] = 上一行[j-1] + 上一行[j] 递推
- 列表嵌套 triangle[i][j] 表示第 i 行第 j 个数
01 · 核心概念
杨辉三角的递推构造与组合数恒等式
杨辉三角的递推构造与组合数恒等式：杨辉三角每个数都等于它“肩上”两个数之和，边缘全是 1。这个规律写成式子就是组合数恒等式 C(n, m) = C(n−1, m−1) + C(n−1, m)，所以第 n 行第 m 个数正好是 C(n, m)。
GESP Python 8 级 · 杨辉三角GESP Python 8 级 · 排列与组合（编程求解）概率需要在计数结果上再建立样本空间，不等同于组合数本身。
02 · 语法与规则
先记住这 3 条，再开始写程序
row = [1] * (i + 1) 快速造出全 1 的行先准确读出这条写法的结构与作用。
row[j] = 上一行[j-1] + 上一行[j] 递推换一组最小数据，手工推演一次结果。
列表嵌套 triangle[i][j] 表示第 i 行第 j 个数再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 杨辉三角：每一行都是组合数的真身
n = 6
triangle = []
for i in range(n):
row = [1] * (i + 1) # 每行首尾都是 1
for j in range(1, i):
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j] # 肩上两数之和
triangle.append(row)
print(" ".join(map(str, row)))
# 第 5 行（从 0 数）第 2 个数，就是组合数 C(5, 2)
print("C(5, 2) =", triangle[5][2])1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 C(5, 2) = 10
行号与列号都从 0 开始数：第 i 行第 j 个数恰好是 C(i, j)。
04 · 逐步理解
每一步只解决一个问题
- 01
看懂递推规律
杨辉三角每个数都等于它“肩上”两个数之和，边缘全是 1。这个规律写成式子就是组合数恒等式 C(n, m) = C(n−1, m−1) + C(n−1, m)，所以第 n 行第 m 个数正好是 C(n, m)。
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j] - 02
用 [1] * (i+1) 造好一行
第 i 行有 i+1 个数，且首尾必为 1。先用 [1] * (i + 1) 造出一行全 1 的列表，再只更新中间位置（j 从 1 到 i−1），边缘自动正确，省心又不易错。
row = [1] * (i + 1) for j in range(1, i): row[j] = triangle[i-1][j-1] + triangle[i-1][j] - 03
一行一行存进大列表
用列表 triangle 把每一行追加进去，triangle[i] 就是第 i 行。这是“二维列表”的典型用法：triangle[i][j] 先行后列，像查表格一样取数。
triangle.append(row) - 04
把整行漂亮地输出
" ".join(map(str, row)) 是竞赛常用套路：map(str, row) 把每个数转成字符串，join 用空格缝成一行，行尾不会有多余空格——OJ 判题对格式很挑剔。
print(" ".join(map(str, row))) - 05
验证“第 i 行第 j 个 = C(i, j)”
打印完 6 行后取 triangle[5][2]，结果是 10，与 comb(5, 2) 完全一致。以后题目要求组合数而 n 又不太大时，杨辉三角递推比阶乘更稳、更快。
print(triangle[5][2]) # 10 - 06
复杂度小算盘
生成 n 行杨辉三角要填 1+2+…+n ≈ n²÷2 个数，时间复杂度 O(n²)，空间 O(n²)。若只问某一行，其实只保留上一行就够，空间可压到 O(n)——这就是“滚动数组”思想的萌芽。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行打印机，观察前 6 行规律
- 2验证 C(5, 2) 与第 5 行第 2 个数相等
- 3把行数改成 10 再看输出
- 4用组合数解释为什么每行首尾都是 1
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- A(n,m)=n!/(n-m)!，C(n,m)=n!/(m!(n-m)!)，并有 C(n,m)=C(n,n-m)。
- 杨辉三角递推 C(n,m)=C(n-1,m-1)+C(n-1,m)，边界 C(n,0)=C(n,n)=1。
- 取模下的组合数算法取决于 n、模数是否为质数、查询次数和是否允许预处理。
- 距离比较应优先比较平方，避免不必要的 sqrt 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
完成检查