Наименьшее общее кратное значений массива с использованием алгоритма Евклида

Я хочу вычислить наименьшее общее кратное массива значений, используя алгоритм Евклида

Я использую эту реализацию псевдокода: найдено в википедии

function gcd(a, b)
    while b ≠ 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a;

Моя реализация javascript такая

function smallestCommons(arr) {

  var gcm = arr.reduce(function(a,b){

    let minNum = Math.min(a,b);
    let maxNum = Math.max(a,b);
    var placeHolder = 0;

    while(minNum!==0){
        placeHolder = maxNum;
        maxNum = minNum;
        minNum = placeHolder%minNum;
    } 

    return (a*b)/(minNum);
  },1);

  return gcm;
}


smallestCommons([1,2,3,4,5]);

Я получаю сообщение об ошибке в цикле while

Бесконечная петля

РЕДАКТИРОВАТЬ Были внесены некоторые исправления, в конце функции gcm я использовал 0 в качестве начального начального значения, оно должно быть 1, так как вы не можете получить gcm из 0.

EDIT2 Ожидаемый результат должен быть 60, так как это наименьшее общее кратное 1,2,3,4,5.


javascript algorithm greatest-common-divisor lcm
person Vincent Tang    schedule 01.11.2017    source источник

Ответы (2)


arrow_upward
25
arrow_downward

С ES6

const gcd = (a, b) => a ? gcd(b % a, a) : b;

const lcm = (a, b) => a * b / gcd(a, b);

Затем используйте сокращение для заданного массива целых чисел:

[1, 2, 3, 4, 5].reduce(lcm); // Returns 60

С ES5

var gcd = function (a, b) {
    return a ? gcd(b % a, a) : b;
}

var lcm = function (a, b) {
    return a * b / gcd(a, b);
}

Затем используйте сокращение для заданного массива целых чисел:

[1, 2, 3, 4, 5].reduce(lcm); // Returns 60
person Елин Й.    schedule 08.04.2018
comment
Красиво, потому что потрясающе коротко и по делу. Лучший ответ ИМО. - person Avatar; 23.09.2018
comment
Мне очень нравится лаконичность версии ES6! Отличная работа, Елин Ю.! - person Jan Molak; 13.12.2019
comment
Превосходное чистое решение, я очень впечатлен :) - person Pete - iCalculator; 21.05.2020

arrow_upward
2
arrow_downward

Вы намеренно перепутали все переменные и последовательность операторов? ;-)

  while(minNum!==0){
        placeHolder = minNum;
        minNum = maxNum % minNum;
        maxNum = placeHolder;
    } 

    //here maxNum = GCD(a,b)

    return (a*b) / (maxNum);  //LCM
person MBo    schedule 01.11.2017
comment
наверное, так как я написал формулу после просмотра видео, то посмотрел вики ;s - person Vincent Tang; 02.11.2017