词条 | 更相减损术 |
释义 | 简介更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。 算法思想《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。” 翻译成现代语言如下: 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用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 (黑体部分可以省略,因为,不进行约简,一样可以求出) |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。