算法卷轴(计算卷)[最大公约数]

  • 时间:
  • 来源:互联网
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/afsya/article/details/103344783

辗转相除法

max 和 min 的最大公约数 = (max%min) 和 min 的最大公约数,当 max%min = 0 时,min 就是最大公约数。

更相减损法

max 和 min 的最大公约数 = (max-min) 和 min 的最大公约数,max = min 时,min 就是最大公约数。

更相减损法 + 移位运算

a、b 都为偶数:(a/2, b/2)*2
a 为偶数、b 为奇数:(a/2, b)
a 为奇数、b 为偶数:(a, b/2)
a、b 都为奇数:更相减损法

public class Main {

    static int getMaxCommonDivisor(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {
            // a、b 都为偶数:返回 getMaxCommonDivisor(a/2, b/2)*2
            return getMaxCommonDivisor(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            // a 为偶数、b 为奇数:返回 getMaxCommonDivisor(a/2, b)
            return getMaxCommonDivisor(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            // a 为奇数、b 为偶数:返回 getMaxCommonDivisor(a, b/2)
            return getMaxCommonDivisor(a, b >> 1);
        } else {
            // a、b 都为奇数:更相减损法
            int max = a > b ? a : b;
            int min = a < b ? a : b;
            return getMaxCommonDivisor(min, (max - min));
        }
    }

    public static void main(String[] args) {
        int result = getMaxCommonDivisor(105, 75);
        System.out.println(result);
    }

}

本文链接http://element-ui.cn/news/show-475.html