一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 599|回复: 3
收起左侧

[编程题] 【基础算法】浅谈辗转相除法

[复制链接] |试试Instant~ |关注本帖
回帖奖励 7 根萝卜 回复本帖可获得 1 根萝卜奖励! 每人限 1 次(中奖概率 60%)
619899442 发表于 2014-7-16 22:09:18 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
辗转相除法作为一种计算最大公约数的算法十分的行之有效,下面lz简单的做一些介绍
首先,本文的讨论范围仅限于非负整数范围内!
解法一
说到辗转相除法,大家第一反应可能就是高中数学必修3的那个框图了,如下所示(百度百科扣的图):
1.PNG
框图的计算速度还是十分可观的,貌似使用了动态规划的思想
只可惜计算虽快,却不容易记忆,为什么不容易记忆呢?因为这种循环算法比较难以理解且正确性比较难以证明。高中的时候应该不会有人会无聊到证明一个算法的正确性吧。。。

下面lz给出比较容易理解的解法二
嘛,先从数学推导开始:
给出两个正整数a,b,a!=b(否则还算个p最大公约啊)这里不妨假设较大者为a,并且假设他们的最大公约数为k
可以写出关系式:a=m*k b=n*k  (a, b, m, n, k 都是整数,且m n互质)
那么: a-b=(m-n)*k 可以得到 (a-b) 与a b 具有相同的最大公约数k,由此求a b最大公约数的问题化为了求a-b b的最大公约数的问题
为什么这里要把 a b 的问题转化为a-b b 的问题呢? 因为这样做的本质是为了把两个数减小,反复多次后,有一个数必然会减小到0,这时问题得以解决(一个数与0的最大公约数即为它本身)

可以把这个结论总结为一句话:两个整数的最大公约数就是他们的差的绝对值和他们较小的那个数的最大公约数
跟据这句话就可以着手码代码了:

#include <cassert>
//取两个数最小值
int min(int a, int b){
    if (a > b) return b;
    else return a;
}
//取两个数最大值
int max(int a, int b){
    if (a > b) return a;
    else return b;
}

int gcd(int lg, int sm){
    if (sm == 0) return lg;  //递归终止条件,一个数减小到0
    else {
        //assert(lg >= sm);
        return gcd(max(sm,lg-sm), min(sm,lg - sm));   //两个整数的最大公约数就是他们的差的绝对值和他们较小的那个数的最大公约数
    }
}

怎么样,代码非常容易理解吧~

上面的解法效率不是很高,尤其是在判断两个数的大小关系的时候,有没有什么办法规避掉判断大小的问题呢?下面lz给出解法三
断言:a b的最大公约数=a%b b的最大公约数  (设a大于b)
证明:
由a=m*k b=n*k
则a%b=(mk)%(nk)
由m n 互质得到   m=n*i+m%n  ( m%n!=0 )
上式两段乘以 k
mk=nk*i + (k*m%n)
即(mk)%(nk)=k*(m%n)
所以   a%b=k*(m%n)   b=k*n
显然m%n是正整数,则a%b b 也有最大公约数k(由于m n互质,用反证法已证m%n n 互质)
这样,求a b的问题就可以化为求 a%b b的问题了~ 这是至关重要的:a%b<b是无条件成立的,这意味着我们不需要在程序运算中判断大小了

类似的,下面给出代码实现:
int gcd2(int lg, int sm){
    if (sm == 0)    return a;
    return gcd2(sm, lg%sm);  
}

只有简单的4行代码,怎么样,很优雅很有艺术感吧~~~

ps 本文中给出的gcd 和gcd2 函数中,lg带入较大的数字,sm带入较小的数字!


评分

1

查看全部评分

RickyYe 发表于 2014-7-16 22:21:31 | 显示全部楼层
可以改成非递归的
  1. int gcd(int a, int b) {
  2.     if (0 == a || 0 == b) {
  3.         return max(a, b);
  4.     }
  5.     int t;
  6.     while ((t = a % b) != 0) {
  7.         a = b;
  8.         b = t;
  9.     }
  10.     return b;
  11. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 619899442 发表于 2014-7-16 22:26:27 | 显示全部楼层
RickyYe 发表于 2014-7-16 22:21
可以改成非递归的

这应该是第一种框图的解法吧,我个人觉得不如递归直观
回复 支持 反对

使用道具 举报

Arkansol 发表于 2014-7-22 12:02:16 | 显示全部楼层

回帖奖励 +1 根萝卜

greatest common divisor DD
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 02:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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