Как разделить массив на две части c

Приведу еще тест:

5 3 4 5 6 7 

Ну вроде так 🙂
Отслеживать
задан 20 ноя 2018 в 14:35
975 8 8 серебряных знаков 19 19 бронзовых знаков

уточните пожалуйста, "разница сумм", сумм элементов? и поделить массив можно "как ножницами отрезать"? или можно составлять эти две части из разных частей исходного массива?

20 ноя 2018 в 15:24

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Разбили весь набор с суммой S пополам.

Составили все возможные подмножества первой половины - их 2^20, около миллиона - посильное количество - посчитали и записали суммы подмножеств в массив, отсортировали его

Составили все возможные подмножества второй половины - считаем суммы s2 и по ходу ищем ближайшее к S/2 - s2 бинарным поиском в массиве, полученном ранее (чтобы не работать с дробными, лучше умножить на 2)

Ключевые моменты на Delphi. A[] - массив данных, в Sums[] генерируются все возможные удвоенные суммы первой половины массива. FindClosestIndex бинарным поиском находит индекс значения в Sums , которое вкупе с текущей (удвоенной) суммой csum из второй половины даёт лучшее приближение к общей сумме S

 //обрабатывает первую половину массива procedure GenSums(ix, imax: Integer; csum: Int64); begin if ix >= imax then begin Sums[cnt] := csum; inc(cnt); Exit; end; GenSums(ix + 1, imax, csum); GenSums(ix + 1, imax, csum + Int64(2) * A[ix]); end; //обрабатывает вторую половину массива, проверяя пары с суммами первой procedure CheckSums(ix, imax: Integer; csum: Int64); var k: Integer; begin if ix >= imax then begin k := FindClosestIndex(S - csum, Sums); Best := Min(Best, Abs(S - (Sums[k] + csum))); Exit; end; CheckSums(ix + 1, imax, csum); CheckSums(ix + 1, imax, csum + Int64(2) * A[ix]); end; Примеры выдачи: 20 40 32 83 10 32 13 57 35 Sum=322 Diff=0 22 70 6 Sum=98 Diff=42 86 34 74 25 28 Sum=247 Diff=7 

P.S. Задача не требует самих множеств, судя по образцовому ответу, иначе можно хранить пары сумма-сам набор в виде 20 битов в int32

Как разделить массив на две части c

Скорее всего, данный вопрос не соответствует тематике Stack Overflow на русском, согласно правилам описанным в справке.

Закрыт 5 лет назад .

Разделить массив на две части, поместив в первую элементы, больше среднего арифметического их суммы, а во вторую меньшие. Помогите, пожалуйста.

Если задача, получить новый массив, в котором сначала идут элементы больше среднего арифметического, затем остальные, то достаточно отсортировать массив по убыванию:

В результата в массиве a сначала будут идти элементы больше средне арифметического.

Поэлементное деление массивов С++

Написать функцию, которая делит поэлементно 2 массива. Параметрами функции должны быть оба массива и массив, в который записывается результат.

Массив в С++ задается указателем на область памяти. При передаче массива в функцию копируется указатель, а при работе с ним изменяется область памяти, т. е. изменяется массив.

Функция, выполняющая задачу может выглядеть так:

Однако, чтобы ее проверить надо ввести значения двух массивов, для этого напишем еще одну функцию (чтобы не дублировать код):

В функции main считаем размер массива, выделим память (с помощью оператора new) под 3 массива. Теперь у нас есть 3 области памяти, которые заполним с помощью функции read_array . Затем, вызовет функцию деления массивов, полученный результат выведем на экран. После того, как массивы стали не нужны — освободим память с помощью оператора delete[] .

Исходный код программы целиком:

Результат работы программы:

Разделение массива на 2 массива C#

у меня есть строковый массив (содержащий от 20 до 300 элементов), и я хочу разделить его на 2 отдельных массива, от середины первого.

Я знаю, как я могу это сделать, используя цикл for, но я хотел бы знать, был ли более быстрый / лучший способ сделать он. Мне также нужно правильно разбить массив, даже если он имеет нечетное количество элементов, например:

5 ответов

вы можете использовать linq:

Почему это работает, несмотря на четность исходного массива размер?

в firstArray занимает array.Length / 2 элементы, а второй пропускает первый array.Length / 2 элементы, это означает, что нет никакого конфликта между этими двумя массивами. Конечно, если количество элементов нечетно, мы не можем разделить массив на две равные части размера.

если вы хотите иметь больше элементов в первой половине (в нечетном случае), сделайте это:

Похожие публикации:

1. Как сделать чтобы 2 документа ворд были вместе в окне
2. Как перенести сайт с openserver на хостинг
3. Как перепаять свитчи на клавиатуре
4. Как создать отчет из ms project server

Разделить массив на 3 части

Как можно разделить массив на три части так, чтобы сумма чисел в каждом массиве не превышала сумму в остальных (В тех случаях, когда это возможно), при этом размеры массивов могут быть неодинаковыми.

Отслеживать
218k 15 15 золотых знаков 118 118 серебряных знаков 229 229 бронзовых знаков
задан 14 янв 2021 в 17:43
25 3 3 бронзовых знака
Можно полным перебором всех вариантов.
14 янв 2021 в 17:44
да, но это будет достаточно долго. Есть какие нибудь другие варианты?
14 янв 2021 в 17:47
Никаких граничных условий нет, значит и так сойдёт, зачем ещё то заморачиваться?
14 янв 2021 в 17:50

@KGYT, это просто будет невозможно. Как будет выполняться (x < y && x < z) && (y < z && y < x) && ( z < y && z < x)

14 янв 2021 в 17:52

Сумма всех элементов, деленная на 2 - s. Подгонять три части, начиная с самых больших элементов, так, чтобы сумма каждой части была меньше s. Сначала самые большие - пока можно - в одну. Потом остальные - в другую часть. Потом в третью. Оставшуюся мелочь распихивать по всем трем, как получится. Понятно, что не более чем эвристика.

14 янв 2021 в 17:53

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Сумма всех элементов, деленная на 2 - s . Подгонять три части, начиная с самых больших элементов, так, чтобы сумма каждой части была меньше s . Сначала самые большие - пока можно - в одну. Потом остальные - в другую часть. Потом в третью. Оставшуюся мелочь распихивать по всем трем, как получится. Понятно, что не более чем эвристика. Но, похоже, работает - попробуйте этот код:

#include #include #include #include #include using namespace std; bool exper() < vectorv,a,b,c; int s = 0, sa = 0, sb = 0, sc = 0; for(int i = 50 + rand()%100; i-->0; ) < int z = rand()%1000-50; s += z; v.push_back(z); >sort(v.begin(),v.end()); for(auto it = v.rbegin(); it != v.rend(); it++) < int x = *it; if ((sa + x)*2 < s) < a.push_back(x); sa += x; >else if ((sb + x)*2 < s) < b.push_back(x); sb += x; >else if ((sc + x)*2 < s) < c.push_back(x); sc += x; >else return false; > if (sa < sb+sc && sb < sa+sc && sc < sa+sb) return true; return false; >int main(int argc, char * argv[]) < for(int tot = 0, fail = 0; ;) < fail += !exper(); ++tot; cout > 

Отслеживать
ответ дан 14 янв 2021 в 18:05
218k 15 15 золотых знаков 118 118 серебряных знаков 229 229 бронзовых знаков

Можно было тупо распихивать самые большие элементы в самый незаполненный массив с темже результатом, а не заморачиваться так. Ну и такая проверка не заденет граничных случаев с вероятностью более 99.9999%, да ещё и отрицательных чисел напихает.

14 янв 2021 в 18:20

Заморачиваться? А вы напишите свой ответ, а мы посмотрим. Еще одна неуместная критика для самоутверждения.