「每日算法」什么是辗转相除法(辗转相除法是什么-)

点击上方\”java全栈技术\”关注,每天学习一个java知识点

大四毕业前夕,计算机学院的小灰又一次顶着炎炎烈日,

去某IT公司面试研发工程师岗位……

「每日算法」什么是辗转相除法(辗转相除法是什么-)

半小时后,公司会议室,面试开始……

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

小灰奋笔疾书,五分钟后……

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

小灰的思路十分简单。他使用暴力枚举的方法,试图寻找到一个合适的整数 i,看看这个整数能否被两个整型参数numberA和numberB同时整除。

这个整数 i 从2开始循环累加,一直累加到numberA和numberB中较小参数的一半为止。循环结束后,上一次寻找到的能够被两数整除的最大 i 值,就是两数的最大公约数。

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

事后,垂头丧气的小灰去请教同系的学霸大黄……

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

辗转相除法, 又名欧几里得算法(Euclidean algorithm),目的是求出两个正整数的最大公约数。它是已知最古老的算法, 其可追溯至公元前300年前。

这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。

「每日算法」什么是辗转相除法(辗转相除法是什么-)

有了这条定理,求出最大公约数就简单了。我们可以使用递归的方法来把问题逐步简化。

首先,我们先计算出a除以b的余数c,把问题转化成求出b和c的最大公约数;然后计算出b除以c的余数d,把问题转化成求出c和d的最大公约数;再然后计算出c除以d的余数e,把问题转化成求出d和e的最大公约数……

以此类推,逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算,直到两个数可以整除,或者其中一个数减小到1为止。

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

五分钟后,小灰改好了代码……

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

更相减损术, 出自于中国古代的《九章算术》,也是一种求最大公约数的算法。

他的原理更加简单:两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25,25减去10的差是15,那么10和25的最大公约数,等同于10和15的最大公约数。

「每日算法」什么是辗转相除法(辗转相除法是什么-)

由此,我们同样可以通过递归来简化问题。首先,我们先计算出a和b的差值c(假设a>b),把问题转化成求出b和c的最大公约数;然后计算出c和b的差值d(假设c>b),把问题转化成求出b和d的最大公约数;再然后计算出b和d的差值e(假设b>d),把问题转化成求出d和e的最大公约数……

以此类推,逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算,直到两个数可以相等为止,最大公约数就是最终相等的两个数。

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

五分钟后,小灰重写了代码……

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

众所周知,移位运算的性能非常快。对于给定的正整数a和b,不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数:

当a和b均为偶数,gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)

当a为偶数,b为奇数,gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)

当a为奇数,b为偶数,gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)

当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b), 此时a-b必然是偶数,又可以继续进行移位运算。

比如计算10和25的最大公约数的步骤如下:

  1. 整数10通过移位,可以转换成求5和25的最大公约数
  2. 利用更相减损法,计算出25-5=20,转换成求5和20的最大公约数
  3. 整数20通过移位,可以转换成求5和10的最大公约数
  4. 整数10通过移位,可以转换成求5和5的最大公约数
  5. 利用更相减损法,因为两数相等,所以最大公约数是5

在两数比较小的时候,暂时看不出计算次数的优势,当两数越大,计算次数的节省就越明显。

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

最后总结一下上述所有解法的时间复杂度:

1.暴力枚举法:时间复杂度是O(min(a, b)))

2.辗转相除法:时间复杂度不太好计算,可以近似为O(log(max(a, b))),但是取模运算性能较差。

3.更相减损术:避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a, b)))

4.更相减损术与移位结合:不但避免了取模运算,而且算法性能稳定,时间复杂度为O(log(max(a, b)))

「每日算法」什么是辗转相除法(辗转相除法是什么-)「每日算法」什么是辗转相除法(辗转相除法是什么-)

本文原本只写到辗转相除法就终告结束,后来网友们指出还有更优化的解法,看来自己还是才疏学浅,很感谢大家指出问题。另外,方法的参数默认必定是正整数,所以在代码中省去了合法性检查。

文中描述的更相减损术是简化了的方式。在九章算术原文中多了一步验证:如果两数都是偶数,计算差值之前会首先让两个数都折半,使得计算次数更少。这种方法做到了部分优化,但古人似乎没想到一奇一偶的情况也是可以优化的。

由于篇幅所限,本文省略了关于辗转相除法原和更相减损术的原理及证明。其实证明过程并不复杂,细心的同学们也可以自己尝试研究一下。谢谢大家

本文摘自程序员小灰

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至89291810@qq.com举报,一经查实,本站将立刻删除。
赞 (0)
上一篇 2024年4月18日 上午11:54
下一篇 2024年4月18日 下午12:00

相关推荐

  • 徐州小学排名2025最新排名最好的小学

    徐州小学排名2025最新排名最好的小学 随着教育的不断发展,徐州地区的小学排名也不断变化。在2025年最新的小学排名中,徐州某小学排名徐州第一。 该小学的师资力量非常强大,教师阵容…

    教育百科 2025年1月20日
  • 怎样和抑郁症患者相处

    和抑郁症患者相处 抑郁症是一种常见的心理疾病,它可能会影响患者的情绪,思维,和行为。与抑郁症患者相处需要耐心,理解和关爱。以下是一些和抑郁症患者相处的建议。 1. 给予患者支持和理…

    教育百科 2025年11月2日
  • 抑郁厌学孩子当兵可以么

    抑郁厌学孩子当兵可以么 作为一名军人,需要具备坚强的意志,勇敢的性格和坚定的信仰。而对于那些患有抑郁厌学的孩子来说,成为一名军人可能是他们寻求救赎和改变的最佳途径之一。 抑郁厌学的…

    教育百科 2025年10月1日
  • 杭州初中生厌学咋办啊

    杭州初中生厌学怎么办? 作为杭州初中生的家长,您是否曾经遇到过孩子厌学的情况?有时候,孩子可能会因为学习压力、成绩下降、同学关系等问题而表现出厌学情绪。在这种情况下,家长应该如何帮…

    教育百科 2025年3月25日
  • 本科生休学保研吗

    本科生休学保研吗 近年来,保研成为许多本科生的目标。然而,保研的过程并不容易,需要学生具备多方面的能力和条件。其中,休学保研是一种特殊的情况,需要学生具备一定的勇气和决心。本文将探…

    教育百科 2024年8月3日
  • 华中师范大学2025年公费师范生录取分数线

    华中师范大学2025年公费师范生录取分数线是多少? 随着教育越来越受到人们的关注,各大高校也不断推出新的教育计划,其中,华中师范大学的公费师范生计划备受欢迎。那么,2025年华中师…

    教育百科 2024年11月21日
  • 杏子不上学

    杏子不上学 杏子是个小女孩,她非常喜欢上学,每天都会按时起床,然后去学校。但是有一天,当她来到学校时,却发现她不再喜欢上学了。 杏子发现,学校的生活并不像她想象中那样有趣。同学们都…

    教育百科 2026年4月15日
  • 初中抑郁可以休学吗

    初中抑郁可以休学吗 在初中阶段,学生们正处于人生的关键时期。然而,由于压力、焦虑、孤独和其他因素,一些人可能会患上抑郁症。如果学生正在经历抑郁症状,那么休学可能是一个有益的选择。在…

    教育百科 2024年7月23日
  • 抑郁症眼红

    抑郁症眼红 抑郁症是一种常见的心理疾病,它让人感到孤独,无助和绝望。对于患有抑郁症的人来说,他们看着周围的世界似乎充满了无尽的黑暗,他们感到整个世界都抛弃他们了。抑郁症眼红,这是抑…

    教育百科 2025年11月5日
  • 温州初中生厌学的对策

    温州初中生厌学的对策 在当今社会中,学习已经成为了每个人必须经历的过程。然而,对于温州初中生来说,学习可能已经成为了他们最不愿意面对的事情。这是因为在温州这个竞争激烈的城市,初中生…

    教育百科 2026年2月10日

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注