Форум на Исходниках.RU

последовательность из N натуральных чисел, чтобы суммы не совпадали

FasterHarder — Sun, 24 Dec 2023 05:36:05 +0000

FasterHarder: ок, спс, есть над чем подумать...
про битовую картину тоже мысли были

насчет критерия оптимальности - моя недоработка, не указал в условии,но тут вроде напрашивается 2 критерия основных
1. макс.число в такой последовательности
2. сумма этих чисел
**3 простота получения очередного числа последовательности <----- и вот этот момент, хм...

вот этот ряд из 2^i своего рода "золотое сечение", т к он гарантированно дает то, что нужно
вариант, предложенный Akina лучше ( "оптимальнее" ), но за это придется платить нахождением очередного числа. Тут ведь вроде сложность факториальная будет, т к нужно перебрать ВСЕ возможные суммы и их сопоставить. На какой-то итерации не хватит мощностей, чтобы получить такое число, хотя суммы, полученные на предыдущих этапах где-то можно хранить ( типа мемоизация ), но это лютые накладные расходы. А для ряда 2^i очередное значение получается за O(1).

Еще ведь в др.рядах, отличных от 2^i все равно макс. значение будет стремиться к макс. из ряда 2^i. Т е ряды буду "примерно" одинаковые.
И еще момент остается, а ВСЕГДА ли можно продолжать получать ряд, члены которого не подчиняются 2^i...наверное, да)

последовательность из N натуральных чисел, чтобы суммы не совпадали

Majestio — Sat, 23 Dec 2023 19:36:52 +0000

Majestio:

Цитата Akina @ 23.12.23, 17:52

То есть, "Нет" - ответ заведомо неверный.

При такой постановки "оптимальности", когда берется максимальное число, да - варианты есть.
Я что-то тормознул, и посчитал, что оптимальным будет набор с меньшей суммой.

последовательность из N натуральных чисел, чтобы суммы не совпадали

Akina — Sat, 23 Dec 2023 17:52:57 +0000

Akina:

Цитата FasterHarder @ 23.12.23, 04:53

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

Первое - частный случай второго. Отбросить.

Цитата Majestio @ 23.12.23, 06:02

2. существует ли более оптимальный набор ( меньше по значению ), чем 2^i

Для 4 чисел существует набор (3,5,6,7), где максимальное из чисел менее такового в наборе из степеней двойки при той же длине набора. Для 5 чисел это, например, (7,10,12,13,14). И так далее... То есть, "Нет" - ответ заведомо неверный.

последовательность из N натуральных чисел, чтобы суммы не совпадали

Majestio — Sat, 23 Dec 2023 06:02:00 +0000

Majestio:

Цитата FasterHarder @ 23.12.23, 04:53

1. в теории чисел может как-то называется официально такая последовательность, которая удовлетворяет требованиям задачи
2. существует ли более оптимальный набор ( меньше по значению ), чем 2^i

На первый вопрос ответить затрудняюсь. А вот на второй, чуйка подсказывает, что более оптимального не найти. Тут объяснение простое. В такой последовательности каждое число состоит из одного бита, и этот бит находится в уникальной позиции. Суммируя такие числа мы не сможем получить сдвига, соответственно не сможем из нескольких меньших чисел получить какое-то большее или сумму из больших. Даже если пробовать в суммах использовать большие и меньшие вперемешку.

последовательность из N натуральных чисел, чтобы суммы не совпадали

FasterHarder — Sat, 23 Dec 2023 04:53:49 +0000

FasterHarder: Всем хай! Сходу к делу!

Задается N натуральных чисел ( на практике N не превышает 15-20, в теории может быть бесконечно большим ): { n1, n2, n3, ..., nn }. Все числа уникальные.
Надо получить ряд этих чисел, чтобы выполнялись такие условия:
1. ни одно из чисел последовательности нельзя получить любой суммой из других чисел последовательности ( это требование не обязательное, но желательное )
2. ни одну сумму чисел в произвольном количестве ( хоть все суммировать ) нельзя представить такой же суммой, но другим набором чисел.
3. числа в последовательности должны быть минимально возможными ( это тоже не обязательно, но желательно )

Например, такой набор набор не подойдет:
{ 1, 2, 4, 7, 9, 11, 15 }, т к:
1 + 4 + 15 = 9 + 11
1 + 4 + 15 = 4 + 7 + 9
2 + 9 = 11 - хотя не критично...

================================

была идея оттолкнуться от простых чисел, но это провал...
{ 2, 3, 5, 7, 11, 13, 17 ... }
7 + 13 = 3 + 17 --> 20

в итоге, вроде можно задать 2^i, i = [ 0 .. ( n - 1 )]:
n = 6 ---> { 1, 2, 4, 8, 16, 32 }

вопросы:
1. в теории чисел может как-то называется официально такая последовательность, которая удовлетворяет требованиям задачи
2. существует ли более оптимальный набор ( меньше по значению ), чем 2^i

спс

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