更相减损术的算法步骤

更相减损法有点类似于求最大公约数的Stein算法。在更相减损法中，若两个是偶数则同除以2，结果乘以2。如果增加一个判断，若为一奇一偶则偶数除以2，结果不变，若为两个奇数才相减，这样就变成了目前计算大整数最大公约数的非常好的一个算法，Stein算法。

更相减损法： *** 作甲数乙数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.

你确定WHILE后面的"a＜ ＞b"没写错？好奇怪的循环条件喔。

忽略掉循环条件的话，程序就这样解读了：

INPUT a,b——输入a,b

WHILE a＜ ＞b——判断是否满足条件，如果是则开始循环，不是则直接不运行循环

IF a ＞ b THEN——如果a>b，那么

a=a-b——把a-b的值代入a

ELSE——如果a>b不成立，即a<=b

b=b-a——把b-a的值代入b

END IF——IF条件语句结束

WEND——循环结束，判断循环条件，如果满足则回去开始循环，如果不满足则跳出循环

PRINT a——输出a的值

END——程序结束

---