JavaScript实现辗转相除法
下面是JavaScript实现欧几里得算法(也称辗转相除法)求最大公约数的代码:
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
其中gcd(a, b)
函数接受两个参数,返回它们的最大公约数。如果b
等于0,那么最大公约数就是a
;否则,递归调用gcd(b, a % b)
,直到b
为0为止,此时的余数就是最大公约数。
例如,求18
和24
的最大公约数,我们可以调用gcd(18, 24)
,具体过程如下:
gcd(18, 24)
= gcd(24, 18 % 24)
= gcd(24, 18)
= gcd(18, 24 % 18)
= gcd(18, 6)
= gcd(6, 18 % 6)
= gcd(6, 0)
= 6
因此,18
和24
的最大公约数是6
。
该博文为原创文章,未经博主同意不得转。本文章博客地址:https://cplusplus.blog.csdn.net/article/details/134025202