求最大公约数之四部曲

解法一：

欧几里得算法 ( 又称辗转相除法 ) ：

        题：给定两个正整数 m 和 n ，求它们的最大公约子（即能得到同时整除 m 和 n 的最大正整数）

        解：

          E1.[ 求余数 ] 以 n 除 m 并令 r 为所得余数。（我们将有 0<<r<n ）

          E2.[ 余数为 0 ？ ] 若 r=0 ，算法结束， n 即为答案

          E3.[ 减少 ] 置 m<-n ， n<-r ，并返回步骤 E1 。

 

算法示意图：

  

public int commonValue(int max,int min){

        if(max<0|| min<0){

           System.out.println("输入的两个参数必须为正整数。");

           return -1;

       }

       if(max<min){

            int temp = min;

            min = max;

            max = temp;

       }

       int remainder = max%min;

       while(remainder!=0){

           max = min;

           min = remainder;

           remainder = max%min;

       }
       return min;

    }
 

 

 

引申题：

   求两个线段长度的“最大公共量度”   ，其中心思想就是求最大公约数

 

 

解法二：

解法一中，用到了取模运算。但对于大整数而言，取模运算（其中用到除法）是非常昂贵的开销，有没有办法能够不用取模运算呢？

  分析：如果一个数能够同时整除 x 和 y(x > y) ，则必能同时整除 x-y 和 y; 即 x 和 y 的公约数与 x-y 和 y 的公约数是相同的，其最大公约数也是相同的，即 f(x,y)=f(x-y,y) ，那么就可以不再需要进行大整数的取模运算，而转换成简单得多的大整数的减法。

示例：

  f(42,30)=f(30,12)=f(18,12)=f(12,6)=f(6,6)=f(6,0) = 6

 

public int cv(int max,int min){

        if(max<min)

            return cv(min,max);

        if(min == 0)

            return max; 

        else

            return cv(max-min,min);

    }

 

   优点： 用减法代替除法，可以提高算法的效率。

   缺点： 如果遇到 f(10 000 000 000 000,1) 这类情况（即两数值相差很大），本算法就不如算法一效率高。

 

 

解法三：

更相减损术： 是出自《九章算术》的一种求 最大公约数 的 算法 ，它原本是为 约分 而设计的，但它适用于任何需要求最大公约数的场合。

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2 约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

　　则第一步中约掉的若干个2 与第二步中等数的乘积就是所求的最大公约数。

该算法的思想是用 2 约简，该算法相比算法二效率有所提高， 那能不能进一步改进算法，想一想该算法只是在两个整数都为偶数的时候用 2 约简，当一个为偶数，一个有奇数时能约简吗？

 

 

private int count = 0;   //计数器，标记用2约简的次数
public int cv2(int max,int min){
		 if(max<min)
			 return cv2(min,max);
		 if(isEven(max)&&isEven(min)){
			 count++;
			 return cv2(max>>1,min>>1);
		 }
		 if(min == max-min){
			 while(count-->0){
			    min = min<<1;
			 }
			 return min;
		 }
		 else
			 return cv2(max-min,min);
	}
	//函数--判断是否是偶数
	public boolean isEven(int i){
		if((i&1) == 0)
			return true;
		return false;
	}

 

解法四：

对于 y 和 x 来说，如果 y = k*y, x = k*x₁ 。那么有 f(y,x)=k*f(y₁ ,x₁ ) 。另外，如果 x = p*x₁ , 假设 p 是素数，并且 y%p!=0( 即 y 不能被 p 整除 ) ，那么 f(x,y)=f(p*x_1, y)=f(x_1, y) 。

同样的为了便于提高运算效率，采用 2 这个素数（乘除运算便于转化成位移运算）。

取 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(y,x-y) ，

那么在 f(x,y)=f(y,x-y) 之后， (x-y) 是一个偶数，下一步定会有除以 2 的操作（即两奇数相减得偶数）。

最坏情况下的时间复杂度是 O(log₂ (max(x,y))) 。

 

f(42,30)=f(42/2,30/2)

          =2 * f(21,15)

          =2 * f(15,21-15)

          =2 * f(15,6)

          =2 * f(15,6/2)

          =2 * f(15,3)

          =2 * f(15-3,3)

          =2 * f(12,3)

          =2 * f(12/2,3)

          =2 * f(6,3)

          =2 * f(6/2,3)

          =2 * f(3,3)

          =2 * f(3,0)

          =2*3

          =6

 

public int cv(int max,int min){

        if(max<min)

            return cv(min,max);

        if(min==0){

            return max;

        }else{

            if(isEven(max)){

               if(isEven(min))

                   return (cv(max>>1,min>>1)<<1);

               else

                   return cv(max>>1,min);

            }else{

               if(isEven(min))

                   return cv(max,min>>1);

               else

                   return cv(min,max-min);

            }

        }

        

    }//函数--判断是否是偶数

public boolean isEven(int i){

if((i&1) == 0)

return true;

return false;

}

 

 

 

评论

1 楼 saieuler 2012-09-18  

以前看过，再标记一下