辗转相除法

梦泉森林 · 发表于 2012-3-30 13:48:58

马上注册，结交更多家长，享用更多功能，让你轻松玩转家长易社区。

您需要登录才可以下载或查看，没有帐号？立即注册

x

辗转相除法又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法，其可追溯至3000年前。

　　在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

　　两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2） × 252。这个重要的等式叫做贝祖等式。

与短除法和分解质因数相比，辗转相除法在求两个相差很多或者两个很大的数的最大公约数时，能过较快的求出结果。而短除法和分解质因数面对较大的数时，往往显得过程复杂。有时候甚至难以判断下一个能被分解出来的质因数是多少。

例1，求2772和2970的最大公约数。

短除法：先提质因数2.变成1386与1485；

提出质因数3.变成462与495；

提出质因数3.变成154与165；

提出质因数11.变成14与15，不能再分解。

所求最大公约数为：2*3*3*11=198

辗转相除法：2970-2772=198 变成求2772与198的最大公因数；

2772/198=14,2772与198的最大公因数为198.

所以2772与2970的最大公约数为198.

例2，求151018和2157668的最大公因数。

短除法：先提质因数2.变成75509和1078834

而接下来该提出多少？

辗转相除法：2157668/151018=14……43416 2157668-14*151018=43416 变成求151018与43416的最大公约数；

151018/43416=3……20770 151018-3*43416=20770 变成求43416与20770的最大公约数；

43416/20770=2……1876 43416-2*20770=1876 变成求20770与1876的最大公约数；

20770/1876=11……134 20770-11*1876=134 变成求1876与134的最大公约数；

1876/134=14 所以1876与134的最大公约数是134.

所以151018与2157668的最大公约数是134.

梦泉森林 · 发表于 2012-3-31 17:27:41

据说现在流行自己顶自己！！！

790682666 · 发表于 2012-4-7 14:59:42

凄惨....我来顶...

xiuxuan · 发表于 2012-4-8 16:32:34

必须顶

常青树 · 发表于 2012-4-8 16:32:34

怎么说呢，太感激你了，楼主

starxzj · 发表于 2012-4-11 11:04:41

说的真有道理啊！

火冰狐 · 发表于 2012-4-11 11:04:41

很好啊啊啊

YY-LIN · 发表于 2012-4-13 14:06:33

就为赚分嘛

boomy · 发表于 2012-4-13 14:06:33

好好帖很好帖确实好帖少见的好帖

快乐的老鼠 · 发表于 2012-4-16 17:02:54

谁能送我几分啊

tianbo · 发表于 2012-4-28 17:18:52

牛牛牛牛

		自动登录	找回密码
密码			立即注册

[世奥赛] 辗转相除法

马上注册，结交更多家长，享用更多功能，让你轻松玩转家长易社区。