Подтвердить что ты не робот

Как найти наименьший общий кратный диапазон чисел?

Учитывая массив из двух чисел, пусть они определяют начало и конец диапазона чисел. Например, [2,6] означает диапазон 2,3,4,5,6. Я хочу написать код javascript, чтобы найти наименее распространенный для диапазона. Мой код ниже работает только для небольших диапазонов, а не что-то вроде [1,13] (который представляет собой диапазон 1,2,3,4,5,6,7,8,9,10,11,12,13), что вызывает переполнение стека. Как я могу эффективно найти наименьшее общее кратное диапазона?

function leastCommonMultiple(arr) {
    var minn, max;
    if ( arr[0] > arr[1] ) {
        minn = arr[1];
        max = arr[0];
    } else {
        minn = arr[0];
        max = arr[1];
    }
    function repeatRecurse(min, max, scm) {
        if ( scm % min === 0 && min < max ) {
            return repeatRecurse(min+1, max, scm);
        } else if ( scm % min !== 0 && min < max ) {
            return repeatRecurse(minn, max, scm+max);
        }
        return scm;
    } 
    return repeatRecurse(minn, max, max);
}
4b9b3361

ОТВЕТЫ

Ответ 1

Я думаю, что это выполняет свою работу.

function leastCommonMultiple(min, max) {
    function range(min, max) {
        var arr = [];
        for (var i = min; i <= max; i++) {
            arr.push(i);
        }
        return arr;
    }

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

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

    var multiple = min;
    range(min, max).forEach(function(n) {
        multiple = lcm(multiple, n);
    });

    return multiple;
}

leastCommonMultiple(1, 13); // => 360360

Ответ 2

function smallestCommons(arr) {
  var max = Math.max(...arr);
  var min = Math.min(...arr);
  var candidate = max;

  var smallestCommon = function(low, high) {
    // inner function to use 'high' variable
    function scm(l, h) {
      if (h % l === 0) {
        return h;
      } else {
        return scm(l, h + high);
      }
    }
    return scm(low, high);
  };

  for (var i = min; i <= max; i += 1) {
    candidate = smallestCommon(i, candidate);
  }

  return candidate;
}

smallestCommons([5, 1]); // should return 60
smallestCommons([1, 13]); // should return 360360
smallestCommons([23, 18]); //should return 6056820

Ответ 3

Мина не такая фантастическая, как другие ответы, но я думаю, что ее легко читать.

function smallestCommons(arr) {
	//order our array so we know which number is smallest and which is largest
	var sortedArr = arr.sort(),
	//the smallest common multiple that leaves no remainder when divided by all the numbers in the rang
	smallestCommon = 0,
	//smallest multiple will always be the largest number * 1;
	multiple = sortedArr[1];

	while(smallestCommon === 0) {
		//check all numbers in our range
		for(var i = sortedArr[0]; i <= sortedArr[1]; i++ ){
			if(multiple % i !== 0 ){
				//if we find even one value between our set that is not perfectly divisible, we can skip to the next multiple
				break;
			}

			//if we make it all the way to the last value (sortedArr[1]) then we know that this multiple was perfectly divisible into all values in the range
			if(i == sortedArr[1]){
				smallestCommon = multiple;
			}

		}

		//move to the next multiple, we can just add the highest number.
		multiple += sortedArr[1];
	}

	console.log(smallestCommon);
	return smallestCommon;
}


smallestCommons([1, 5]); // should return 60.
smallestCommons([5, 1]); // should return 60.
smallestCommons([1, 13]); // should return 360360.
smallestCommons([23, 18]); // should return 6056820.

Ответ 4

Это нерекурсивная версия вашего исходного подхода.

function smallestCommons(arr) {
  // Sort the array
  arr = arr.sort(function (a, b) {return a - b}); // numeric comparison;
  var min = arr[0];
  var max = arr[1];

  var numbers = [];
  var count = 0;

  //Here push the range of values into an array
  for (var i = min; i <= max; i++) {
    numbers.push(i);
  }
  //Here freeze a multiple candidate starting from the biggest array value - call it j
  for (var j = max; j <= 1000000; j+=max) {

    //I increase the denominator from min to max
    for (var k = arr[0]; k <= arr[1]; k++) {

      if (j % k === 0) { // every time the modulus is 0 increase a counting 
        count++; // variable
      }
    }

    //If the counting variable equals the lenght of the range, this candidate is the least common value
    if (count === numbers.length) { 
      return j; 
    }
    else{
      count = 0; // set count to 0 in order to test another candidate
    }
  }
}

alert(smallestCommons([1, 5]));

Ответ 5

 function leastCommonMultiple(arr) {
    /*
      function range(min, max) {
        var arr = [];
       for (var i = min; i <= max; i++) {
        arr.push(i);
      }
       return arr;
    }
    */
    var min, range;
     range = arr;
    if(arr[0] > arr[1]){
       min = arr[1];
    }
    else{
       min = arr[0]
    }

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

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

   var multiple = min;
    range.forEach(function(n) {
       multiple = lcm(multiple, n);
    });

   return multiple;
}

console.log(lessCommonMultiple ([1, 13]))

Ответ 6

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

function LCM(arrayRange) {
    var newArr = [];

    for (var j = arrayRange[0]; j <= arrayRange[1]; j++){
        newArr.push(j);
    }

    var a = Math.abs(newArr[0]);
    for (var i = 1; i < newArr.length; i++) {
        var b = Math.abs(newArr[i]),
            c = a;

        while (a && b) {
            a > b ? a %= b : b %= a;
        }
        a = Math.abs(c * newArr[i] / (a + b))
    }
   return console.log(a);
}

LCM([1,5]);

Ответ 7

Возможно, вы изначально имели переполнение стека из-за опечатки: вы переключались между min и minn в середине repeatRecurse (вы бы поняли, что если repeatRecurse не было определено во внешней функции). При этом фиксированное значение repeatRecurse(1,13,13) возвращает 156.

Очевидным ответом на то, чтобы избежать, является превращение рекурсивной функции в нерекурсивную функцию. Вы можете это сделать:

function repeatRecurse(min, max, scm) {
    while ( min < max ) {
        while ( scm % min !== 0 ) {
            scm += max;
        }
        min++;
    }
}

Но, возможно, вы можете увидеть ошибку на этом этапе: вы не гарантируете, что scm по-прежнему делится на элементы, которые были до min. Например, repeatRecurse(3,5,5)=repeatRecurse(4,5,15)=20. Вместо добавления max вы хотите заменить scm на наименьший общий кратный с помощью min. Вы можете использовать rgbchriss gcd (для целых чисел, !b - это то же самое, что и b===0). Если вы хотите сохранить оптимизацию хвоста (хотя я не думаю, что у любого javascript-механизма есть оптимизация хвоста), youd в конечном итоге:

function repeatRecurse(min, max, scm) {
    if ( min < max ) {
        return repeatRecurse(min+1, max, lcm(scm,min));
    }
    return scm;
}

Или без рекурсии:

function repeatRecurse(min,max,scm) {
    while ( min < max ) {
        scm = lcm(scm,min);
        min++;
    }
    return scm;
}

Это по существу эквивалентно решению rgbchriss. Более элегантный метод может делить и побеждать:

function repeatRecurse(min,max) {
    if ( min === max ) {
        return min;
    }
    var middle = Math.floor((min+max)/2);
    return lcm(repeatRecurse(min,middle),repeatRecurse(middle+1,max));
}

Я бы рекомендовал отказаться от исходного аргумента, являющегося массивом из двух чисел. Во-первых, это приводит к тому, что вы говорите о двух разных массивах: [min,max] и массиве диапазонов. С другой стороны, было бы очень легко передать более длинный массив и никогда не понять, что вы сделали что-то неправильно. Его также требует нескольких строк кода для определения min и max, когда они должны были быть определены вызывающим.

Наконец, если вы будете работать с действительно большими числами, может быть лучше найти наименьшее общее число с использованием простой факторизации чисел.

Ответ 8

function range(min, max) {
  var arr = [];
  for (var i = min; i <= max; i++) {
    arr.push(i);
  }
  return arr;
}

function gcd (x, y) {
  return (x % y === 0) ? y : gcd(y, x%y);
}

function lcm (x, y) {
  return (x * y) / gcd(x, y); 
}

function lcmForArr (min, max) {
  var arr = range(min, max);
  return arr.reduce(function(x, y) {
    return lcm(x, y); 
  });
}

range(10, 15); // [10, 11, 12, 13, 14, 15]
gcd(10, 15); // 5
lcm(10, 15); // 30
lcmForArr(10, 15); //60060

Ответ 9

Функция LCM для диапазона [a, b] 

// Euclid algorithm for Greates Common Divisor
function gcd(a, b)
{ 
	return !b ? a : gcd(b, a % b);
} 

// Least Common Multiple function
function lcm(a, b) 
{
	return a * (b / gcd(a,b));
}

// LCM of all numbers in the range of arr=[a, b] 
function range_lcm(arr)
{
	// Swap [big, small] to [small, big]
	if(arr[0] > arr[1]) (arr = [arr[1], arr[0]]);

	for(x = result = arr[0]; x <= arr[1]; x++) {
		result = lcm(x, result);
	}
	
	return result; 
}

alert(range_lcm([8, 5])); // Returns 840

Ответ 10

Как насчет:

// Euclid Algorithm for the Greatest Common Denominator
function gcd(a, b) {
    return !b ? a : gcd(b, a % b);
  }
  // Euclid Algorithm for the Least Common Multiple

function lcm(a, b) {
    return a * (b / gcd(a, b));
  }
  // LCM of all numbers in the range of arr = [a, b];

function smallestCommons(arr) {
  var i, result;
  // large to small - small to large
  if (arr[0] > arr[1]) {
    arr.reverse();
  } // only happens once. Means that the order of the arr reversed.
  for (i = result = arr[0]; i <= arr[1]; i++) { // all numbers up to arr[1] are arr[0].
    result = lcm(i, result); // lcm() makes arr int an integer because of the arithmetic operator.
  }
  return result;
}
smallestCommons([5, 1]); // returns 60

Ответ 11

function lcm(arr) {
  var max = Math.max(arr[0],arr[1]),
      min = Math.min(arr[0],arr[1]),
      lcm = max;
  var calcLcm = function(a,b){
    var mult=1;
    for(var j=1; j<=a; j++){
      mult=b*j;
      if(mult%a === 0){
        return mult;
      }
    }
  };
  for(var i=max-1;i>=min;i--){
    lcm=calcLcm(i,lcm);
  }
  return lcm;
}
lcm([1,13]); //should return 360360.

Ответ 12

    /*Function to calculate sequential numbers 
in the range between the arg values, both inclusive.*/
    function smallestCommons(arg1, arg2) {
     
       if(arg1>arg2) { // Swap arg1 and arg2 if arg1 is greater than arg2
          var temp = arg1;
          arg1 = arg2;
          arg2 =temp;
        }
      
      /*
      Helper function to calculate greatest common divisor (gcd)
      implementing Euclidean algorithm */
      function gcd(a, b) {
      	return b===0 ? a : gcd(b, a % b); 
       }
      
      /*
      Helper function to calculate lowest common multiple (lcm) 
of any two numbers using gcd function above */
       function lcm(a,b){
          return (a*b)/gcd(a,b);
         }
      
      var total = arg1; // copy min value
      for(var i=arg1;i<arg2;i++){
          total = lcm(total,i+1);
         }
      //return that total
      return total;
    }
    /*Yes, there are many solutions that can get the job done.
    Check this out, same approach but different view point.
    */
    console.log(smallestCommons(13,1)); //360360

Ответ 13

Вот мое решение. Надеюсь, вам будет легко следовать:

function smallestCommons(arr) {
  var min = Math.min(arr[0], arr[1]);
  var max = Math.max(arr[0], arr[1]);

  var smallestCommon = min * max;

  var doneCalc = 0;

  while (doneCalc === 0) {
    for (var i = min; i <= max; i++) {
      if (smallestCommon % i !== 0) {
        smallestCommon += max;
        doneCalc = 0;
        break;
      }
      else {
        doneCalc = 1;
      }
    }
  }

  return smallestCommon;
}

Ответ 14

Вот еще одно нерекурсивное решение for-loop

function smallestCommons(arr) {
  var biggestNum = arr[0];
  var smallestNum = arr[1];
  var thirdNum;
  //make sure biggestNum is always the largest
  if (biggestNum < smallestNum) {
    thirdNum = biggestNum;
    biggestNum = smallestNum;
    smallestNum = thirdNum;
  }
  var arrNum = [];
  var count = 0;
  var y = biggestNum;

  // making array with all the numbers fom smallest to biggest
  for (var i = smallestNum; i <= biggestNum; i += 1) {
    arrNum.push(i);
  }

  for (var z = 0; z <= arrNum.length; z += 1) {
    //noprotect
    for (y; y < 10000000; y += 1) {
      if (y % arrNum[z] === 0) {
        count += 1;
        break;
      }
      else if (count === arrNum.length) {
        console.log(y);
        return y;
      }
      else {
        count = 0;
        z = 0;
      }
    }
  }
}
smallestCommons([23, 18]);

Ответ 15

function smallestCommons(arr) {
  var sortedArr = arr.sort(); // sort array first
  var tempArr = []; // create an empty array to store the array range
  var a = sortedArr[0];
  var b = sortedArr[1];
  for(var i = a; i <= b; i++){
    tempArr.push(i);
  }
  // find the lcm of 2 nums using the Euclid algorithm
  function gcd(a, b){
    while (b){
      var temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

  function lcm(a, b){
    return Math.abs((a * b) / gcd(a, b));
  }
  var lcmRange = tempArr.reduce(lcm);


  return lcmRange;
}

Ответ 16

Эй, я наткнулся на эту страницу и хотел поделиться своим решением:)

function smallestCommons(arr) {
  var max = Math.max(arr[0], arr[1]),
      min = Math.min(arr[0], arr[1]),
      i = 1;
  while (true) {
    var count = 0;
    for (j = min; j < max; j++) {
      if (max * i % j !== 0) {
        break;
      }
      count++;
    }
    if (count === (max - min)) {
      alert(max * i);
      return max * i;
    }
    i++;
  }
}
smallestCommons([23, 18]);

Ответ 17

function smallestCommons(arr) {
    let smallest, biggest, min;
    arr.reduce(function (a, b) {
        biggest = Math.max(a, b);
    });
    const max = biggest;
    arr.reduce(function (a, b) {
        smallest = Math.min(a, b);
        min = smallest;
    });
    check: while (true) {
        biggest += max;
        for (min = smallest; min < max; min++) {
            if (biggest % min != 0) {
                continue check;
            }
            if (min == (max - 1) && biggest % min == 0) {
                console.warn('found one');
                return biggest;
            }
        }
    }
}