2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

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

 
 
 
 
Сообщение21.09.2006, 17:24 
Таким способом можно получить массив натуральных чисел, но 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!!!
Не подходит.

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

 
 
 
 
Сообщение21.09.2006, 19:29 
Аватара пользователя
:evil:
foroshchuk писал(а):
Ее можно получить еще и комбинацией 32 + 2 + 4 + 8 = 48!!!

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

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

 
 
 
 
Сообщение21.09.2006, 19:48 
упссс!!!
Точно, ошибся. Спасибо.

 
 
 
 
Сообщение22.09.2006, 18:25 
А фибоначчиева арифметика никак не подходит?

 
 
 
 
Сообщение22.09.2006, 19:24 
Аватара пользователя
:evil:
1,1,2,3,…
1+1+2 = 3+1
не, не подойдет…

 
 
 
 
Сообщение25.09.2006, 13:15 
незваный гость писал(а):
:evil:
1,1,2,3,…
1+1+2 = 3+1
не, не подойдет…


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

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

 
 
 
 Re: Построить набор слагаемых, каждая сумма представляется единс
Сообщение25.12.2009, 02:57 
Аватара пользователя
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

 
 
 
 Re: Построить набор слагаемых, каждая сумма представляется единс
Сообщение26.12.2009, 14:48 
Аватара пользователя
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}$. :D

 
 
 
 Re: Построить набор слагаемых, каждая сумма представляется единс
Сообщение27.12.2009, 16:28 
Аватара пользователя
Нет. Не подходит, т.к. в приведенном массиве лишь ни одно число не может быть представлено суммой других, но $100+106=102+104$

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group