| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > последовательность из N натуральных чисел, чтобы суммы не совпадали |
| Автор: FasterHarder 23.12.23, 04:53 |
| Всем хай! Сходу к делу! Задается 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 |
| Автор: Majestio 23.12.23, 06:02 |
| Цитата FasterHarder @ 1. в теории чисел может как-то называется официально такая последовательность, которая удовлетворяет требованиям задачи 2. существует ли более оптимальный набор ( меньше по значению ), чем 2^i На первый вопрос ответить затрудняюсь. А вот на второй, чуйка подсказывает, что более оптимального не найти. Тут объяснение простое. В такой последовательности каждое число состоит из одного бита, и этот бит находится в уникальной позиции. Суммируя такие числа мы не сможем получить сдвига, соответственно не сможем из нескольких меньших чисел получить какое-то большее или сумму из больших. Даже если пробовать в суммах использовать большие и меньшие вперемешку. |
| Автор: Akina 23.12.23, 17:52 |
| Цитата FasterHarder @ 1. ни одно из чисел последовательности нельзя получить любой суммой из других чисел последовательности ( это требование не обязательное, но желательное ) 2. ни одну сумму чисел в произвольном количестве ( хоть все суммировать ) нельзя представить такой же суммой, но другим набором чисел. Первое - частный случай второго. Отбросить. Для 4 чисел существует набор (3,5,6,7), где максимальное из чисел менее такового в наборе из степеней двойки при той же длине набора. Для 5 чисел это, например, (7,10,12,13,14). И так далее... То есть, "Нет" - ответ заведомо неверный. |
| Автор: Majestio 23.12.23, 19:36 |
| При такой постановки "оптимальности", когда берется максимальное число, да - варианты есть. Я что-то тормознул, и посчитал, что оптимальным будет набор с меньшей суммой. |
| Автор: FasterHarder 24.12.23, 05:36 |
| ок, спс, есть над чем подумать... про битовую картину тоже мысли были насчет критерия оптимальности - моя недоработка, не указал в условии,но тут вроде напрашивается 2 критерия основных 1. макс.число в такой последовательности 2. сумма этих чисел **3 простота получения очередного числа последовательности <----- и вот этот момент, хм... вот этот ряд из 2^i своего рода "золотое сечение", т к он гарантированно дает то, что нужно вариант, предложенный Akina лучше ( "оптимальнее" ), но за это придется платить нахождением очередного числа. Тут ведь вроде сложность факториальная будет, т к нужно перебрать ВСЕ возможные суммы и их сопоставить. На какой-то итерации не хватит мощностей, чтобы получить такое число, хотя суммы, полученные на предыдущих этапах где-то можно хранить ( типа мемоизация ), но это лютые накладные расходы. А для ряда 2^i очередное значение получается за O(1). Еще ведь в др.рядах, отличных от 2^i все равно макс. значение будет стремиться к макс. из ряда 2^i. Т е ряды буду "примерно" одинаковые. И еще момент остается, а ВСЕГДА ли можно продолжать получать ряд, члены которого не подчиняются 2^i...наверное, да) |