java 算法基础之一找寻最大公约数

2013-10-05

java 算法基础之一寻找最大公约数最近发现在搞Android的都要懂一点数据结构和算法才能进阶到高手，所以就回

java 算法基础之一寻找最大公约数
最近发现在搞Android的都要懂一点数据结构和算法才能进阶到高手，所以就回去复习了一下基础，为一些公司招聘做题做准备。
今天研究了一下最大公约数的求法，在网上也找了不同的解法，现在就想总结一下，拿出来分享给大家，共同学习
首先讲一个什么是公约数，这个问题我们小学都学过，可能有一部分人已经忘记了，所以还是讲一下，假设有两个数a,b,所谓的公约数就是能把a,b整除的最大整数。

明白了要求我们就来解决问题，一拿到问题我们都应该都能想到一个方法，就是使用穷举法，从2开始一个个找，到一个两个都能除的就记录起来，一直找到小于min(a,b)结束，
记录到的值就是他们的最大公约数代码由下：

//找出最大公约数,穷举法        public static int getMaxDivide_ab(int a,int b){                int value=1;                int max;                int min;                if(a==b){                        return a;                }                if(a>b){                        max=a;                        min=b;                }else{                        max=b;                        min=a;                }                for(int i=2;i<min;i++){                        if(0==max%i && 0==min%i){                                value=i;                        }                }                return value;        }

第二种方法是使用欧几里德算法，这个已经有2000+年的历史了，这个比起上一个来的要高效，假设我们的最大公约数表示为f(a,b),并且有a>=b>0,
欧几里德就给了我们一个很好的定理，f(a,b)=f(b,a%b),有了这个等式我们就很容易得出这个算法的递归式，现在我们来看下这个等式是怎么来的
设有 r=a/b ,q=a%b
所以就有 a=a/b*b+q ----(这里的a/b*b!=a ，原因就是我们用的是整数来计算的)
也就是a=r*b+q 变换一下有：q=a-r*b 设d=f(a,b)，a/d=m,b/d=n;则有q=dm-r*dn=d(m-rn)
所以q/d也为0；设d|q表示d是q的约数；以下相同；
又有d|b;所以有d|(b,q),设D是(b,q)的最大公约数，则会有d<=D=f(b,q);

再回到前面r=a/b,q=a%b这两个条件有
a=r*b+q,由于D|(b,q),所以D|a,所以有D|(a,b)
所以有D<=d=f(a,b),结合上部分就有d<=D <+d,及D=d;
所以得证；
代码实现由下：

public static int oujilide(int a,int b){                if(a<b){                        int temp;                        temp=a;                        a=b;                        b=temp;                }                if(0==b){                        return a;                }                return oujilide(b,a%b);        }

第三种方法是上一种的变形

我们在对大整数求最大公约数，第二种方法的效率就出现了瓶颈，实际上对于大整数而言，取模运算（用到除法）的开销非常的昂贵，这就是欧几里得算法的局限性，那么我们就得优化一下它了，借鉴欧几里得的辗转相除法，既然是取模运算导致的问题，那么我们就不用取模运算，换用“-”运算，即 f(x,y)=f(x-y,y);深入考虑一下发现在算法运行的过程可能会出现x<y的情况，这时候要交换x和y，但是结果不受影响。
这个方法的证明可以看上面一种给出的证明，细想一下都是一样的
实现代码也很简单：
public static int xymod(int a,int b){
                if(a<b){
                        int temp;
                        temp=a;
                        a=b;
                        b=temp;
                }
                if(0==b){
                        return a;
                }
                return xymod(a-b,b);
        }

在算法的效率上第二种和第三种都有个自的局限性，一个在大整数上，一个在迭代上，我们还可以找到一个综合上面两种的算法就是，一步步的简化a,b这两个数，简化的方法由下：

(1)如果y=k*y1,x=k*x1.那么有f(x,y)=k*f(x1,y1)
(2)如果x=p*x2,p为素数，并且y%p != 0，那么f(x,y) = f(p*x2,y) = f(x2,y)
于是我们得到下面的解决方法：
将p = 2,
若x，y均为偶数，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1);
若x是偶数，y是奇数，f(x,y) = f(x/2,y) = f(x>>1,y);
若x是奇数，y是欧式，f(x,y) = f(x,y/2) = f(x,y>>1);
若x和y均为奇数，f(x,y) = f(y,x-y)。这时x-y一定是偶数，下一步一定会除以2。
上面的方法来源都可以用到上面的证明过程，
代码实现由下：
public static int moveCombe(int a,int b){
                if(a<b){
                        return moveCombe(b, a);
                }
                if(0==b){
                        return a;
                }
                if(isTwo(a)){
                        if(isTwo(b)){
                                return moveCombe(a/2, b/2)*2;
                        }
                        return moveCombe(a/2, b);
                }else{
                        if(isTwo(b)){
                                return moveCombe(a, b/2);
                        }
                        return moveCombe(b, a-b);
                }


        }
        private static boolean isTwo(int a) {
                if(0==a%2){
                        return true;
                }else{
                        return false;
                }
        }

上面的代码都比较简单，我就没有做注解了，这些思想大部分都来自了网络，代码自己重写过，有不对之处还请大家指出，共同学习。

热点排行

编程

java 算法基础之一找寻最大公约数