首页 > 其他 > 详细

编程之美:最大公约数问题

时间:2014-03-15 00:47:17      阅读:597      评论:0      收藏:0      [点我收藏+]


/*
最大公约数
*/
#include <stdio.h>

/*
方法1:辗转相除
缺点:对于大整数,取模运算开销大
*/
int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}

/*
方法2:
缺点:迭代次数过多
*/
int gcd2(int x,int y){
	if(x<y)
		return gcd2(y,x);
	return y==0?x:gcd2(x-y,y);
}
/*
方法3:
1、如果y=k*y1,x=k*x1,那么有f(y,x)=k*f(y1,x1)
2、如果x=p*x1,且y%p!=0,假设p为素数,那么有f(x,y)=f(p*x1,y)=f(x1,y)

取p=2
若x,y为偶数,f(x,y)=2*f(x>>1,y>>1)
若x为偶数,y为奇数,f(x,y)=f(x>>1,y)
若x为奇数,y为偶数,f(x,y)=f(x,y>>1)
若x,y均为奇数,f(x,y)=f(x,x-y)
*/
int gcd3(int x,int y){
	if(x<y)
		return gcd(y,x);
	if(y==0)
		return x;
	else{
		if(!(x&1)){
			if(!(y&1))
				return gcd3(x>>1,y>>1)<<1;
			return gcd3(x>>1,y);
		}
		else{
			if(!(y&1))
				return gcd3(x,y>>1);
			return gcd(y,x-y);
		}
	}
}
int main(){  
	int a=12,b=8;

	printf("%d\n%d\n%d\n",gcd(a,b),gcd2(a,b),gcd3(a,b));
	
    return 0;  
}  


编程之美:最大公约数问题,布布扣,bubuko.com

编程之美:最大公约数问题

原文:http://blog.csdn.net/starcuan/article/details/21252757

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!