昨晚刷抖音,跳出的第一条是李永乐老师(清华大学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

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

0
分类: js
浏览:1,339

0 条评论

发表评论

电子邮件地址不会被公开。

你必须允许浏览器启用JavaScript才能看到验证码

Scroll Up