算法——欧几里得算法

欧几里得算法

欧几里得算法是用来求两个正整数最大公约数的算法。
古希腊数学家欧几里得在其著作中《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]算法导论(第三版)
全部评论

相关推荐

07-25 10:31
门头沟学院 Java
求问各位大佬,笔试都考点啥
投递科大讯飞等公司10个岗位
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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