算法是一组有限的规则,规则给出求解特定类型问题的运算序列。
算法的 5 个重要特征:
有限性。算法在有限步骤后必然终止。步骤 E1 后,余数 r < n;步骤 E3 后,n ⬅ r,n 的值在递减。经有限步骤后,直到 r = 0 时步骤终止。
具有算法的所有其它特征,只是可能缺少有限性,称为计算方法。
确定性。算法的每个步骤都必须精确地定义,无歧义。
输入。算法有 0 或多个输入,这些输入是从特定的对象集合取出。
输出。算法有 1 或多个输出,和输入有特定关系的量。
能行性。算法的所有运算都可用笔和纸,在有限时间内精确地完成。
算法 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 时命题也成立。