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

  Seves

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

    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是偶数,否则是奇数

    1. 最小公倍数

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

    作者 @没有故事的老大爷

    24