欧几里德算法(求最大公约数)

欧几里德算法也就是辗转相除法,有着2000年的历史了。欧几里德算法依据的算法理论是一个定理:gcd(a,b) = gcd(b,a mod b)。
实现源码为:

//递归实现
int gcd(int m, int n)
{
	if (m < n)
	{
		int tem = m;
		m = n;
		n = tem;
	}
	if (n == 0)
		return m;
	else
		return gcd(m, m%n);
}

//非递归实现
int gcd(int m, int n)
{
	if (m < n)
	{
		int tmp = m;
		m = n;
		n = tmp;
	}
	if (n == 0)
		return m;
	while (n > 0)
	{
		int tmp = m % n;
		m = n;
		n = tmp;
	}
	return m;
}

0 条评论
发表一条评论