例2用更相减损术求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:用更相减损术求两个正数84与72的最大 公约数
例2 用更相减损术求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：用更相减损术求两个正数84与72的最大 公约数
更相减损术算法 第一步给定两个正整数不妨设m>n, 第二步若m,n都是偶数则不断用2约简使他 们不同时是偶数约简后的两个数仍记为 mn 第三步,d=mn 第四步,判断”d>0”是否成立若是则将n,d 中较大者记为m较小的记为n,返回第三步; 否则2^k*d(k是约简整数的2的个数)为所 求的最大公约数
第一步,给定两个正整数,不妨设m>n, 第二步,若m,n都是偶数,则不断用2约简,使他 们不同时是偶数,约简后的两个数仍记为 m,n 第三步,d=m-n 第四步,判断”d<>0”是否成立,若是,则将n,d 中较大者记为m,较小的记为n,返回第三步; 否则,2^k *d(k是约简整数的2的个数)为所 求的最大公约数. 更相减损术算法
开始 输m,n(m>n) K N=n/2 K=k+1 MEm/2 Mn为偶数?是 D=m-n 否 MEd D=m-n Ned MEn 否 D<>n? 是→ D>n? 输出2^kd 结束
开始 输m,n(m>n) K=0 M,n为偶数? K=k+1 M=m/2 N=n/2 D=m-n D<>n? 是 D>n? 否 M=n N=d D=m-n M=d 是 输出2^k d 结束 是 否
NPUT“mn=“mn While ds>n f msn then lF d>n then a=m mEn ELSE n=a mEn END IF K=0 End if WhILE m Mod 2=0 d=m-n anD n Mod 2=0 Wend m=m/2 d=2k'd n=n/2 Print d k=k+1 End WEND d=m-n
INPUT “m,n=“;m,n IF m<n THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n While d<>n IF d>n then m=d ELSE m=n n=d End if d=m-n Wend d=2^k*d PRINT d End
3.辗转相除法与更相减损术的比较: (1)都是求最大公约数的方法,计算上 辗转相除法以除法为主,更相减损术以减法为 主;计算次数上辗转相除法计算次数相对较少, 特别当两个数字大小区别较大时计算次数的区 别较明显。 (2)从结果体现形式来看,辗转相除法 体现结果是以相除余数为0则得到,而更相减损 术则以减数与差相等而得到
3.辗转相除法与更相减损术的比较: （1）都是求最大公约数的方法，计算上 辗转相除法以除法为主，更相减损术以减法为 主;计算次数上辗转相除法计算次数相对较少， 特别当两个数字大小区别较大时计算次数的区 别较明显。 （2）从结果体现形式来看，辗转相除法 体现结果是以相除余数为0则得到，而更相减损 术则以减数与差相等而得到