編程之美：最大公約數問題

/*
最大公約數
*/
#include 

/*
方法1：輾轉相除
缺點：對於大整數，取模運算開銷大
*/
int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}

/*
方法2：
缺點：迭代次數過多
*/
int gcd2(int x,int y){
	if(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>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;  
}