最大公约数

发表于 更新于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟
引言：

求两个数的最大公约数

最大公约数

经典的问题，这里我们直接给出三种算法

辗转相除法（欧几里得算法）：两个正整数a和b(a>b)，他们的最大公约数等于 a 除以 b 的余数 c 和 b（小的那个数） 之间的最大公约数。递归出口是（a%b==0）

更相减损术：两个正整数a和b(a>b)，他们的最大公约数等于a-b的插值c和较小数b的最大公约数。递归出口是(a == b)

综合方法：

  1. 如果a,b均为偶数 gcd(a,b) = 2*gcd(a/2,b/2) = gcd(a>>1,b>>1)<<1
  2. 如果a,b一个奇数一个偶数 gcd(a,b) = gcd(偶数/2,奇数) = gcd(偶数>>1, 奇数)
  3. 如果a,b均为奇数 (a>b) gcd(a,b) = gcd(a-b,b) 此时 a-b 为偶数

递归出口是（a==b）

思考如图：

IMG_0031

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * @author 董文浩
 * @Date 2020/7/10 19:57
 * 求两个数的最大公约数
 */
public class GreatestCommonDivisor {
    /**
     * 求一个数的最大公约数，是很经典的问题了
     * 我们主要列出以下几种方法：
     * 1. 辗转相除法（欧几里得算法）
     * 2. 更相减损术
     * 3. 融合两种方法特点的最佳方法
     */

    /**
     * 欧几里得算法：两个正整数a和b(a>b)，他们的最大公约数等于 a 除以 b 的余数 c 和 b（小的那个数） 之间的最大公约数
     */
    public static int euclidean(int a, int b){
        int bigger = a > b ? a : b;
        int smaller = a > b ? b : a;
        if(bigger % smaller == 0){
            return smaller;
        }
        return euclidean( bigger%smaller ,smaller);
    }

    /**
     * 更相减损术：两个正整数a和b(a>b)，他们的最大公约数等于a-b的插值c和较小数b的最大公约数
     */
    public static int morePhaseLoss(int a , int b){
        if(a == b){
            return a;
        }
        int smaller = a > b ? b : a;
        int bigger = a > b ? a : b;
        return morePhaseLoss(bigger - smaller , smaller);
    }

    /**
     * 综合方法：
     *          1. 如果a,b均为偶数  gcd(a,b) = 2*gcd(a/2,b/2) = gcd(a>>1,b>>1)<<1
     *          2. 如果a,b一个奇数一个偶数 gcd(a,b) = gcd(偶数/2,奇数) = gcd(偶数>>1, 奇数)
     *          3. 如果a,b均为奇数 (a>b) gcd(a,b) = gcd(a-b,b) 此时 a-b 为偶数
     */
    public static int gcd(int a , int b){
        if( a==b){
            return a;
        }
        if((a&1)==0 && (b&1) == 0){
            //全是偶数
            return gcd(a>>1,b>>1)<<1;
        }else if((a&1)!=0 && (b&1) == 0){
            //a为奇数，b为偶数
            return gcd(a,b>>1);
        }else if((a&1)==0 && (b&1) != 0){
            //a为偶数，b为奇数
            return gcd(a>>1,b);
        }else {
            int smaller = a > b ? b : a;
            int bigger = a > b ? a : b;
            return gcd(bigger-smaller,smaller);
        }
    }
    public static void main(String[] args) {
        // 辗转相除法测试
        System.out.println(euclidean(25,10));
        System.out.println(euclidean(100,80));
        System.out.println(euclidean(27,14));
        // 更相减速术测试
        System.out.println(morePhaseLoss(25,10));
        System.out.println(morePhaseLoss(100,80));
        System.out.println(morePhaseLoss(27,14));
        // 综合方法
        System.out.println(gcd(25,10));
        System.out.println(gcd(100,80));
        System.out.println(gcd(27,14));
        //输出均为 5 、20 、 1

    }

}

快速判断是奇数还是偶数，与1（&1）

1
例如	7 -> 二进制