求最大公约数的算法
求最大公约数的算法2010-07-11 22:43更相减损术
更相减损术,又称"等值算法"
关于约分问题,实质是如何求分子,分母最大公约数的问题。《九章算术》中介绍了这个方法,叫做"更相减损术",数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法。
例:今有九十一分之四十九,问约之得几何?
我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母。
"以少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之。"
译文如下:
约分的法则是:若分子、分母均为偶数时，可先被2除，否则，将分子与分母之数列在它处，然后以小数减大数，辗转相减，求它们的最大公约数，用最大公约数去约简分子与分母。
其与古希腊欧几里德所著的《几何原本》中卷七第一个命题所论的相同。列式如下:
91 49 42 49 42 7
35 7
28 7
21 7
14 7
7 7
这里得到的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)
每次所得两数与前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明。
这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施".吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.
更相减损法很有研究价值,它奠定了我国渐近分数,不定分析,同余式论和大衍求一术的理论基础.望能仔细品味。
辗转相除法
辗转相除法,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法,其可追溯至前300年。它首次出现于欧几里德的《几何原本》(第VII卷，命题i和ii)中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
:
设两数为a、b(b
本文档为【求最大公约数的算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483