小灰算法(二): 可能是小学老师没教你的最大公约数算法

2019-11-05 本文已影响0人没有故事的老大爷

文章参考自书籍：《漫画算法-小灰的算法之旅》-魏梦舒

1.暴力枚举法

最大公约数是我们在小学都学过的，是最基本的数学知识，基本的我们都没有怀疑过它是否有更好的方法去计算。因为笔者当年的老师教我们从最小的数一直往上试，看看能不能同时被这俩整数整除，一直循环下去就能计算出最大公约数了。比如求10和25的最大公约数，大家或许会先试2，发现不是。然后试3，然后4...，一直到5。10/5=2,25/5=5. 2和5已经没有共同可分解的因数了。所以最大公约数是5. 如果用代码来写，可能会稍微有些不同，但是基本思路也是用一个循环去试出来最大的公约数。时间复杂度为O(N). 代码如下：

    public static int gcdV1(int a, int b) {
        int big = a>b ? a:b;
        int small = a<b ? a:b;
        if (0==(big%small)) {  // 边界条件
            return small;
        }
        for (int i=small/2; i>1; i--) {
            if (0==(small%i) && 0==(big%i)) {
                return i;
            }
        }
        return 1;
    }

2. 辗转相除法

但是如果作为一道面试题，肯定不会这么简单，或许还有更好的方法等着我们去探索。这时候请出我们的欧几里得大神。

欧几里得

他提出了辗转相除法。这个算法是一条定理：两个正整数a和b (a>b), 它们的最大公约数等于a除以b的余数c和b之间的最大公约数。例如25和10,25除以10商2余5，那么25和10的最大公约数等同于10和5的最大公约数。所以在代码中我们可以用这条定理去递归，将比较大的整数运算简化成较小的运算，直到其中较小的数是1(能被较大数整除)为止。代码如下：

    public static int gcdV2(int a, int b) {
        int big = a>b ? a:b;
        int small = a<b ? a:b;
        if (0==(big%small)) {  // 边界条件
            return small;
        }
        return gcdV2(big%small, small);
    }

3. 更相减损术

辗转相除法的思路确实不错，但是其中的a%b取模运算在大整数的情况下性能会比较差劲。这时候还得看我国古代的《九章算术》提出的更相减损术。原理如下：

九章算术

两个正整数a和b (a>b)，它们的最大公约数等于a-b的差值c和较小数b的最大公约数。例如25和10,25减去10的差是15，那么25和10的最大公约数等同于15和10的最大公约数。利用此原理我们可以写出如下代码：

    public static int gcdV3(int a, int b) {
        if (a == b) {  // 边界条件
            return a;
        }
        int big = a>b ? a:b;
        int small = a<b ? a:b;
        return gcdV3(big-small, small);
    }

4. 更相减损与移位相结合

更相减损法确实规避了取模这种性能差的运算，但是递归深度明显增加了。比如计算1000和1的最大公约数会递归999次。要是能结合辗转相除和更相减损的共同优点就好了。所以我们总结出了这样一种gcd算法。规则如下：

(1) 当a和b均为偶数时，gcd(a,b) = 2gcd(a/2, b/2)=2gcd(a>>1, b>>1);
(2)当a为偶数b为奇数时，gcd(a,b) = gcd(a/2, b)=gcd(a>>1, b);
(3)当a为奇数b为偶数时，gcd(a,b) = gcd(a, b/2)=gcd(a, b>>1);
(4)当a和b均为奇数时，先利用更相减损术一次 gcd(a,b) = gcd(b, a-b)，此时a-b一定为偶数，然后又可以套用上面的规则继续计算了。

例如我们还是计算25和10的最大公约数，步骤如下。

1.gcd(25,10) = gcd(25, 5)

2.gcd(25,5) = gcd(20,5) // 更相减损术

3.gcd(20,5) = gcd(10,5)

4.gcd(10,5) = gcd(5,5)

5.gcd(5,5)因为两数想等，所以最大公约数是5 // 更相减损术

哦可，talk is cheap, show U the code.

    public static int gcdV4(int a, int b) {
        if (a == b) {  // 边界条件
            return a;
        }
        if (0==(a&1) && 0==(b&1)) {
            return gcdV4(a>>1, b>>1)<<1;
        } else if (0==(a&1) && 0!=(b&1)) {
            return gcdV4(a>>1, b);
        } else if (0!=(a&1) && 0==(b&1)) {
            return gcdV4(a, b>>1);
        }  else {
            int big = a>b ? a:b;
            int small = a<b ? a:b;
            return gcdV4(big-small, small);
        }
    }

注：(a&1)==0说明a是偶数，否则是奇数

最小公倍数

最小公倍数等于: (a*b)/gcd(a,b)，这样求解最小公倍数也不在话下了。

作者 @没有故事的老大爷

小灰算法(二): 可能是小学老师没教你的最大公约数算法

猜你喜欢

热点阅读