求解最大公约数和最小公倍数问题

开发技术作者： 2024-06-17 01:40:02

思路：最大公约数问题也是一个非常典型的递归算法的应用。每次递归使得原来求两个大数之间的公约数转变成求两个稍微小点的数之间的公约数，要求转换的过程要保证不会改变公约数的。这就要看其中转换的原理了。原理从《几何原本》中得出--辗转相除。假设f(x, y) 表示x,y的最大公约数是g，而k = x/y,b

思路：

最大公约数问题也是1个非常典型的递归算法的利用。每次递归使得原来求两个大数之间的公约数转变成求两个略微小点的数之间的公约数，要求转换的进程要保证不会改变公约数的值。这就要看其中转换的原理了。

原理从《几何本来》中得出--展转相除。假定f(x,y) 表示x,y的最大公约数是g，而k = x/y,b= x%y，则g必能整出b。由于x = ky + b，b = x - ky，b/g = (x-ky)/g1定为整数，所以必有g整除b。

以下所示：

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

代码以下：

[html] view
 plaincopy

int gcd(int x , int y)  

{  

   return (y == 0 )?x :gcd(y , x % y) ;   

}

非递归代码：

int gcd(int x,int y) { int temp; while(y!=0) { temp=x; x=y; y=temp%y; } return x; }

书中还引申出展转相减法，原理跟上面所述差不多。

[html] view plaincopy

if(x < y)

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

int gcd(int n,int m) { if(n==0) return m; while (m!= 0) { if (n > m) n = n - m; else m = m - n; } return n; }

或：

int GetMaxCommonDivide_new(int n,int m) { if(n<m) { n^=m; m^=n; n^=m; //n=n+m; //m=n-m; //n=n-m; } while (m!= 0) { if (n > m) n = n - m; else m = m - n; } return n; }

最后书中提到1种相除和相减相结合的方法，保证了不做过量冗余的步骤。这就是把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,51); font-family:Arial; font-size:14px; line-height:26px"> 若x，y均为奇数，f(x,y) =f(y,x-y)

此解法结合了上述两种方法：第1种方法递归次数相当少但每次取模挺耗时（到底耗时情况如何，我没有具体了解过，但肯定比加减法耗时些），而第2种递归可能会相当多，但每次运算都是减法运算，很快。综合二者，用2为基数，可以保证递归次数不那末多，同时运算也快。

代码以下：

[cpp] view
 plaincopy

int gcd(int x , int y)

if(x < y)
return gcd(y , x) ;
if(y == 0)
return x ;
if(isEven(x)) //x为奇
{
if(isEven(y)) //y为奇
return gcd(x - y, y) ;
else //y为偶
return gcd(x , y >>1) ;
}
//x为偶
{
//y为奇数
return gcd(x >> 1, y) ;
//y为偶
return 2 * gcd(x >> 1, y >> 1) ;
}
}

求解最小公倍数：

从题面上看，好像我们需要求解的是两个题目，但其实就是1个题目。那就是求最大公约数？为何呢？我们可以假想这两个数m和n，假定m和n的最大公约数是a。那末我们可以这样写：

m = b *a；

n = c * a;

所以m和n的最小公倍数就应当是a*b*c啊，那不就是m * n / a，其中m和n是已知的，而a就是那个需要求解的最大公约数。所以就有了下面的代码，

[cpp] view
 plaincopy

int GetMinCommonMultiple(int m,87); background-color:inherit; font-weight:bold">int n)  
    assert(m && n);  

    return m * n / gcd(m, n);  

}