Например, есть самый простой массив - [0, 1, 2, 3, 4, 5]
И, скажем, его нужно разделить на 3 массива. Но так, чтобы сумма чисел в получившихся массивах везде была либо равна, либо максимально близкая. В данном случае идеально будет так:
[0, 5]
[4, 1]
[3, 2]
В каждом массиве сумма чисел равна 6.
А есть какая-нибудь формула, по которой можно было бы так поделить массив? Заранее спасибо!
PS: На каком языке - не важно.
Другие языки программирования и технологии
Разделить массив с числами на несколько массивов, чтобы сумма чисел в массивах была равна.
Тут не формула нужна, а алгоритм нужен.
Для такого общего случая, когда элементы массива являются арифметической
прогрессией, можно искать элементы новых массивов как
min(mass)+max(mass). Затем исключать найденные числа из массива и
продолжать операцию. Для таких массивов это подойдет на 100 %.
Что касается для алгоритма общего случая, попробую составить:
Найдем, на какие числа n делится без остатка и чему равен результат деления. n - размерность первоначального массива. Те числа, на которые делится n - размерность новых массивов, результат деления - число новых массивов.
предположим, что массив отсортирован по убыванию.
Тогда заполним первые элементы новых массивов элементами из начального массива, начиная с нулевого элемента.
Результат: (при первоначальном массиве: 39 34 33 25 16 11 9 3 1)
[39
[34
[33
Затем, повторим эту операцию, только заполнять массивы будем снизу вверх
[39 11 = 50
[34 16 = 50
[33 25 = 58
далее находим новый массив с наименьшей суммой и добавляем ему максимальный элемент из оставшихся и т. д.
[39 11 9 ] = 59
[34 16 3 ] = 53
[33 25 1 ] = 59
Думаю, это максимально приближенный результат к условию задачи.
Для такого общего случая, когда элементы массива являются арифметической
прогрессией, можно искать элементы новых массивов как
min(mass)+max(mass). Затем исключать найденные числа из массива и
продолжать операцию. Для таких массивов это подойдет на 100 %.
Что касается для алгоритма общего случая, попробую составить:
Найдем, на какие числа n делится без остатка и чему равен результат деления. n - размерность первоначального массива. Те числа, на которые делится n - размерность новых массивов, результат деления - число новых массивов.
предположим, что массив отсортирован по убыванию.
Тогда заполним первые элементы новых массивов элементами из начального массива, начиная с нулевого элемента.
Результат: (при первоначальном массиве: 39 34 33 25 16 11 9 3 1)
[39
[34
[33
Затем, повторим эту операцию, только заполнять массивы будем снизу вверх
[39 11 = 50
[34 16 = 50
[33 25 = 58
далее находим новый массив с наименьшей суммой и добавляем ему максимальный элемент из оставшихся и т. д.
[39 11 9 ] = 59
[34 16 3 ] = 53
[33 25 1 ] = 59
Думаю, это максимально приближенный результат к условию задачи.
Это чето типа похоже на "задачу укладки рюкзака". Эта задача уже давно решена, поищите в нете, может подойдут те же алгоритмы.
Первое что пришло на ум: складываем все числа в массиве и делим на количество новых массивов. получаем число, к которому должны стремиться суммы новых массивов. Далее перебираем старый массив, пробегаемся по нему и добавляем числа из исходноо так чтобы подогнать к нужной сумме
Похожие вопросы
- Помогите :) Дан массив из n целых чисел. Найти количество встречающихся равных чисел.
- как разделить массив на три части в с++?
- Подсчитать количество 3-значных чисел,сумма цифр которых меньше либо равна 24
- Как разделить файл формата .pdf на несколько файлов???
- Помогите найти алгоритм подбора множителей к числам заданного массива, сумма произведений которых равна заданному числу
- 1.Заполнить массив случайными числами. Вывести элементы массива на экран. Заменить все его минимальные элементы нулями.
- Как получить нужное число из суммы нескольких чисел в массиве?
- Сортировка одномерного массива + вставка числа в отсортированный массив PASCAL
- Pascal . Дан массив вещественных чисел. Найти сумму элементов, номера которых являются простыми числами
- MASM32 случайные числа, , массив
[5
[4
затем
[5 2
[4 3
след. шаг:
проверяем сумму, если сумма у первого массива меньше либо равна сумме эл-ов 2го массива, то заполнение идет с первого массива.
7=7
значит следующим будет заполнятся первый массив
[5 2 1]
[4 3 0]