标签

先看一下TAOCP内该算法的描述:

算法E(欧几里得算法)  给定两个正整数m和n,求它们的最大公因子,即能够同时整除m和n的最大正整数。
E1.[求余数]  以n除m并令r为所得余数。(我们将有0<= r < n)
E2.[余数为零?]  若r = 0,算法结束,n即为答案。
E3.[减少]  置m <– n,n <– r,并返回步骤E1。
书中的证明为:

在步骤E1后,对于某个整数,我们有
m = qn + r
如果r = 0,则m是n的倍数,显然在这样一种情况下,n是m和n的最大公因子;

如果r 不等于0,注意整除m和n的任何数必定也整除m – qn = r,因此整除n和r的任何数必定整除qn + r = m;所以{m,n}的公因子集合和{n,r}的公因子集合是一样的。特别的,{m,n}的最大公因子和{n,r}的最大公因子是一样的。因子步骤E3不改变原来问题的答案。

证明中的要点是上句中的黑色字体部分,证明如下:
假设m和n的公因子为f,且m=sf, n = tf,则m = qn + r 转化为sf = tfn +r ==> r = (s – tn)f,得证。

最后说下习题1.1.1.3:
题目:3.[20] (为了提高效率)改变算法E使得像“m <– n”这样平凡的替代运算都加以避免。以算法E的风格来写出这个新算法,并称之为算法F。
思想:由于E1中m做完除法后就没有用了,所以可以将m直接等于余数;这样以来m < n了,所以需要将m,n位置颠倒进行一下除法运算,回到m > n的开始状态继续循环。
算法F:
F1.[求余数] 以n除m并令m为所得余数。(我们将有0<= m < n)
F2.[余数为零?] 若m = 0,算法结束,n即为答案。
F3.[求余数] 以m除n并令n为所得余数。(我们将有0<= n < m)
F4.[余数为零?] 若n = 0,算法结束,m即为答案;否则回到F1

思考:写代码的时候为何经常会丢失数学思维方式?经常不明白算法背后的原理。需要多锻炼锻炼。

Advertisements