欧几里得算法(辗转相除法)

算法是一组有限的规则,规则给出求解特定类型问题的运算序列。

算法的 5 个重要特征:

  1. 有限性。算法在有限步骤后必然终止。步骤 E1 后,余数 r < n;步骤 E3 后,n ⬅ r,n 的值在递减。经有限步骤后,直到 r = 0 时步骤终止。

    具有算法的所有其它特征,只是可能缺少有限性,称为计算方法。

  2. 确定性。算法的每个步骤都必须精确地定义,无歧义。

  3. 输入。算法有 0 或多个输入,这些输入是从特定的对象集合取出。

  4. 输出。算法有 1 或多个输出,和输入有特定关系的量。

  5. 能行性。算法的所有运算都可用笔和纸,在有限时间内精确地完成。

算法 E(欧几里得算法)给定两个正整数 m 和 n,求它们的最大公因子,即能够同时整除 m 和 n 的最大正整数。

E0.[确保 m >= n] 如果 m < n,交换 m ↔ n。

E1.[求余数] 余数 r = m % n。

E2.[余数为零?] 若 r = 0,算法结束,n 即为答案。

E3.[减少] 置 m ⬅ n,n ⬅ r,返回步骤 E1。|

// 输入
int m = 24;
int n = 16;

if (m < n) {
    int temp = m;
    m = n;
    n = temp;
}
for (int r = m % n; r != 0; r = m % n) {
    m = n;
    n = r;
}
// 输出
printf("%d\n", n);

算法 E(扩充的欧几里得算法)给定两个正整数 m 和 n,计算它们的最大公因数 d 和两个整数 a 和 b,使得 am + bn = d。

199/77=2,余45。45=199-2*77
77/45=1,余32。32=77-45*1=77-(199-77*2)*1=-199+3*77
45/32=1,余13。13=45-32*1=(199-77*2)-(-199+77*3)=2*199-5*77
32/13=2,余6。6=32-13*2=(-199+3*77)-(2*199-5*77)*2=-5*199+13*77
13/6=2,余1。1=13-6*2=(2*199-5*77)-(-5*199+13*77)*2=12*199-31*77
6/1=6,余0,结束。a = 12,b = -31。am + bn = 1。

当 m 是 n 的倍数时,最大公因数 d 为 n,am + bn = n,推出 a = 0,b = 1。
每行用字母替代 c / d = q,c % d = r,r = a * c – b * d。
当 r = 0 时,d 为最大公因数,程序结束。

从第三行时,发现规律:a = 上上行a – 上行a * q。


第一行 a = 1,b = -q = -2。
a1 = 1,b1 = -2 保存当前 a,b 的值。

第二行 a = -1 = -a * q,b = 1 – b * q = 3。
t = a1 = 1,t1 = b1 = -2 保存上次的 a1,b1 的值。
a1 = a = -1,b1 = b = 3 保存当前 a,b 的值。

第三行 a = 2 = t – a * q,b = -5 = t1 – b * q。

…随后几行都符合此规律。

构建第一行、第二行,使之符合规律。
第二行 a = -1 = t – a * q,b = t1 – b * q = 3。推出之前的 t = a1 = 0,t1 = b1 = 1。

第一行 a = 1 = t – a * q,b = t1 – b * q = -q = -2。推出之前的 t = a1 = 1,a = 0,b = 1,t1 = b1 = 0。
t = a1 = 0,t1 = b1 = 1。推出之前的 a1 = a = 0,b1 = b = 1。
a1 = 1,b1 = -2 保存当前 a,b 的值。

所以执行第一行前,设初始值 a = 0,b = 1;a1 = 1,b1 = 0。

t = a1 = 1,t1 = b1 = 0
a1 = a = 0,b1 = b = 1
第一行 a = t-a*q = 1,b = t1-b*q = -2

t = a1 = 0, t1 = b1 = 1
a1 = a = 1, b1 = b = -2
第二行 a = t-a*q = -1,b = t1-b*q = 3
...

E1. a ⬅ b1 ⬅ 0,b ⬅ a1 ⬅ 1,c ⬅ m,d ⬅ n。

E2. q ⬅ c/d,r ⬅ c%d。

E3. 如果 r = 0,算法终止。am + bn = d。

E4. t ⬅ a1,a1 ⬅ a,a ⬅ t – aq;t ⬅ b1,b1 ⬅ b,b ⬅ t – bq;c ⬅ d,d ⬅ r;回到 E2。|

// 输入
int m = 199;
int n = 77;

int a, a1, b, b1, t, c, d, r, q;

c = m;
d = n;
a = b1 = 0;
b = a1 = 1;
r = c % d;
q = c / d;
while (r != 0) {
    t = a1;
    a1 = a;
    a = t - a * q;
    
    t = b1;
    b1 = b;
    b = t - b * q;

    c = d;
    d = r;
    
    r = c % d;
    q = c / d;
}
// 输出
printf("最大公因数:%d\n", d);
printf("a:%d\n", a);
printf("b:%d\n", b);

算法 I(数学归纳法)给定一个正整数 n,这个算法将输出 P(n) 为真的一个证明。

I1.k ⬅ 1,证明 P(1) 为真。

I2.如果 k = n,算法终止,P(n) 为真。

I3.如果 P(1)、P(2)、… P(k) 为真,证明 P(k+1) 为真。

I4.k ⬅ k+1,返回步骤 I2。|

命题:对于正整数 n,如果 n >= 10,则 2n > n3

①当 n = 10 时,210 = 1024 > 1000 = 103,命题成立。

②k >= 10,假设 n = k 时,2k > k3 成立。

③当 n = k+1 时,2k+1 = 2k + 2k,(k+1)3 = k3 + 3k2 + 3k + 1。

k > 4,有 k2 > 4k > 3k + 4。
不等式两边同时乘以 k:k3 > 3k2 + 4k > 3k2 + 3k + 1。
若 k3 < 2k 成立,则 3k2 + 3k + 1 < 2k
k3 + (3k2 + 3k + 1) < 2k + 2k,即 (k+1)3 < 2k+1

结论:若 n = k 时命题成立,则 n = k+1 时命题也成立。

④因 k = 10 时命题成立,所以 k = 11、12、… n 时命题也成立。