求一个数的最大公约数的三种思路——解题笔记

朴灿烈づ我的快乐病毒、 2022-08-06 15:03 93阅读 0赞

**求一个数的最大公约数的三种思路——解题笔记**

编程之美上的题目：求一个数的最大公约数。

这道题目有三种解题思路，总结如下：

# 思路一： #

直接使用辗转相除法，这个不多介绍，代码如下：

// 直接辗转相除法
    int gcd1(int a, int b)
    {
    	for(int m = a%b; m != 0; m = a%b)
    	{
    		a = b; 
    		b = m; 
    	}
    	return b; 
    }

分析：辗转相除法需要用到数值之间的取余运算，这是非常耗时间的。

# 思路二： #

改进辗转相除法中取余（除法）运算，改为减法。这里可以利用一个规律，x和y的最大公约数等于x-y和y的最大公约数。不过需要判断x和y的大小。

代码如下：

// x和y的最大公约数等于x-y和y的最大公约数
    int gcd2(int a, int b)
    {
    	if(a < b)
    		swap(a, b);  // 默认前面的数较大
    	while(b)
    		return gcd2(b, a-b);  // 递归
    	return a; 
    }

分析：虽然这种方法只有减运算，用的是递归的实现形式。但是，需要递归的次数比较多，假如a和b之间相差较大，那么每次都只是相减，会迭代很多次。

# 思路三： #

可以结合前面两个思路的优点，我们不全都是用减运算，偶尔用一次除法，不过只是除以2，即判断奇偶数，而且用移位运算实现。

![Center][]

代码如下：

// 通过判断奇偶数，减少迭代次数
    bool isEven(int a) 
    {
    	return !(a & 1);  // 按位与来判断奇偶数
    }
    
    int gcd3(int a, int b)
    {
    	if(a < b)
    		swap(a, b);  // 默认前面的数较大
    
    	if(!b)
    		return a; 
    
    	if(isEven(a))  // if a is even
    	{
    		if(isEven(b))  // b is even at the same time
    			return (gcd3(a>>1, b>>1) <<1); // note that *2
    		else
    			return (gcd3(a>>1, b));  // if only a is even
    	}
    	else
    	{
    		if(isEven(b))
    			return gcd3(a, b>>1); // is only b is even 
    		else 
    			return gcd3(a-b, b);  // neither a or nor b is even 
    	}
    }

分析：时间复杂度只是a和b中较大数的二进制位数，也就是O(log max(a, b))。注意其中判断是否为奇偶数用的是位运算。

[Center]: /images/20220806/286076968fb04ebface0e786ef97932d.png