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

/*
最大公约数
*/
#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; }