A-A+

最大公约数 ACM

2012年08月11日 知识 暂无评论 阅读 143 次

两个数的最大公约数

--来源于百度空间

最大公约数最经典的算法欧几里得,下面对欧几里得算法进行基本证明,假设用f(x,y)表示x y的最大公约数,取k=x/y,b=x%y,则x=ky+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);

}

解法2

在解法1中用到了取模运算,取模在计算机中是非常昂贵的开销,那我们能不能不取模呢?

采用与欧几里得相应的分析,如果一个数能够同时整除x和y,则必能够同时整除x-y,和y,而能够同时整除x-y和y的数,也必能够同时整除x和y,即x和y的最大公约数与x-y和y的最大公约数相同,即f(x,y)=f(x-y,y)

int gcd(int x,int y)

{

if(x<y)

return gcd(y,x);

if(y==0)//不要忘了这儿的判断

return x;

else

return gcd(x-y,y);

}

解法3

解法2同样具有缺陷,如果遇到(100000000,1),就很尴尬了!

我们知道2是一个素数,同时对于二进制的大整数而言,可以很容易的除以2和乘以2的运算转换成移位运算,从而避免解法一的大整数除法,和解法二的多次迭代

原理:1、f(x,y)=k*f(x1,y1);2、如果x=p*x1,假设p是素数,并且y%p!=0,那么f(x,y)=f(p*x1,y)=f(x1,y)。

由此可得到算法为:不断的对x和y做除2操作,直至两者均不能被2整除,采用辗转相减法,获得一个可被2整除的数,继续做除2操作,循环,直至两数之一为0。详细描述如下:

若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)

代码

int gcd(int a,int b)
{
if(a==b) return a;
if((a&1)==0)
{
if((b&1)==0)
return gcd(a>>1,b>>1)<<1;
else
return gcd(a>>1,b);
}
else
{
if((b&1)==0)
return gcd(a,b>>1);
else
return gcd(((a>b)?(a-b):(b-a))>>1,(a+b)>>1);
}
}

标签:

给我留言

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录