Построить набор слагаемых, каждая сумма представляется единс

[foroshchuk]

Задача состоит в следуещем:
Нужно найти массив из N разных чисел.
Любая сумма может быть сформирована только одной комбинацией чисел из этого массива.
Например, есть массив простых чисел:
7, 11, 13, 17, 19, 23, 29, 31, 43.
Сумма "31" может получиться как
1) 11+13+17
2) так и само число 31
Т.е. такой массив не подходит.
Если выпало, например, число 20, то можно было бы точно сказать, что оно получилось путем сложения 5+15 (числами из массива) или 20 - число массива.

[PAV]

Вы хотите узнать какой-либо теоретический способ строить такие массивы или речь о программе, которая бы каким-либо образом строила массивы такого рода, при этом допускаются элементы перебора?

В сумме каждое слагаемое может встречаться не более одного раза или допускаются повторы?

[foroshchuk]

Числа в комбинации не могут повторяться. Суммы формируются путем сложения разных чисел в массиве.
Я пишу диплом по электроннике. И вот появился стопор в построении мат. модели расчета таких чисел, которые будут использовать контроллер. Количество этих чисел в массиве может колебаться, в зависимости от условий. По-этому, хотелось бы теоретическую модель для начала понять. Все-таки диплом.

[Руст]

Простейший набор это числа $2^k, k=0,1,2...$. Если все натуральные числа представимы в виде конечного набора суммы натуральных чисел из заданного набора, то другого такого набора не существует.

[foroshchuk]

Таким способом можно получить массив натуральных чисел, но 2^100 даст уже очень большое число.
Здесь задача немного сложнее.
Эти числа - это номиналы сопротивлений резисторов. Если принять 2^0 за 1 кОм, то 2^10 даст уже 1 МОм. Технически это не эффективно.
Нужно расширить количество возможных номиналов в пределах 1 Ом - 1 МОм до 100 шт.
Может есть другая возможность?
Кстати,я только заметил, что 2^k ,k=0,1,2 не подходит, т.к. получится комбинация в массиве не удовлетворяет условию.
1, 2, 4, 8, 16, 32, 64, 128, ...
Например, сумма 32+16=48. Ее можно получить еще и комбинацией 32+2+4+8=48!!!
Не подходит.

[Руст]

Если N чисел удовлетворяют вашему условию (только единственный набор представляет любое возможное значение), то количество всех сумм (включая пустую) равна $Q=2^N$, соответственно сумма чисел всего набора не меньше Q и среди этого набора чисел будут числа большие, чем Q/N. При N=100, так тли иначе встретятся очень большие числа.

[незваный гость]

foroshchuk писал(а):

Ее можно получить еще и комбинацией 32 + 2 + 4 + 8 = 48!!!

32 + 2 + 4 + 8 = 46 (в десятичной системе счисления). Для получения указанных Вами равенств следует перейти в восьмеричную, но там 8 следует записывать как 10

Так что вспомните, что написано большими дружественными буквами на энциклопедии «Автостопом по галактике»: “Don’t panic”

[foroshchuk]

упссс!!!
Точно, ошибся. Спасибо.

[бобыль]

А фибоначчиева арифметика никак не подходит?

[незваный гость]

1,1,2,3,…
1+1+2 = 3+1
не, не подойдет…

[бобыль]

незваный гость писал(а):

:evil:
1,1,2,3,…
1+1+2 = 3+1
не, не подойдет…

В фибоначчиевой арифметике разложение единственно, если в нем запрещено использовать соседние числа Фибоначчи. Поэтому в примере останется только 3 + 1. Я вот только не знаю, подойдет ли автору такая единственность.

[Руст]

Но это ничего не меняет. Запрет использования соседних чисел только слегка уменьшает показатель роста таких чисел от 2 до $\frac{1+\sqrt 5 }{2}$. Как я уже говорил, любая такая совокупность n чисел содержит числа порядка 2^n.

[maxal]

foroshchuk в сообщении #33107 писал(а):

Нужно найти массив из N разных чисел.
Любая сумма может быть сформирована только одной комбинацией чисел из этого массива.
Например, есть массив простых чисел:
7, 11, 13, 17, 19, 23, 29, 31, 43.
Сумма "31" может получиться как
1) 11+13+17
2) так и само число 31
Т.е. такой массив не подходит.

Судя по приведенному примеру, вас заботит больше отсутствие равных сумм, нежели представимость чисел. Да и, собственно говоря, конечным набором чисел нельзя представить "любую сумму", если каждое число из набора используется только один раз. Поэтому требование скорее должно было звучать так:

Любая сумма может быть сформирована не более чем одной комбинацией чисел из этого массива.

Это довольно известная задача - вот для примера статья, где обсуждается построение подобных массивов:
A Construction for Sets of Integers with Distinct Subset Sums

[age]

foroshchuk в сообщении #33107 писал(а):

Задача состоит в следуещем:
Нужно найти массив из N разных чисел.
Любая сумма может быть сформирована только одной комбинацией чисел из этого массива.
Например, есть массив простых чисел:
7, 11, 13, 17, 19, 23, 29, 31, 43.
Сумма "31" может получиться как
1) 11+13+17
2) так и само число 31
Т.е. такой массив не подходит.
Если выпало, например, число 20, то можно было бы точно сказать, что оно получилось путем сложения 5+15 (числами из массива) или 20 - число массива.

Это массив ${100,...,199}$.

[age]

Нет. Не подходит, т.к. в приведенном массиве лишь ни одно число не может быть представлено суммой других, но $100+106=102+104$