PYTHON LESSON 066
分数约分器
掌握辗转相除法求最大公因数，会用 GCD 求最小公倍数并给分数约分。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- while 版辗转相除：a, b = b, a % b
- 递归版辗转相除：gcd(b, a % b)
- lcm = a * b // gcd(a, b)
01 · 核心概念
最大公因数与辗转相除法
最大公因数与辗转相除法：把 12/18 约成 2/3，关键是找到 12 和 18 的最大公因数 6。小数还能短除，遇到 1071/462 这种大数，分解质因数就太慢了——需要更锋利的武器。
GESP Python 5 级 · 辗转相除法GESP Python 5 级 · 约数与倍数大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
while 版辗转相除：a, b = b, a % b先准确读出这条写法的结构与作用。
递归版辗转相除：gcd(b, a % b)换一组最小数据，手工推演一次结果。
lcm = a * b // gcd(a, b)再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 分数约分器：辗转相除法
def gcd(a, b):
"""辗转相除：大数除以小数，余数接着除，直到余 0"""
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
"""最小公倍数 = 两数之积 ÷ 最大公因数"""
return a * b // gcd(a, b)
def reduce_fraction(zi, mu):
"""把分数 zi/mu 约到最简"""
g = gcd(zi, mu)
return zi // g, mu // g
print("gcd(12, 18) =", gcd(12, 18))
print("gcd(1071, 462) =", gcd(1071, 462))
print("lcm(4, 6) =", lcm(4, 6))
zi, mu = reduce_fraction(12, 18)
print("12/18 约分后是", str(zi) + "/" + str(mu))
zi, mu = reduce_fraction(105, 42)
print("105/42 约分后是", str(zi) + "/" + str(mu))gcd(12, 18) = 6 gcd(1071, 462) = 21 lcm(4, 6) = 12 12/18 约分后是 2/3 105/42 约分后是 5/2
辗转相除法两千多岁（欧几里得算法），至今仍是求最大公因数的主力算法。
04 · 逐步理解
每一步只解决一个问题
- 01
约分需要最大公因数
把 12/18 约成 2/3，关键是找到 12 和 18 的最大公因数 6。小数还能短除，遇到 1071/462 这种大数，分解质因数就太慢了——需要更锋利的武器。
- 02
神奇的“互相除”
看一组魔术：gcd(12, 18) → 18 ÷ 12 余 6 → 12 ÷ 6 余 0 → 答案就是 6。每次用“除数”和“余数”组成新的一对小数接着除，余数为 0 时的除数就是最大公因数。
gcd(12, 18) → gcd(6, 12) → gcd(0, 6) → 6 - 03
一行交换的艺术
a, b = b, a % b 一行完成“新 a 等于旧 b，新 b 等于余数”。while b != 0 循环到余数为 0 为止，a 里就是答案。这是 Python 里写辗转相除最优雅的姿势。
while b != 0: a, b = b, a % b return a - 04
递归版：函数自己调自己
辗转相除还可以一行递归写完：b 为 0 就返回 a，否则返回 gcd(b, a % b)。递归思想在五级的分治算法里还会大放异彩。
def gcd(a, b): return a if b == 0 else gcd(b, a % b) - 05
由 GCD 到 LCM
最大公因数和最小公倍数是好搭档：lcm = a × b ÷ gcd。比如 gcd(4, 6) = 2，lcm 就是 24 ÷ 2 = 12。“几小时后再次同时发车”这类题全靠它。
def lcm(a, b): return a * b // gcd(a, b) - 06
约分器完工
分子分母同除以最大公因数，分数就约到最简。把 gcd、lcm、reduce_fraction 收进你的函数工具箱，它们会在后面的题目里反复出场。
g = gcd(zi, mu) return zi // g, mu // g
05 · 练习与检验
自己写出来，才算真正学会
- 1运行约分器，看 12/18 变成 2/3
- 2手算 gcd(1071, 462) 再和程序核对
- 3换一对大数，感受辗转相除的速度
- 4用 lcm 算两道“再次同时”的应用题
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查