2.7 最大公约数问题

1,方法一:
最经典的辗转相除法.

int gcd(int x, int y)
{
	return (!y)? x:gcd(y, x % y);
}

缺点:取模运算开销较大,容易成为瓶颈.

2,方法二:

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,方法三:
有效利用x,y的奇偶性.

若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(y, x-y);

int gcd(int x, int y)
{
	if (x < y)
		return gcd(y, x);
	if (y == 0)
		return x;
	else
	{
		if (isEven(x))
		{
			if (isEven(y))
				return gcd(x >> 1, y >> 1) << 1;
			else
				return gcd(x >> 1, y);
		}
		else
		{
			if (isEven(y))
				return gcd(x, y >> 1);
			else
				return gcd(y, x - y);
		}
	}
}