javascript使用toString方法判断对象类型
浏览数：31 /
时间：2015年06月09日
求两个正整数的最大公约数
方法1、辗转相除法
int gcd(int a,int b)
{
if(a<b)
{
return gcd(b, a);
}
if(b==0)
{
return a;
}
return gcd(b, a%b);
}
缺点;
如果该整数是大整数，那么需要频繁地去做取余运算
方法2. 用减法
gcd(x,y)=gcd(x-y,y);
int gcd(int a,int b)
{
if(b==0)
{
return a;
}
if(a<b)
{
return gcd(b, a);
}
return gcd(a-b, b);
}
缺点：迭代次数太多，如果是f(1111111,1);就会去做很多次减法
解法3.
综合了移位运算和减法，避开了除法运算，提高了效率
int isEven(int i)
{
return !(i&0x01);
}
int gcd(int a,int b)
{
if(b==0)
{
return a;
}
if(a<b)
{
return gcd(b, a);
}
if (isEven(a))
{
if(isEven(b))
{
return gcd(a>>1,b>>1)<<1;
}else
{
return gcd(a>>1,b);
}
}else
{
if (isEven(b))
{
return gcd(a, b>>1);
}else
{
return gcd(a-b, b);
}
}
}
int main(int argc, const char * argv[])
{
int a=15;
int b=20;
cout<<gcd(a,b)<<endl;
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
