Страницы

Поиск по вопросам

среда, 12 июня 2019 г.

Сложение всех элементов массива

Нужно решить следующую задачу:
Имеется массив, содержащий произвольные числа: [3], [5], [2], [6] .... Нужно найти суммы всех возможных сложений его элементов и записать их в другой массив. Т.е. получается если в массиве 4 элемента, другой массив должен состоять из 16.
Как реализовать алгоритм?


Ответ

То есть вам нужно получить все возможные подмножества данного множества.
Самый простой вариант - для множества из N элементов берем число из N битов, и проходим по всем возможным значениям числа (для 4 элементов - от 0000 до 1111, т.е. от 0 до 15). Далее для каждого числа суммируем элементы, соответствующие единицам - типа, для 0011 - третий и четвертый (понятно, что удобнее и логичнее считать с младших битов, так что нулевой и первый :))
Думаю, перевести на конкретный язык проблем не составит.
Если задача конкретно в суммах - то я бы смотрел на коды Грея, тогда каждое следующее значение получается путем прибавления или вычитания только одного элемента.

Комментариев нет:

Отправить комментарий