更相减损法: *** 作甲数乙数Stein算法: *** 作甲数乙数 9863 986398-63=35633598是偶数,除以2496363-35=283528都是奇数,63-49=14491435-28=728714是偶数,除以249728-7=2172149-7=4242721-7=1471442是偶数,除以221714-7=77721-7=14147 7-7=07014是偶数,除以277 7-7=070
更相减损术《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”
翻译成现代语言如下:
第一步:任意给定两个正整数;判断它们是否都是偶数.若是,则用2约简;若不是则执行第二步.
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个 *** 作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数.
其中所说的“等数”,就是最大公约数.求“等数”的办法是“更相减损”法,实际上就是辗转相除法.
例 用更相减损术求98与63的最大公约数
由于63不是偶数,把98和63以大数减小数,并展转相减
98-63=35
63-35=28
35-28=7
28-7=14
14-7=7
所以,98和63的最大公约数等于7.
第一步:输入两个正整数a,b(a>b)第二步:若a不等于b ,则执行第三步;否则转到第五步;
第三步:把a-b的差赋予r
第四步:如果b>r,那么把b赋给a,把r赋给b否则把r赋给a,执行第二步;
第五步:输出最大公约数b.
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)