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 总结：以上两种方法中，辗转相除法的效率较高。

本文章由javascript技术分享原创和收集