0%

求最大公约数

求最大公约数有三种方式

  1. 暴力穷举法
  2. 辗转相除法
  3. 更相减损术

    暴力穷举法

    暴力穷举法的思路:从两个数之间找最小的数,然后用这个数往下减,若是两个数都能够被整除,那个数就是最大公约数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int maxNumber(int m, int n) {
    int temp = m > n ? n : m;
    for (int i = temp; i > 0; i--) {
    if (m % i == 0 && n % i == 0) {
    return i;
    }
    }
    return 0;
    }

这种算法的效率太慢。要是笔试写这个分分钟回去等通知。

辗转相除法

辗转相除法有两种方式,维基百科和百度百科对于辗转相除法的定义有些出入
百度百科:最大公约数等于a除以b的余数c和b之间的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
int maxNumber(int m, int n) {
int temp;
if (n > m) {
temp = n;
n = m;
m = temp;
}
if (m % n == 0) {
return n;
}
return maxNumber(n, m % n);
}

维基百科:最大公约数等于其中较小的数和两数的差的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
int maxNumber(int m, int n) {
int temp;
if (n > m) {
temp = n;
n = m;
m = temp;
}
if (m % n == 0) {
return n;
}
return maxNumber(m - n, n);
}

更相减损术

更相减损术出自《九章算术》
原文描述:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。
白话文译文:如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

  1. 任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
  2. 以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
  3. 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxNumber(int m, int n) {
if (m == n) {
return n;
}
if (n > m) {
return maxNumber(n,m);
}else {
// 同为偶数
if((m&1) == 0 && (n&1)==0){
return maxNumber(m >> 1, n >> 1) << 1;
}else if((m&1) == 0 && (n&1) !=0){
return maxNumber(m >>1,n);
}else if((m&1) != 0 && (n&1) ==0){
return maxNumber(m,n>>1);
}else {
return maxNumber(n,m - n);
}
}
}