1. 编程圈首页
  2. 文库
  3. 后端开发

漫画算法笔记之求两个数最大公约数

题目

求两个整数的最大公约数

辗转相除法

定义

辗转相除法,又名欧几里得算法(Euclideanalgorithm),该算法的目的是求出两个正整数的最大公约数。它是已知最古老的算法,其产生时间可追溯至公元前300年前。这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

实现

漫画算法笔记之求两个数最大公约数

缺点

不过有一个问题,当两个整数较大时,做a%b取模运算的性能会比较差。

更相减损术

定义

更相减损术,出自中国古代的《九章算术》,也是一种求最大公约数的算法。古希腊人很聪明,可是我们炎黄子孙也不差。它的原理更加简单:两个正整数a和b(a>b),它们的最大公约数等于ab的差值c和较小数b的最大公约数。例如10和25,25减10的差是15,那么10和25的最大公约数,等同于10和15的最大公约数。

实现

漫画算法笔记之求两个数最大公约数

缺点

但是,更相减损术依靠两数求差的方式来递归,运算次数肯定远大于辗转相除法的取模方式。同时,更相减损术是不稳定的算法,当两数相差悬殊时,如计算 10000 和 1 的最大公约数,就要递归 9999 次。

结合更相减损术和辗转相除法

定义

众所周知,移位运算的性能非常好。对于给出的正整数a和b,不难得到如下的结论。(从下文开始,获得最大公约数的方法getGreatestCommonDivisor被简写为gcd。)

  • 当a和b均为偶数时,gcd(a,b)=2×gcd(a/2,b/2)=2×gcd(a>>1,b>>1)
  • 当a为偶数,b为奇数时,gcd(a,b)=gcd(a/2,b)=gcd(a>>1,b)
  • 当a为奇数,b为偶数时,gcd(a,b)=gcd(a,b/2)=gcd(a,b>>1)
  • 当a和b均为奇数时,先利用更相减损术运算一次,gcd(a,b)=gcd(b,a-b),此时ab必然是偶数,然后又可以继续进行移位运算

实现

漫画算法笔记之求两个数最大公约数

发布者:编程圈,转转请注明出处:https://www.bianchengquan.com/article/68021.html

发表评论

登录后才能评论