Наименее общее несколько - для цикла ломается - JavaScript - PullRequest
Новая
       74

Наименее общее несколько - для цикла ломается - JavaScript

0 голосов
/ 30 декабря 2018

Я прохожу курс на FreeCodeCamp.org, и мне нужно найти «Smallest Common Multiple».Таким образом, я нашел решение, которое, как мне кажется, работает и до определенного момента.Тогда код просто кажется, что он ломается.Вот мой код: 

function smallestCommons(arr) {
  arr = arr.sort((a,b) => {return a - b;});
  console.log(arr);
  var truesec = false;
  for(var a = arr[1]; truesec != true; a++){

    for(var e = 1; e <= arr[1]; e++){
      //console.log(a % e + " " + e);
      if(a % e != 0){
        truesec = false;
        break;
      }else{
        truesec = true;
      }
    }
    //console.log(truesec + " " + a);
    if(truesec == true){
      return a;
    }
  }

  return a;
}


console.log(smallestCommons([23,18]));

Это должно вернуть 6056820 согласно их контрольному списку, но каждый раз, когда я проверяю, я получаю разные результаты, я получаю и 114461 & 122841 из одного и того же кода,Может кто-нибудь сказать мне, что не так с этим?

Вот назначение, если оно помогает: Скрипты промежуточного алгоритма: наименьшее общее кратное

Ответы [ 2 ]

0 голосов
/ 30 декабря 2018

Я бы использовал другой подход к этой проблеме:

  1. функция создания для получения всех простых факторов
  2. создание массива простых факторов всех чисел от a[0] до a[1]
  3. уменьшить массив как наибольшую мощность для каждого простого фактора.
  4. умножить на все простые множители, оставшиеся в массиве

Ваш подход займет O(k*a[1]), когда k ответ - и k может быть очень высоким ...Этот подход займет O((a[1])^2)

Рассмотрим следующий код: 

function smallestCommons2(arr) {
    arr.sort((a,b) => {return a - b;});
    let factors = [];
    for(let i = arr[0]; i <= arr[1]; i++)
        factors.push(findPrimeFactors(i));

    let reduced = reduceFactors(factors);
    let ans = 1;
    for (let i in reduced)
        ans *= Math.pow(i, reduced[i]);
    return ans;
}

function reduceFactors(factorsArr) {
    let factorObject = {};
    for (let i in factorsArr) {
        for(let key in factorsArr[i]) {
            if (!(key in factorObject) || factorObject[key] < factorsArr[i][key])
                factorObject[key] = factorsArr[i][key];
        }
    }
    return factorObject;
}

function findPrimeFactors (num) {
    var primeFactors = [];
    while (num % 2 === 0) {
        primeFactors.push(2);
        num = num / 2;
    }

    var sqrtNum = Math.sqrt(num);
    for (var i = 3; i <= sqrtNum; i++) {
        while (num % i === 0) {
            primeFactors.push(i);
            num = num / i;
        }
    }
    if (num > 2)
        primeFactors.push(num);

    let factorObject = {};

    for (let item of primeFactors) {
        if (item in factorObject)
            factorObject[item] += 1;
        else factorObject[item] = 1;
    }
    return factorObject;
}


console.log(smallestCommons2([23,18]));

Этот код будет выводить 6056820 в сек

Отредактировано -нашел пост , который делает то же самое лучше

0 голосов
/ 30 декабря 2018

Ваш алгоритм пытается найти общее кратное между 1 и большим числом в массиве , что может занять очень много времени.Тем не менее, вопрос от FreeCodeCamp просит вас найти общее кратное между двумя числами в массиве , поэтому результат, рассчитанный по вашему алгоритму, не соответствует тестам.

Чтобы сделать вашрешение работает, вы можете изменить

с for (var e = 1; e <= arr[1]; e++)

на for (var e = arr[0]; e <= arr[1]; e++)

, чтобы выполнить цикл между двумя числами в массиве.

...