现在的位置: 首页 > 综合 > 正文

最大公约数问题

2018年10月01日 ⁄ 综合 ⁄ 共 1314字 ⁄ 字号 评论关闭

写一个程序,求两个正整数的最大公约数。如果两个正整数都很大,有什么简单的算法吗?
      例如,给定两个数1 100 100 210 001,, 120 200 021,求出其最大公约数。
解法一:辗转相除法
      假设用f(x,y)表示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),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另一个数就是两者最大的公约数。
函数如下:

 int gcd(int x,int y)
 {
     return (!y)? x:gcd(y,x%y);
}

解法二:
如果一个数能够同时整除x和y,则必能同时整除x-y和y;而能够同时整除x-y和y的数也比能同时整除x和y,即x和y的公约数与x-y和y的公约数是相同的,其最大公约数也是相同的,即f(x,y)= f(x-y,y),那么就可以不再需要进行大整数的取模运算,而转换成简单得多的大整数的减法。
在实际操作中,如果x<y,可以先交换(x,y)因为(x,y)=(y,x),从而避免求一个正数和一个负数的最大公约数情况的出现。一直迭代下去,直到其中一个数为0。
函数如下:

BigInt gcd(BigInt x, BigInt y) 
{ 
    if(x < y) 
       return gcd(y, x); 
    if(y == 0) 
       return x;
    else 
       return gcd(x-y, y);
}

解法三:结合解法一和解法二
从分析公约数的特点入手。对于y和x来说,如果y=k*y1,x=k*x1。那么有f(y , x) = k*f(y1 , x1)。另外,如果x = p*x1,假设p是素数,并且y%p!=0(即y不能被p整除),那么f(x, y) = f(p*x1,y) = f(x1 , 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),那么在f(x , y) = f(y , x-y)之后,(x-y)是一个偶数,下一步一定会有除以2的操作。
因此,最坏情况下的时间复杂度是O(log2(max( x, y)))。
函数如下:

 bool IsEven(BigInt m) 
  {
      if(m % 2 == 0) 
         return true; 
      else 
         return false; 
  }
  BigInt gcd(BigInt x, BigInt y) 
  { 
     if(x < y) 
         return gcd(y, x); 
     if(y == 0) 
         return x; 
     else 
     { 
        if(IsEven( x )) 
        { 
           if(IsEven( y )) 
               return (gcd(x >> 1, y >> 1) << 1); // 2*gcd(x>>1, y>>1) 
           else 
               return gcd(x >> 1, y); 
        } 
        else 
        { 
           if(IsEven( y )) 
               return gcd(x, y >> 1); 
           else return gcd(y, x - y); 
        } 
     } 
 }

抱歉!评论已关闭.