欧几里德算法- JavaScript

Euclid's Algorithm - JavaScript

本文关键字：JavaScript 算法 欧几里德      更新时间：2023-09-26

我是JavaScript的新手，我正在学习递归函数。具体来说，我正在研究欧几里得算法。除了第2行的基本情况"if (!B){返回a;}。我知道在某一点a % b将等于NaN这是递归调用应该停止的时候。但是"如果"有什么用呢?B)"意思是最简单的形式?"这事让我无法接受。提前感谢您的反馈!

// Euclid's Algorithm 
var gcd = function(a, b) {  
   if (!b) {  
       return a;  
   }  
   return gcd(b, a % b);  
};  
console.log(gcd(462, 910));

这就是欧几里得算法的基本原理。

gcd(a, b) = gcd(b, a%b)

但b为0时除外。这个案子的结果是什么?你可以想象0实际上有无限个因数:你可以用0除以任何数，余数总是0。

由此，我们可以推出

gcd(a, 0) = a

这是算法的终止情况。

if (!b)实际检查是否为b===0，在本例中返回a。

(!B)正在对变量B求值以返回false值。在JavaScript中NaN是假的，这意味着它不是假的，但它会在布尔值中计算为假。

正如其他人提到的，变量b将等于0而不是NaN。我只是在解释NaN是如何计算的

欧几里得算法的基本情况发生在其中一个参数等于零时，这意味着两个数的最大公约数是非零数。你可以参考这个链接看一些例子:https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

这是我如何实现欧几里得算法:

   function gcd(a, b) {
        // base cases
        if(a === 0) { return b;}
        if(b === 0) { return a;}
        // decrease and conqure - recursion
        return gcd(b, a % b);
    }
    console.log(gcd(9, 6));
    console.log(gcd(6, 9));

简单地说，在这种情况下，!b与b == 0相同。0作为真值为假，因此!0将为真。

换句话说，当b为零时，函数返回a，否则继续进行更多递归层。

你认为a % b将变成NaN的论点实际上是错误的- b变成零的事实，并且你检测到，这意味着你从来没有真正将任何东西除以零得到NaN。

//I'm glad that I can help others, here is my version:
//Euclid's algorithm:
//1)Find reminder of division m by n
//2)If remainder is zero, n is a solution
//3)Reduce(if r != zero)
const euclid = function(num1, num2){
    //compute the remainder:
    var remainder = num1 % num2;
    if(remainder == 0){
        return num2;
   
    }else{
        //step 3:
        num1 = num2;
        num2 = remainder;
       return euclid(num1, num2);
    }
}
//test the result:
console.log(euclid(80, 30));
相关文章：