更相減損術的演算法步驟

㈠ 更相減損法是什麼原理是什麼

更相減損法是出自《九章算術》的一種求最大公約數的演算法。

原理：任意給定兩個正整數，判斷它們是否都是偶數。若是則用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