摘要： 更相减损法 我国早期也有解决求最大公约数问题的算法.就是更相减损术． 更相减损术求最大公约数的步骤如下:可半者半之.不可半者.副置分母之数.以少减多.更相减损.求其等也.以等数约之． 翻译出来为: 第一步:任意给出两个正数,判断它们是否都是偶数．若是.用2约简,若不是.执行第二步． 第二步:以较大的数减去较小的数.接着把较小的数与所得的差比较.并以大数减小数．继续这个操作.直到所得的数相等为止.则这个数就是所求的最大公约数． 再从这个角度看一下“求a=204.b=85的最大公约数 的问题.S1步可以等价为等式:.S2步可以等价为等式:.这两步从减法的角度可以理解为:204-85.所得的差与减式中的较小数比较.再用大的数减小的数.循环执行以上步骤,直到结果为0.此时减数就是a和b的最大公约数.这一算法根据它的特点.也可以用循环语句完成. 参考代码: /a放较大的数.b放较小的数 If a < b Then m ← a a ← b b ← m /交换a.b中的数 End If /确保a是a.b中较大的数 r ← a – b /两数相减 While r ≠ 0 If b > r Then a ← b b ← r Else a ← r End If r ← a – b /确保相减后仍用较大的数减去较小的数 End While Print b 用“更相减损法 求多于两个数的最大公约数就可以显示出其优越性 [小结]比较辗转相除法与更相减损术的区别 (1)都是求最大公约数的方法.计算上辗转相除法以除法为主.更相减损术以减法为主.计算次数上辗转相除法计算次数相对较少.特别当两个数字大小区别较大时计算次数的区别较明显． (2)从结果体现形式来看.辗转相除法体现结果是以相除余数为0则得到.而更相减损术则以减数与差相等而得到． [追踪训练]

网址：http://m.1010jiajiao.com/timu_id_2503494[举报]