简介

算法思想

实例

与辗转相除法的比较

对“可半者半之”的理解

BASIC实现

简介

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

算法思想

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。

实例

例1、用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

例2、用更相减损术求260和104的最大公约数。

解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。

此时65是奇数而26不是奇数，故把65和26辗转相减：

65-26=39

39-26=13

26-13=13

所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。

与辗转相除法的比较

辗转相除法也可以可以用来求两个数的最大公约数。

更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。

对“可半者半之”的理解

通常认为，算法描述中的第一步“可半者半之”是指分子分母皆为偶数的时候，首先用2约简。因为更相减损术原先是专用来约分，所以并不用考虑最后计算结果时，要把第一步中约掉的若干个2再乘回去。加入这一步的原因可能是，分母、分子皆为偶数是在分数加减运算的结果中比较容易遇到的一种情况，用这种方法有可能减少数字的位数，简化计算。

当然，省略这个以2约简的步骤，也能得到正确的答案。

BASIC实现

INPUT "m,n=";m,n

i=0

WHILE m MOD 2=0 AND n MOD 2=0

m=m/2

n=n/2

i=i+1

WEND

DO

IF m<n THEN

r=m

m=n

n=r

END IF

m=m-n

LOOP UNTIL m=0

PRINT “m、n的最大公约数为”;n*2ˆi

END

(黑体部分可以省略，因为，不进行约简，一样可以求出）