2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:46 
Аватара пользователя
Изменение массива удвоит количество числовых сравнений, но уж или место, или время. Золотое правило.
С умножениями и прочими многочленами такая беда: вдруг числа очень большие, на грани формата. И что делать?

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 13:00 
gris в сообщении #621360 писал(а):
Изменение массива удвоит количество числовых сравнений

Ничего не увеличит -- ведь проверка булевского массива тоже подразумевает сравнение. Хуже того: поскольку при этом обращаться придётся к дополнительному участку памяти -- время за счёт использования булевского массива только увеличится (если не вдаваться в детали архитектуры процессора).

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

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 13:06 
Аватара пользователя
Cash в сообщении #621359 писал(а):
Достаточно ли этого теоретически?
Теоретически необходимо $n$ алгебраически независимых симметрических многочленов.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 13:09 
Аватара пользователя
У Вас проверяется восемь условий. А Вы хотите обойтись проверкой трёх или четырёх.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 13:17 
Кстати, можно ли как-то быстро вычислить $N$ элементарных симметрических многочленов? В голову приходят только способы со сложностью $O(N^2)$.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 13:28 
Евгений Машеров в сообщении #621366 писал(а):
У Вас проверяется восемь условий. А Вы хотите обойтись проверкой трёх или четырёх.
На мой взгляд, чисто теоретически в целочисленном случае достаточно проверки одного условия. Что-нибудь типа
$\sum\limits_{k=1}^8 9^{a_k} = \sum\limits_{k=1}^8 9^{b_k}$
Но на практике такой подход, естественно, неприменим.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 17:26 
Цитата:
Теоретически необходимо $n$ алгебраически независимых симметрических многочленов

В общем случае, да.
Но ведь у нас же данные - целочисленные. Неужели это нисколько не меняет дело?

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 17:58 
Аватара пользователя
Cash в сообщении #621461 писал(а):
В общем случае, да.
Но ведь у нас же данные - целочисленные. Неужели это нисколько не меняет дело?
Ну, можно упаковать все в одно целое число. А вообще, если переменная умеет хранить $2^n$ значений, то для однозначного восстановления однго из $C_{2^n}^8$ сочетаний потребуется не меньше $7$ переменных при $n\geq 8$ и $8$ переменных при $n\geq 16$.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 20:18 
Если предполагается, что неравных массивов будет значительно больше чем равных, то с чисто практической точки зрения в алгоритме программы можно использовать сначала сравнение сумм, если равно, то сравнение произведений, ну, и в самом конце - сортировку и т.п.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 20:34 
Возможно я не понял какая именно задача решается - нахождение для определенного массива всех массивов, удовлетворяющих условиям равенства сумм и произведений элементов исходному? Тогда я бы начал с произведений, а именно - разложил бы каждый элемент исходного массива на простые множители (щедро досыпав единиц), получил бы все возможные массивы - комбинации этих множителей, дающие в произведении значение исходного массива, а потом проверял бы их на сумму.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 20:55 
Задача состоит в том, чтобы дать ответ, можно ли из второго массива получить первый, путём перестановки его элементов. Сортировать запрещается.
Ну в общем-то я уже сделал её, так как мою гипотезу безжалостно опровергли :mrgreen: пришлось делать по другому: считаю количество нулей в одном и другом массиве, если не совпадает сразу ответ "нет", а иначе начинаю цикл, беру первый элемент массива, если ноль, беру следующий, если нет, то считаю сколько раз этот элемент встречается в обоих массивах, одновременно с этим обнуляю эти элементы, проверяю, совпадает ли количество, если совпадает берём следующий элемент, если нет, сразу ответ "нет", ну и так проверяю все элементы.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 21:34 
main.c в сообщении #621573 писал(а):
иначе начинаю цикл, беру первый элемент массива, если ноль, беру следующий, если нет, то считаю сколько раз этот элемент встречается в обоих массивах,

Зачем сколько раз-то?...

Как только для очередного ненулевого элемента первого массива встречается равный ему элемент второго -- тот элемент второго надо обнулить и перейти к следующему ненулевому элементу первого массива. И как только такой встречи не случилось -- всё, совпадения нет. А если удалось пройти первый массив до конца, так и не наткнувшись на невстречу -- значит, совпадение.

Мой предыдущий вариант с манипуляцией знаками подразумевал ровно то же самое, только в качестве маркера использовался знак, а не нулёвость. Достоинство знакового подхода: возможность при необходимости восстановить исходные массивы без потери памяти и при этом практически без потери скорости. Недостаток: вдвое уменьшается допустимый диапазон входных данных; но -- всего лишь вдвое.

----------------------------
Истчо Пыс. Это темо -- явно алгоритмическое, и место ей -- откровенно не в математике, а в компьютерных разделах. Это к сведению модераторов.

 
 
 
 Re: Доказать гипотезу.
Сообщение21.09.2012, 20:41 
Аватара пользователя
Ну,я бы сказал, что тут есть математическая сторона вопроса и алгоритмическая. Математическая - можно ли сравнить два набора из n чисел с точностью до перестановки (мультимножества?), проверив менее чем n условий. Для вещественных чисел ответ довольно тривиален - нет, нельзя. Для целых чисел, ограниченных по диапазону значений, ответ неясен. Полагаю, тоже нельзя. Но контрпример с ходу не нарисую. Алгоритмическая же - как лучше всего организовать проверку. И она действительно уместна в другом форуме.

 
 
 
 Re: Доказать гипотезу.
Сообщение21.09.2012, 20:46 
Аватара пользователя
Для целых чисел, ограниченных по диапазону, можно весь массив зашифровать в одно число (правда, очень большое) и сравнивать только его.

-- Пт, 2012-09-21, 21:47 --

Или Вы имели в виду, что все доступные нам переменные ограничены, так что собрать такое число не выйдет?

 
 
 
 Re: Доказать гипотезу.
Сообщение21.09.2012, 22:00 
Аватара пользователя
Можно. Скажем, значения 8 симметрических многочленов, приписанные один за другим. Но ни в какую разрядную сетку не влезут...

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


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