家长易论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1604|回复: 10
打印 上一主题 下一主题

[世奥赛] 辗转相除法

[复制链接]
跳转到指定楼层
楼主
发表于 2012-3-30 13:48:58 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
document对象

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

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

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.
分享到:  QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享分享 分享淘帖
沙发
 楼主| 发表于 2012-3-31 17:27:41 | 只看该作者
据说现在流行自己顶自己!!!
板凳
发表于 2012-4-7 14:59:42 | 只看该作者
凄惨....我来顶...
地板
发表于 2012-4-8 16:32:34 | 只看该作者
必须顶  
5
发表于 2012-4-8 16:32:34 | 只看该作者
怎么说呢,太感激你了,楼主
6
发表于 2012-4-11 11:04:41 | 只看该作者
说的真有道理啊!
7
发表于 2012-4-11 11:04:41 | 只看该作者
很好啊啊啊  
8
发表于 2012-4-13 14:06:33 | 只看该作者
就为赚分嘛  
9
发表于 2012-4-13 14:06:33 | 只看该作者
好 好帖 很好帖 确实好帖 少见的好帖  
10
发表于 2012-4-16 17:02:54 | 只看该作者
谁能送我几分啊  
11
发表于 2012-4-28 17:18:52 | 只看该作者
牛牛牛牛  
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|网站地图|家长易论坛 ( 鄂ICP备16011226号-1  点我聊天

GMT+8, 2024-11-30 05:14

Powered by 家长易

快速回复 返回顶部 返回列表