js实现辗转相除法求最大公约数

昨晚刷抖音，跳出的第一条是李永乐老师（清华大学2009届毕业生，现就职于北京人大附中）讲诉他为什么要当中学老师的视频，看完后被他圈粉了，就进入主页一直刷他的其他作品，其中一条就是《轻松Get辗转相除法求最大公约数》，哇！有意思，打开电脑，试试用js能不能写出这个算法。

先来复习一下什么是辗转相除法：

假设求104和40的最大公约数，我们知道，除法有被除数、除数、商、余数。所以，该题被除数为104，除数为40，进行一次除法运算后，商为2，余数为24。辗转相除法规定，当余数不为0时（即不能整除），就应该把上一次的除数作为下一次的被除数、上一次的余数作为下一次的除数再次进行除法运算，接着看余数是否为0。不为0，继续此方法做除运算；为0，此时的除数就是二者的最大公约数。理论很骨感，例子才丰满：

友情提示，如果你想自己动手看看能不能用js写出这个算法，请不要继续往下翻，拿出纸笔开始构思吧！如果你是通过电脑浏览这篇文章的，你可以在这个页面上点击鼠标右键，选择检查（或审查元素）以调出调试工具，在console标签下开始写你的js代码

1、使用递归

/*
 *@method gcd
 *@param { Number } a
 *@param { Number } b
 *@return { Number } a和b的最大公约数
*/
function gcd(a, b) {
  if (a < b) {
    // 利用es6数组解构方法巧妙地置换a和b的值，目的使a大于b
    [a, b] = [b, a]
  }
  if (b === 0) {
    return a
  }
  if (a % b !== 0) {
    return gcd(b, a % b)
  } else {
    return b
  }
}

// 调用
gcd(104, 40) // 8
gcd(40, 104) // 8
gcd(40, 0) // 40

2、使用循环

/*
 *@method gcd
 *@param { Number } a
 *@param { Number } b
 *@return { Number } a和b的最大公约数
*/
function gcd(a, b) {
  if (a < b) {
    [a, b] = [b, a]
  }
  while (b !== 0) {
    let remainder = a % b
    a = b
    b = remainder
  }
  return a
}

// 调用
gcd(104, 40) // 8
gcd(40, 104) // 8
gcd(40, 0) // 40

网上还有一种叫做更相减损的方法，即始终拿大的减小的，所得差给原本大的一方，如此循环往复，直到两者相等，那么相等的这个数字就是最大公约数了，详见：

function gcd (a, b) {
  if (a === b) {
    return b
  }
  if (a > b) {
    a -= b
  } else {
    b -= a
  }
  return gcd(a, b)
}

// 调用
gcd(104, 40) // 8

总结：以上两种方法中，辗转相除法的效率较高。

最后编辑于：2020.02.24 13:59:42