算法——欧几里得算法

欧几里得算法

欧几里得算法是用来求两个正整数最大公约数的算法。
古希腊数学家欧几里得在其著作中《The Elements》中最早描述了这种算法,所以叫欧几里得算法。

a*x + b*y = gcd(a, b);
存在唯一的x, y使得上面等式成立。

算法原理

欧几里得算法主要就需要一个叫GCD递归定理的支撑。

gcd(a,b) = gcd(b,a mod b);

gcd在这里指最大公约数,意思就是a与b的最大公约数与b与a mod b的最大公约数相同。

下面我们就来证明一下这个定理:

|在这里的意思是就是整除

欧几里得算法的代码表示

int Gcd(int a, int b)
{
   
	if(b == 0)
		return a;
	else
		return Gcd(b, a % b);
}

用30和21这个例子来证明一下代码的正确性:

Gcd(30, 21);-->
Gcd(21, 9);-->
Gcd(9, 3);-->
Gcd(3, 0);-->
Gcd = 3;

参考文献

[1]算法导论(第三版)
全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务