Форум программистов, компьютерный форум, киберфорум
Наши страницы
JavaScript
Войти
Регистрация
Восстановить пароль
 
Voliki
0 / 0 / 0
Регистрация: 01.05.2013
Сообщений: 14
1

Сложение элементов массива по несколько штук

05.09.2017, 14:02. Просмотров 282. Ответов 3
Метки нет (Все метки)

Здравствуйте! Есть проблема, уже дня три не могу решить. Есть массив числе, и есть значение К количество чисел, которые нужно сложить. Например дан массив [0,1,2,3,4,5,6,7] и К=3, нужно сложить сначала 3 первых числа, затем два первых и следующее через одно. То есть 0+1+2 / 0+1+3 / 0+1+4 .... 0+2+3 / 0+2+4 / и тд пока не получатся все комбинации. Есть такой код
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function chooseBestSum(t, k, mas) {
 var coord = [];
            var rezmas = [], max = [];
            var h = 0;
            var top = 0;
            for (var i = 0; i < k; i++)
                coord[i] = i;
            for (var i = 1; i <= k; i++) {
                max[i-1] = mas.length-k+i;
            }
            if (mas.length < k)
                return null;
 
            var ret = rek(mas, coord, rezmas, k, 0, max, h, t);
            for (var i = 0; i < ret.length; i++) {
                if (top < ret[i] && ret[i] <= t)
                    top = ret[i];
            }
            if(top == 0)
              top = null;
            return top;
        }
        function rek(mas, coord, rezmas, k, p, max, h, t) {
            var prom = 0;
                if (coord[coord.length - 1] < mas.length) {
                    for (var i = 0; i < k; i++)
                        prom += mas[coord[i]]
                    if(prom <= t){
                    rezmas[p] = prom;
                    if (coord[0] != mas.length - k) {  
                        prom = 0;
                        p++;
                        coord[coord.length - 1] += 1;
                        rek(mas, coord, rezmas, k, p, max, h, t);
                    } else return rezmas;
                    }
                } else {
                    h = 0;
                    for (var j = 0; j < k; j++) {
                        if (coord[j] == max[j]) {
                            coord[j - 1] = coord[j - 1]+1;
                            for (var o = 0; o < k - (j); o++) {
                                coord[j + o] = coord[j + o-1] + 1;
                                h = h + 1;
                            }
                        }
                        if (h>0)
                        {
                            break;
                        }     
                    }
                    rek(mas, coord, rezmas, k, p, max, h, t);
                }
                return rezmas;
        }
mas - массив чисел, k - количество чисел которое нужно сложить, t значение которое сравнивается с ответом.
да и еще среди сумм чисел необходимо найти близкое к t либо равняющемуся ему. Ну могу найти логическую ошибку, не со всеми массивами может работать. 28 строка где идет проверка значения работает не правильно, если ответ не будет найдет до того как это условие будет ложно то получается ошибка, а без него идет переполнение стека, подскажите как можно переделать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.09.2017, 14:02
Ответы с готовыми решениями:

HTML спойлер - несколько штук на страницу - работает только первый
Всем привет. Подскажите, пожалуйста, есть код спойлера, есть 5 пунктов на...

Разбивка набора элементов по 6 штук и объединение их в блоки по 6 штук
Есть набор элементов class=&quot;row&quot; Нужно их разбить в группы по 6 штук и...

Использовать TMemo для ввода элементов целочисленного массива в количестве 10 штук
Задание следущее: Дан массив целых чисел, состоящий из 10 элементов. Заполнить...

RegExp несколько штук
Нужны следующие регулярные выражения 1)&lt;%= &quot;любые символы&quot; %&gt; 2)%&gt; &quot;любые...

CompletableFuture блоками по несколько штук
Здравствуйте! Подскажите как можно реализовать получше такое: -есть много...

3
j2FunOnly
Модератор
910 / 845 / 490
Регистрация: 05.06.2015
Сообщений: 1,949
05.09.2017, 14:50 2
Voliki, не надо создавать тему в нескольких разделах, а то придет злой модератор и а-та-та.

Цитата Сообщение от Voliki Посмотреть сообщение
То есть 0+1+2 / 0+1+3 / 0+1+4 .... 0+2+3 / 0+2+4 / и тд
Это ваше многоточие ни разу не красноречиво...
Я вас правильно понял, что вы хотите получить суммы всех возможных комбинаций заданного размера элементов массива?

Добавлено через 10 минут
То есть
Код
[0, 1, 2] // => 3
[0, 1, 3] // => 4
[0, 1, 4] // => 5
[0, 1, 5] // => 6
[0, 1, 6] // => 7
[0, 1, 7] // => 8
[0, 2, 3] // => 5
[0, 2, 4] // => 6
[0, 2, 5] // => 7
[0, 2, 6] // => 8
[0, 2, 7] // => 9
[0, 3, 4] // => 7
[0, 3, 5] // => 8
[0, 3, 6] // => 9
[0, 3, 7] // => 10
[0, 4, 5] // => 9
[0, 4, 6] // => 10
[0, 4, 7] // => 11
[0, 5, 6] // => 11
[0, 5, 7] // => 12
[0, 6, 7] // => 13
[1, 2, 3] // => 6
[1, 2, 4] // => 7
[1, 2, 5] // => 8
[1, 2, 6] // => 9
[1, 2, 7] // => 10
[1, 3, 4] // => 8
[1, 3, 5] // => 9
[1, 3, 6] // => 10
[1, 3, 7] // => 11
[1, 4, 5] // => 10
[1, 4, 6] // => 11
[1, 4, 7] // => 12
[1, 5, 6] // => 12
[1, 5, 7] // => 13
[1, 6, 7] // => 14
[2, 3, 4] // => 9
[2, 3, 5] // => 10
[2, 3, 6] // => 11
[2, 3, 7] // => 12
[2, 4, 5] // => 11
[2, 4, 6] // => 12
[2, 4, 7] // => 13
[2, 5, 6] // => 13
[2, 5, 7] // => 14
[2, 6, 7] // => 15
[3, 4, 5] // => 12
[3, 4, 6] // => 13
[3, 4, 7] // => 14
[3, 5, 6] // => 14
[3, 5, 7] // => 15
[3, 6, 7] // => 16
[4, 5, 6] // => 15
[4, 5, 7] // => 16
[4, 6, 7] // => 17
[5, 6, 7] // => 18
Добавлено через 4 минуты
Цитата Сообщение от Voliki Посмотреть сообщение
и еще среди сумм чисел необходимо найти близкое к t либо равняющемуся ему
Ну это просто, определитесь в каком разбеге это число "близкое" и сравнивайте разницу по модулю, если эта разница равна 0 или меньше вашего "критерия близости" чисел, то ответ подходит.

P.S. ваш код не смотрел.
0
Voliki
0 / 0 / 0
Регистрация: 01.05.2013
Сообщений: 14
05.09.2017, 16:30  [ТС] 3
Цитата Сообщение от j2FunOnly Посмотреть сообщение
Это ваше многоточие ни разу не красноречиво...
Я вас правильно понял, что вы хотите получить суммы всех возможных комбинаций заданного размера элементов массива?
Вы меня верно поняли, но массивы в задаче значительно отличаются от примера, который я показал
Цитата Сообщение от j2FunOnly Посмотреть сообщение
Ну это просто, определитесь в каком разбеге это число "близкое" и сравнивайте разницу по модулю, если эта разница равна 0 или меньше вашего "критерия близости" чисел, то ответ подходит.
это я знаю как сделать, просто написал для полного понимания задачи.
0
j2FunOnly
Модератор
910 / 845 / 490
Регистрация: 05.06.2015
Сообщений: 1,949
05.09.2017, 18:37 4
Цитата Сообщение от Voliki Посмотреть сообщение
но массивы в задаче значительно отличаются от примера, который я показал
Значительно это как? Цифры другие?

Добавлено через 1 час 39 минут
Нам надо получить комбинации массивов заданной длины, JS массивы из коробки это не умеют. Не проблема, у нас есть эти ваши интернеты: https://gist.github.com/axelpale/3118596 (MIT)
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function k_combinations(set, k) {
  var i, j, combs, head, tailcombs;
 
  if (k > set.length || k <= 0) {
    return [];
  }
 
  if (k == set.length) {
    return [set];
  }
 
  if (k == 1) {
    combs = [];
    for (i = 0; i < set.length; i++) {
      combs.push([set[i]]);
    }
    return combs;
  }
 
  combs = [];
  for (i = 0; i < set.length - k + 1; i++) {
    head = set.slice(i, i + 1);
    tailcombs = k_combinations(set.slice(i + 1), k - 1);
    for (j = 0; j < tailcombs.length; j++) {
      combs.push(head.concat(tailcombs[j]));
    }
  }
  return combs;
}
Нам нужны только те элементы, сумма которых удовлетворяет нашему условию. Хелпер для подсчета суммы элементов массива (и этого JS не умеет из коробки ) Можно конечно хакнуть класс Array, но манкипатч не путь для самураев.
Javascript
1
2
3
4
5
function sum(array) {
  var sum = 0;
  array.forEach(el => sum += el);
  return sum;
}
И пишем функцию-фильтр:
Javascript
1
2
3
4
5
6
function accepted(sumToFind, maxDelta) {
  return v => {
    const delta = Math.abs(sum(v) - sumToFind);
    return delta >= 0 && delta <= maxDelta;
  }
}
Все готово, вот и наша функция которая возвращает массив массивов, которые так долго искали
Javascript
1
2
3
function chooseBestSum(t, k, mas, d) {
  return k_combinations(mas, k).filter(accepted(t, d));
}
Итого
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
<form>
  <h3>[0, 1, 2, 3, 4, 5, 6, 7]</h3>
  <label>Найти:</label>
  <input name="sumToFind" type="number" min="0" value="10">
  <label>Погрешность:</label>
  <input name="criteria" type="number" min="0" max="5" value="0">
  <label>Длина комбинации:</label>
  <input name="combLength" type="number" min="0" max="6" value="3">
  <input type="submit" value="Найти">
  <h3>Result:</h3>
  <output name="result"></output>
</form>
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// _https://gist.github.com/axelpale/3118596
function k_combinations(set, k) {
  var i, j, combs, head, tailcombs;
 
  if (k > set.length || k <= 0) {
    return [];
  }
 
  if (k == set.length) {
    return [set];
  }
 
  if (k == 1) {
    combs = [];
    for (i = 0; i < set.length; i++) {
      combs.push([set[i]]);
    }
    return combs;
  }
 
  combs = [];
  for (i = 0; i < set.length - k + 1; i++) {
    head = set.slice(i, i + 1);
    tailcombs = k_combinations(set.slice(i + 1), k - 1);
    for (j = 0; j < tailcombs.length; j++) {
      combs.push(head.concat(tailcombs[j]));
    }
  }
  return combs;
}
 
function sum(array) {
  var sum = 0;
  array.forEach(el => sum += el);
  return sum;
}
 
function accepted(sumToFind, maxDelta) {
  return v => {
    const delta = Math.abs(sum(v) - sumToFind);
    return delta >= 0 && delta <= maxDelta;
  }
}
 
function chooseBestSum(t, k, mas, d) {
  return k_combinations(mas, k).filter(accepted(t, d));
}
 
const mas = [0, 1, 2, 3, 4, 5, 6, 7];
document.querySelector('form').addEventListener('submit', function(e) {
  e.preventDefault();
  const t = parseInt(this.sumToFind.value, 10);
  const k = parseInt(this.combLength.value, 10);
  const d = parseInt(this.criteria.value, 10);
 
  const b = chooseBestSum(t, k, mas, d);
  this.result.value = '';
  if (b.length) {
    b.forEach(n => this.result.innerHTML += `${n} => ${sum(n)}<br>`);
  } else {
    this.result.value = 'Not found';
  }
});
https://jsfiddle.net/j2FunOnly/4mehc3z8/
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2017, 18:37

Выгрузка данных в таблицу по несколько штук
Очень нужна ваша помощь! есть таблица &lt;table&gt; &lt;thead&gt; &lt;tr&gt; ...

Перемещение файлов из папки в несколько папок по 1000 штук
Здравствуйте! Помогите решить задачу, плиз. Есть папка, содержащая примерно 30...

Напечатать в виде списка стоимости несколько штук указанного товара
Ребята помогите: Одна штука некоторого товара стоит 20,4 рублей. Напечатать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru