欧几里得算法可视化

理解最大公约数的计算原理

1. 什么是欧几里得算法？

欧几里得算法用于计算两个数的最大公约数 (GCD)。核心思想是：$$ \gcd(a, b) = \gcd(b, a \bmod b) $$

a (较大数)
48
,
b (较小数)
18
被除数
48
÷
除数
18
=
商
2
...
余 12

2. 算法步骤追踪

3. 几何理解：为什么有效？

用矩形分割来理解：用较小的矩形去拼成较大的矩形，无法拼完的部分就是余数。

几何解释：
  • 一个 a×b 的矩形可以用 b×b 的正方形填充
  • 如果 b 能整除 a，则 gcd(a, b) = b
  • 如果不能整除，剩余部分大小为 (a % b) × b
  • 问题转化为：寻找能同时整除 b 和 (a % b) 的最大数

4. 数学证明

$$ \gcd(a, b) = \gcd(b, a \bmod b) $$
证明：

设 $a = q \times b + r$，其中 q 是商，r 是余数 ($r = a \bmod b$)

如果 d 整除 a 和 b，那么 d 也整除 $r = a - q \times b$

如果 d 整除 b 和 r，那么 d 也整除 $a = q \times b + r$

因此，a 和 b 的公约数集合 = b 和 r 的公约数集合

∴ $$ \gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b) $$

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;  // b = 0 时，a 就是 GCD
}

5. 实际例子：计算 gcd(48, 18)

步骤 1: gcd(48, 18)
    48 ÷ 18 = 2 余 12
    → gcd(48, 18) = gcd(18, 12)

步骤 2: gcd(18, 12)
    18 ÷ 12 = 1 余 6
    → gcd(18, 12) = gcd(12, 6)

步骤 3: gcd(12, 6)
    12 ÷ 6 = 2 余 0
    → gcd(12, 6) = gcd(6, 0)

步骤 4: gcd(6, 0)
    当余数为 0 时，除数就是 GCD
    → gcd(6, 0) = 6

结论：gcd(48, 18) = 6