《九章算术》——更相减损术 第一步:任意给定两个正整数;判断他们是 否都是偶数。若是,则用2约简;若不是则 执行第二步。 第二步:以较大的数减较小的数,接着把所 得的差与较小的数比较,并以大数减小数。 继续这个操作,直到所得的减数和差相等为 止,则这个等数就是所求的最大公约数
《九章算术》——更相减损术 第一步：任意给定两个正整数；判断他们是 否都是偶数。若是，则用2约简；若不是则 执行第二步。 第二步：以较大的数减较小的数，接着把所 得的差与较小的数比较，并以大数减小数。 继续这个操作，直到所得的减数和差相等为 止，则这个等数就是所求的最大公约数
2、更相减损术 (1)算理:所谓更相减损术,就是对于 给定的两个数,用较大的数减去较小的数 然后将差和较小的数构成新的一对数,再 用较大的数减去较小的数,反复执行此步 骤直到差数和较小的数相等,此时相等的 两数便为原来两个数的最大公约数
2、更相减损术 （1）算理：所谓更相减损术，就是对于 给定的两个数，用较大的数减去较小的数， 然后将差和较小的数构成新的一对数，再 用较大的数减去较小的数，反复执行此步 骤直到差数和较小的数相等，此时相等的 两数便为原来两个数的最大公约数
例3用更相减损术求98与63的最大公约数 解:由于63不是偶数,把98和63以大数减 小数,并辗转相减 98-63=35 63-35=28所以,98和63的 35-28=7最大公约数等于7 28-7=21 21-7=21 14-7=7 练习:月更相减损术求两个正数84与72的 最大公约数.12
例3 用更相减损术求98与63的最大公约数 解：由于63不是偶数，把98和63以大数减 小数，并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝21 14－7＝7 所以，98和63的 最大公约数等于7 用更相减损术求两个正数84与72的 最大公约数． 练习： 12
(2)算法步骤 第一步:输入两个正整数ab(a>b); 第二步:若a不等于b,则执行第三步;否则转 到第五步; 第三步:把a-b的差赋予r; 第四步:如果b>r那么把b赋给a,把r赋给b;否 则把r赋给a,执行第二步; 第五步:输出最大公约数b
（2）算法步骤 第一步：输入两个正整数a,b(a>b); 第二步：若a不等于b ,则执行第三步；否则转 到第五步； 第三步：把a-b的差赋予r; 第四步：如果b>r, 那么把b赋给a,把r赋给b;否 则把r赋给a，执行第二步； 第五步：输出最大公约数b
序框图(4)程序 开始 a。b 输入a,b WhilE as>b ≠b? 否 r=a-b If b>r then =a-b a=b a=r r<b》 b=r 走b ELSE a=r END F 输出b WEND 结束 print b
（3）程序框图 （4）程序 INPUT “a,b=“;a,b WHILE a<>b r=a-b IF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END 开始 输入a,b a≠b? 是 否 输出b 结束 b=r a=b r=a-b a=r 否 r<b? 是