【基础算法】浅谈辗转相除法

辗转相除法作为一种计算最大公约数的算法十分的行之有效，下面lz简单的做一些介绍
首先，本文的讨论范围仅限于非负整数范围内！
解法一：
说到辗转相除法，大家第一反应可能就是高中数学必修3的那个框图了，如下所示（百度百科扣的图）：

框图的计算速度还是十分可观的，貌似使用了动态规划的思想
只可惜计算虽快，却不容易记忆，为什么不容易记忆呢？因为这种循环算法比较难以理解且正确性比较难以证明。高中的时候应该不会有人会无聊到证明一个算法的正确性吧。。。

下面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. 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. }

复制代码

RickyYe 发表于 2014-7-16 22:21
可以改成非递归的

这应该是第一种框图的解法吧，我个人觉得不如递归直观

greatest common divisor DD