更相减损术的算法步骤

㈠ 更相减损法是什么原理是什么

更相减损法是出自《九章算术》的一种求最大公约数的算法。

原理：任意给定两个正整数，判断它们是否都是偶数。若是则用2约简，若不是则以较大的数减较小的数，然后把所得的差与较小的数比较，并以大数减小数，直到所得的减数和差相等为止。

㈡ 用相减损术求288与153的最大公约数

288和153一奇数一偶数，288-153=135，153-135=18，135-18=117，117-18=99，99-18=81，81-18=63，63-18=45，45-18=27，27-18=9，18-9=9

所以，288和153的最大公约数是9

• 更相减损术求两个数的最大公约数的方法步骤：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

㈢ 什么是更相减损之术

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
用更相减损术求98与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，并辗转相减：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数等于7。

㈣ 更相减损术的算法步骤

更相减损法有点类似于求最大公约数的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

㈤ 更相减损法 为什么可以用于求最大公约数呢即它的原理是什么

我认为更相减损法的原理就是同余啊。
两数X = AP，Y = BP
P是最大公约数，A>B且互素，则BP、（A-B）P同样必有最大公约数P，
更相减损，最后必求得1P。

㈥ 辗转相除法和更相减损之术分别是什么

辗转相除法，
又名欧几里德算法（Euclidean
algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
另一种求两数的最大公约数的方法是更相减损法。

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专着，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

白话文译文：（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

希望我的回答对您有所帮助，春节快乐，学习进步！

㈦ 更相减损术的方法

更相减损术,又称"等值算法"
“关于约分问题,实质是如何求分子,分母最大公约数的问题.
例如：求441和378的最大公约数
1.由于均不为偶数，不必同除以2（同为偶数则需要）
2.
把大数减去小数
441-378=
63
3.比较减数和差的大小
用大的减去小的
378-63=315
4.同上
315-63=252
252-63=189
189-63=126
126-63=
63
5.当差在运算过程中出现2次相同的时候
差即为最大公约数（63出现了2次）
其实这比较麻烦
当数较大时
减死人
可以用辗转相除法做容易些

㈧ 更相减损法的概述

古法探源(1)
更相减损法,又称等值算法
“关于约分问题,实质是如何求分子,分母最大公约数的问题.<九章算术>中介绍了这个方法,叫做”更相减损术”,数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法,中学生应该掌握它.
例1.今有九十一分之四十九,问约之得几何?
我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母,”以少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之.”译文如下：约分的法则是：若分子、分母均为偶数时，可先被2除，否则，将分子与分母之数列在它处，然后以小数减大数，辗转相减，求它们的最大公约数，用最大公约数去约简分子与分母。其与古希腊欧几里德所着的《几何原本》中卷七第一个命题所论的相同。列式如下:
91≡42（mod49)
49≡7（mod42)
7│42
这里得到的7就叫做”等数”,91和49都是这等数的重叠(即倍数),故7为其公约数.而7和7的最大公约数就是7,(7,7)=7,所以 (91,49)=(42,7)=(7,7)=7
更相减损术在现代仍有理论意义和实用价值.吴文俊教授说:”在我国,求两数最大公约数即等数,用更相减损之术,将两数以小减大累减以得之,如求24与15的等数,其逐步减损如下表所示: (24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得两数与前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明.
这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施”.吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.
更相减损法很有研究价值,它奠定了我国渐近分数,不定分析,同余式论和大衍求一术的理论基础.望能仔细品味

㈨ 更相减损法是什么原理是什么

更相减损术,或称“辗转相除法”是用来求最大公约数的． 给出两个正整数a和b，用b除a得商a0，余数r，写成式子：a=a0b+r，0≤r＜b． ..........(1) 这是最基本的式子．如果r等于0，那么b可以除尽a，而a、b的最大公约数就是b． 如果r≠0，再用r除b，得商a1，余数r1，即：b=a1r+r1，0≤r1＜r．............ (2) 如果r1=0，那么r除尽b，由(1)也除尽a，所以r是a、b的公约数．反之，任何一个除尽a、b的数，由(1)，也除尽r，因此r是a、b的最大公约数． 如果r1≠0，则用r1除r得商a2，余数r2，即：r=a2r1+r2，0≤r2＜r1． ...........(3) 如果r2=0，那么由(2)可知r1是b、r的公约数，由(1)，r1也是a、b的公约数．反之，如果一数除得尽a、b，那末由(1)，它一定也除得尽b、r，由(2)，它一定除得尽r、r1，所以r1是a、b的最大公约数． 如果r2≠0，再用r2除r1，如法进行．由于b＞r＞r1＞r2＞......逐步小下来，而又都是正整数，因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1)．这就是有名的辗转相除法，在外国称为欧几里得算法． 例子:求42897与18644的最大公约数： 42897=2×18644+5609， (i) 18644=3×5609+1817， (ii) 5609=3×1817+158， (iii) 1817=11×158+79， (iv) 158=2×79． 所以，42897与18644的最大公约数=79