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

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

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),这样求解最小公倍数也不在话下了。

作者 @没有故事的老大爷

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345