最大公约数算法解析

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

给定两个正整数,求其最大公约数,相信这是每一个写代码的同学绝壁遇见过的练习,当然解法也非常多,下面先给出一个没有经过任何算法处理的程序:
public static int getResult(int a,int b){

    int max = (a>b)?a:b;
    int result=0;
    for(int i = 1;i < max;i++){
        if(a%i == 0 && b%i == 0){
            result=i;
        }
    }
    return result;
}

这样当然是可以解出来的,但是要循环遍历其中较大的正整数,如果两个数量都非常大的话,效率是非常低的,每当遇到效率低下的程序,我们必然会想到优化,算法优化总是很靠谱的一种方法。下面就列出几种添加算法的方法来解决最大公约数的问题。

解法一:
辗转相除法,假设求正整数 num1,num2 的最大公约数,假设f(x,y)为两者的最大公约数,取 k = x / y (取整),b = x % y (取余);则 x = k y + b ;那么能同时被x ,y整除的数必然也同时能被 b , y 整除,能被b , y整除的数也能同时被x,y整除,也就是说,x,y的最大公约数就是b,y的最大公约数,则有 f (x , y) = f(y , x%y) (x>=y>0),这样递归运算,比如
f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; 这样将运算次数直接降低了很多。下面附上代码:
private static int gcd(int x, int y) {
int result = ((y == 0) ? x : gcd(y, x % y));
return result;
}

解法二:
解法一虽然很好的解决了求公约数的问题,但是算法中包含有除法,在计算机中除法的开销是很大的,能不能不用除法呢。可以这样考虑,一个数能被x , y整出,必然也能被x-y,y整出,也就是一个数被x,y整出是这个数被x-y,y整出的充分必要条件。那么f(x, y) = f(x-y , y);这样计算的话,就可以把大整数之间的取模运算转换为大整数之间的减法运算。由于f(x,y)= f(y,x),为了避免求出一个正数和一个负数的最大公约数,要灵活运用f(x,y)= f(y,x),迭代进行,直到一方为0;比如:
f(42,30) = f(30,12) = f(18 , 12)= f(12 , 6) = f(6,6)= f(6 , 0) = 6;这样运算跟上面的方法比起来,优化了大数据取模的问题,但是运算次数会增大,代码如下:
private static int gcd(int x, int y) {
if (y == 0) {
return x;
}
if (x < y) {
return gcd(y, x);
} else {
return gcd(x - y, y);
}
}

解法三:
解法一的不足之处在于复杂的大数据除法运算,解法二虽然干掉了大数据的除法运算,但是增加了操作次数。两种方法都不是非常的完美,那么我们就用第三种方法来解决,第三种方法使用的二进制方案,估计很多同学看到01100100就要放弃了,千万不要,其实这东西不难。
对于x,y来说,有x=k * x1,y = k * y1 ,则f(x ,y) = f(k * x1,k * y1) = k * f(x1 ,y1);此为一。
另外,如果 x = p * x1,且p为素数,y%p != 0,则f(x ,y)= f(p * x1, y) = f(x1 ,y);此为二。

由一和二两个公式,我们可以计算公约数了:
设p=2:
假设x,y都是偶数:f(x,y)= 2f(x>>1,y>>1); 假设x是偶数,y是奇数:f(x,y) = f(x>>1,y); 假设x是奇数,y是偶数:f(x,y) = f(x,y>>1); 假设x,y都是奇数:f(x,y) = f(y,x-y);---这是根据解法二中推出来的 下面还以42 和 30 为例: f(42,30) = f(101010,11110) = 2f(10101,1111) = 2f(1111,110)=2 * f(1111,11) = 2 f (1100,11) = 2f(110,11)=2 f(11,11) = 2* f(0,11) = 2* 3=6
括号中均为二进制表达,这样最坏的情况下,复杂度也就是log 2(max(x,y));----2是底数,尼玛,这格式弄不出来。

下面附上代码:
private static int gcd(int x, int y) {
if (x < y) {
return gcd(y, x);
}
if (y == 0) {
return x;
}
if (isEven(x)) {
if (isEven(y)) {
// x,y都为偶数,f(x,y)=2f(x/2,y/2) return gcd(x >> 1, y >> 1) << 1; } else { // x偶数,y奇数,f(x,y)=f(x/2,y) return gcd(x >> 1, y); } } else { if (isEven(y)) { // x奇数,y偶数,f(x,y)=2f(x,y/2)
return gcd(x, y >> 1);
} else {
// x,y都为奇数,f(x,y)=f(x-y,y)
return gcd(x - y, y);
}
}
}

public static boolean isEven(int x) {
    return (x % 2 == 0) ? true : false;
}

以前根本没有想过这么些玩意,第一次看算法,顿时感觉高大上啊,不过的确,看到这样解决以前常用来解决的公约数问题,的确眼前一亮啊,希望大家多多给意见哦~

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看