从可用规则到可证明算法：为什么步骤正确

本课要解决的问题

一个算例成功，不等于方法永远正确；怎样证明算法对所有输入都有效？

这不是先背名词再找用途。我们从一个确切问题出发，逐步抽出能够重复使用的数学结构。学完本课，你应能解释“为什么要这样定义”，并独立完成一个计算或证明。

概念建立

算法给出有限、明确的操作序列；证明则解释每一步为何保持目标性质，并说明过程为何终止。欧几里得算法用 gcd(a,b)=gcd(b,a mod b) 缩小问题，余数严格下降保证终止。

推导主线

写 a=qb+r。一个数同时整除 a 与 b，当且仅当它同时整除 b 与 r=a-qb，所以两对数的公因数完全相同，最大公因数也相同。每轮余数满足 0≤r<b，非负整数不可能无限严格下降。

完整例题

求 gcd(252,105)：252=2×105+42；105=2×42+21；42=2×21+0。最后一个非零余数是21，所以最大公因数为21。这里“答案”和“算法必然正确”的理由同样重要。

严格边界

列举很多样例只能增加信心，不能代替一般证明。算法正确性通常包含部分正确性与终止性；只说明结果若出现就是对的，还没有证明它一定会停。

课后闭环

用辗转相除法求 gcd(414,662)，每一步写商和余数；再用公因数集合不变解释正确性。

完成页面中的单选、多选和计算题。计算题要保留中间步骤；多选题漏选或多选均视为没有掌握定义。错误按“对象、运算、条件、推理、计算”标出第一处失误，隔一天遮住答案重做。