Как найти сумму чисел массива, которых равна определенному числу?

const circle_1 = [7, 2, 3, 5, 16, 50, 25, 40],
      circle_2 = [2, 5, 10, 30, 25, 3, 10, 25],
      circle_3 = [25, 10, 2, 10, 5, 2, 10, 5],
      circle_4 = [7, 2, 3, 20, 3, 7, 2, 5],
      circle_5 = [2, 20, 1, 7, 25, 1, 25],
      circle_6 = [3];


Нужно взять по одному елементу с каждого массива так, чтобы получилось число 136. Как правильно написать алгоритм поиска? Подозреваю, что нужно использовать рекурсию, но никак не раздуплюсь как ее применить. Заранее спасибо

По самому тупому алгоритму получилось так ( МНЕ ОЧЕНЬ СТЫДНО (: )
function findCountByArray() {
  for (let a = 0; a < circle_1.length; a++) {
    for (let b = 0; b < circle_2.length; b++) {
      for (let c = 0; c < circle_3.length; c++) {
        for (let d = 0; d < circle_4.length; d++) {
          for (let e = 0; e < circle_5.length; e++) {
            for (let f = 0; f < circle_6.length; f++) {
              if (circle_1[a] + circle_2[b] + circle_3[c] + circle_4[d] + circle_5[e] + circle_6[f] == 136) {
                return [circle_1[a], circle_2[b], circle_3[c], circle_4[d], circle_5[e], circle_6[f]];
              }
            }
          }
        }
      }
    }
  }
  return [];
}
  • Вопрос задан
  • 2340 просмотров
Решения вопроса 1
rockon404
@rockon404
Frontend Developer
Вот вариант на ES6, используется spread operator:
const circle_1 = [7, 2, 3, 5, 16, 50, 25, 40],
      circle_2 = [2, 5, 10, 30, 25, 3, 10, 25],
      circle_3 = [25, 10, 2, 10, 5, 2, 10, 5],
      circle_4 = [7, 2, 3, 20, 3, 7, 2, 5],
      circle_5 = [2, 20, 1, 7, 25, 1, 25],
      circle_6 = [3];
      
function findSum(value, arrays, i = 0) {
  for (let j = 0; j < arrays[i].length; j++) {
    const el = arrays[i][j];
    
    if (i < arrays.length - 1) {
      const result = findSum(value - el, arrays, i + 1);
      
      if (result !== null) {
        return [el, ...result];
      }
    } else if (el === value) {
      return [el];
    }
  }
  return null;
}

console.log('result', findSum(136, [
  circle_1, 
  circle_2, 
  circle_3, 
  circle_4, 
  circle_5,
  circle_6
]));

// => result  [50, 30, 25, 3, 25, 3]


Демо: https://jsfiddle.net/0ho4g942/
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Astrohas
@Astrohas
Python/Django Developer
Тут товарищ рекурсия нужна
CIRCLES = [
    [7, 2, 3, 5, 16, 50, 25, 40],
    [2, 5, 10, 30, 25, 3, 10, 25],
    [25, 10, 2, 10, 5, 2, 10, 5],
    [7, 2, 3, 20, 3, 7, 2, 5],
    [2, 20, 1, 7, 25, 1, 25],
    [3]
]
condidats = [0,0,0,0,0,0]
      
R  = [];
function get_sum(s, ind){
    if (ind >= CIRCLES.length) {
        if (s == 136) {
           alert(condidats)
         }
     }
    else {
      for (let i in CIRCLES[ind] ){
      	item =  CIRCLES[ind][i];
        condidats[ind] = item;
        get_sum(s+item, ind+1);
      }
    }
}

get_sum(0, 0)


думаю псевдокод понятен
упд: исправил
вот и js говнокод
https://jsfiddle.net/m1nsra5d/4/
Ответ написан
crazy_leo
@crazy_leo
Frontend Developer
Если по легче, то - const count = 136
А если без шуток, что-то типо того:
function findCount (arrays, maxValue) {
  let count = 0
  let chunkPositions = [-1, 0]

  let mergedArray = []
  let resultArray = []

  arrays.forEach(array => {
    mergedArray = mergedArray.concat(array)
  })
  
  for (let i = 0; i < mergedArray.length; i++) {
    if (++chunkPositions[0] == arrays.length) {
      chunkPositions[0] = 0
      ++chunkPositions[1]
    }
    
    if (count >= maxValue) break
    else {
      const [aposition, iposition] = chunkPositions
      const value = arrays[aposition][iposition]
      
      if (!value || (count + value > maxValue)) continue

      count += value
      resultArray.push(value)
    }
  }

  return resultArray
}

findCount([
  [7, 2, 3, 5, 16, 50, 25, 40],
  [2, 5, 10, 30, 25, 3, 10, 25],
  [25, 10, 2, 10, 5, 2, 10, 5],
  [7, 2, 3, 20, 3, 7, 2, 5],
  [2, 20, 1, 7, 25, 1, 25],
  [3]
], 136)

// Output => [7, 2, 25, 7, 2, 3, 2, 5, 10, 2, 20, 3, 10, 2, 3, 1, 5, 10, 7, 5, 3, 2]


Функция работает без рекурсии
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы