欧几里得算法 - 人类最古老的算法之一
古老钥匙与数字世界：欧几里得算法
📰 5W1H 发明者故事
Who（何人）- 发明者是谁？
发明者：欧几里得（Euclid，约公元前300年）
背景：欧几里得是古希腊数学家，亚历山大里亚图书馆的学者。他最著名的贡献是13卷本的《几何原本》（Elements），这套书统治了西方数学教育两千年。然而很多人不知道，他在《几何原本》第七卷中，记录了一个用于计算两个正整数最大公约数的算法——这是有文字记载的最古老的算法之一，比计算机早了2300年。
当时的处境：古希腊数学家面临一个实际问题：如何将两段长度化简为最简比例？比如256厘米和96厘米的两根木棒，能被哪个最长的单位同时量尽？这需要找最大公约数（GCD）。欧几里得用几何方法描述了这个算法，但其核心思想是纯算术的。
When（何时）- 什么时候发明的？
时间：约公元前300年（记录于《几何原本》）
时代背景：
- 古希腊数学达到顶峰，柏拉图学院刚刚结束，亚里士多德的形式逻辑刚刚建立
- 亚历山大大帝征服后，亚历山大城成为地中海世界的知识中心
- 数学家们还没有负数和零的概念，但对整数和几何有深刻理解
- "算法"这个词（algorithm）来自9世纪数学家花剌子密（al-Khwarizmi），但欧几里得的方法早已具备算法的核心特征
Where（何地）- 在哪里发明的？
地点：埃及亚历山大城（Alexandria）的缪斯神庙（Mouseion，即图书馆）
环境：亚历山大图书馆汇聚了古代世界最聪明的学者，藏书据说超过70万卷纸草纸卷轴。欧几里得在这里不仅整理了前人的几何知识，还发展了严格的证明方法。
What（何事）- 发明了什么？
算法：欧几里得算法（Euclidean Algorithm）求最大公约数
核心原理：gcd(a, b) = gcd(b, a mod b)，直到余数为0
关键洞察：
- 辗转相除：如果 r = a mod b，则 gcd(a, b) = gcd(b, r)
- 递归终止：最终 b=0 时，gcd(a, 0) = a
- 几何解释：用短线段反复量长线段，最后剩余的最短线段就是公约数
算法步骤（以24和36为例）：
gcd(36, 24) → 36 = 1×24 + 12，gcd(24, 12) gcd(24, 12) → 24 = 2×12 + 0，gcd(12, 0) gcd(12, 0) = 12Why（何因）- 为什么发明？
要解决的问题：
- 分数化简：把 24/36 化简为 2/3，需要找 gcd(24,36)=12
- 比例计算：建筑、音乐中的比例关系
- 测量问题：用最少的测量单位量两段长度
- 密码学（现代）：RSA加密算法的核心是互质判断（gcd=1）
当时的挑战：古希腊人没有"0"的概念，也没有现代的除法符号。欧几里得用几何语言描述了这个算法（“用短线量长线”），本质是同一个算法。
动机：希腊人追求数学中的"完美比例"（如黄金比例），需要精确计算约数关系。
How（何果）- 如何实现？有什么影响？
时间复杂度：O(log(min(a,b)))——斐波那契数是最坏情况，但收敛极快
空间复杂度：O(1)（迭代版本）或O(log n)（递归版本）
扩展欧几里得算法（Extended Euclidean）：不仅求gcd，还找 ax + by = gcd(a,b) 的整数解，是RSA密钥生成的核心。
历史影响：
- 2300年来持续使用，是数论的基石
- RSA公钥密码（1977）的核心：e和φ(n)互质，即gcd(e, φ(n))=1
- 计算机图形学中的Bresenham直线算法用到了类似思想
- 克努斯在TAOCP第二卷4.5节详细分析了其效率
📝 自然语言需求定义
需求名称：实现欧几里得算法求最大公约数，并扩展为求最小公倍数
功能需求
- 迭代GCD：用循环实现欧几里得算法，求两正整数的最大公约数
- 递归GCD：用递归实现，展示算法的递归本质
- LCM（最小公倍数）：利用 lcm(a,b) = a*b/gcd(a,b) 计算
- 互质判断：gcd(a,b)==1 时互质，返回true
- 扩展欧几里得：求 ax + by = gcd(a,b) 的整数解 x, y
验收标准
| 编号 | 测试场景 | 预期结果 | 验证方式 |
|---|---|---|---|
| 1 | gcd(48, 18) | 6 | 直接验证 |
| 2 | gcd(100, 75) | 25 | 直接验证 |
| 3 | gcd(17, 13)（互质） | 1 | 返回1，is_coprime为true |
| 4 | gcd(a, 0) = a | gcd(42,0)=42 | 边界条件 |
| 5 | lcm(4, 6) | 12 | lcm = 4*6/gcd(4,6)=2 |
| 6 | 扩展GCD：gcd(35,15) | 5，且存在x,y使35x+15y=5 | 验证等式成立 |
| 7 | 斐波那契数的GCD（最坏情况） | gcd(fib(20),fib(19))=1 | 性能不退化 |
💻 C语言实现文件
对应文件:euclidean_gcd.c
编译运行:
gcc-oeuclidean_gcd_test euclidean_gcd.c ./euclidean_gcd_test
