思构A氯湘除法中天是顺题装构 辗转相除法是一个反复执行直到余数等于0停止 的步骤,这实际上是一个循环结构。m=n×q+r 用程序框图表示出右边的过程8251-6105×1+2146 r=m mod n 6105=2146×2+1813 m=n 2146=1813×1+333 n=r 1813=333×5+148 ? 否 是 333=148×2+3 148=37×4+0
辗转相除法是一个反复执行直到余数等于0停止 的步骤，这实际上是一个循环结构。 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否
《九章算术》一一更相减损术 算理:可半者半之,不可半者,副置分母、子之数, 以少减多,更相减损,求其等也,以等数约之 第一步:任意给顶两个正整数;判断他们是否都是 偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差 与较小的数比较,并以大数减小数。继续这个操作, 直到所得的减数和差相等为止,则这个等数就是所 求的最大公约数
《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数， 以少减多，更相减损，求其等也，以等数约之。 第一步：任意给顶两个正整数；判断他们是否都是 偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差 与较小的数比较，并以大数减小数。继续这个操作， 直到所得的减数和差相等为止，则这个等数就是所 求的最大公约数
例3用更相减损术求98与63的最大公约数 解:由于63不是偶数,把9和63 以大数减小数,并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98和63的最大公约数等于7
例3 用更相减损术求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