|
/* 本文引用国家信息学竞赛2009年国家队金斌《欧几里德算法的应用》，缩略版。 */
================================================================
1.1欧几里得算法（EuclideanAlgorithm）
即大家所熟知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间
内把问题变换到能直接判定解的规模。可表示为递归式gcd(a,b) = gcd(b, a mod b) ，其中，a，b是任意的非负整数。
直接给出伪代码：
EUCLID(a,b)
1 if b = 0
2 then return a
3 else return EUCLID(b,a mod b)
举例说明：EUCLID(30,21) =EUCLID(21,9) = EUCLID(9,3) = EUCLID(3,0) = 3
1.2复杂度分析
这里只给出简要的分析,说明其时间复杂度(忽略除法的复杂度)为O(log n),对于任意两个数a, b满足a > b,我们考虑如下这个语句的效果
a a mod b
如果 b ≤ a/2 ，则 amod b ≤ b ≤ a/2
如果 b > a/2 ，则 a mod b ≤ a – b ≤ a – a/2 ≤a/2
可以看出,每次这个操作都会将a减半,所以最后复杂度是O(log n)。
1.3拓展欧几里得算法
拓展欧几里得算法(ExtendedEuclidean Algorithm )是基于欧几里得算法而来解一类特殊的线性丢番图方程(Diophantineequation)
Extended Euclidean Algorithm伪代码：
Input: a, b
Output: a solution to ax +by = gcd(a, b)
1: function extendedgcd(a,b)
2: if b = 0 then
3: return (1, 0)
4: else
5: (x, y) extended gcd(b, a mod b)
6: return (y, x (a div b) × y)
7: end if
下边做个简要分析,这是个修改版的辗转相除算法,是可以算出最后的gcd(a, b)的,考
虑第3行,当当前情况是a = gcd(a, b), b = 0时,则很容易看出x = 1, y = 0是一组解,所以在第5行的时候我们可以假定x ×b + y × (a mod b) = gcd(a, b)。对上式展开可得:
gcd(a, b) = xb + y × (a (a div b) × b)
= xb + ya y × (a div b) × b
= y × a +(x (a div b) × y) × b
所以这个算法在正向计算出gcd(a, b)之后,返回时就计算出了解,而复杂度显然和原先的一样。
1.4欧几里得算法在多项式求公因式的中用法
这里给出一个不太正规的多项式“整除”的定义:即求一个新的多项式使“余数”次数小
于“除数”。然后就可以在此基础上定义“取模”乃至后面的欧几里得过程。下面是一个例
子。
x^4 + 8x^3 + 12x^2+ 17x + 6 (1)
x^4 4x^3 + 4x^2 3x + 14 (2)
x^3 +(2/3) x^2 + (5/3)x (2/3) (3)
x^2 + x + 2 (4)
0 (5)
设式（1）为h(x),式（2）为g(x）,gcd（h(x),g(x)）=gcd(g(x），g(x) mod h(x));
同整数的欧几里德算法一样，即可得到(1)与(2)的最大公因式为(4)。
欧几里得算法在多项式求公因式中的应用与原始的欧几里得算法只是操作的对象及其运算方式不一样，减小问题规模思想是一样的。
1.5二维欧几里得算法的应用
给出两个向量 a,b，当x，y满足不同时为0时，|ax+by|最小。
1） 当a与b的夹角很小可以忽略不计时，答案实际上是gcd(|a|,|b|).(证明略)
2） 当a与b的夹角大于PI/3时，答案是min（|a|,|b|）；
|ax+by|=sqrt(|ax|^2 + |by|^2 – 2|ax||by|cos(a,b))
>=sqrt(|ax|^2+ |by|^2 - |ax||by|)
>=sqrt((|ax|-|by|)^2+ |ax||by|)
若x = 0，则y ！= 0，(|ax|-|by|)^2= |by|^2>=|b|^2>=min(|a|,|b|)^2
若y= 0 ，则x！=0，(|ax|-|by|)^2= |ax|^2>=|a|^2>=min(|a|,|b|)^2
若x!=0,y!=0,|ax||by|>=|a||b|>=min(|a|,|b|)^2
1.6 小结
欧几里得算法本质就是通过一个特定的运算,将规模变小,最后将问题变成一个平凡的问题。很多时候,我们只是在不经意间推得了一个将问题规模变小的式子,但是没有到能直接算出的地步,这时我们就可以尝试着去反复这个过程。
| 
转播
