2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Доказать гипотезу.
Сообщение20.09.2012, 11:16 
Добрый день, уважаемые форумчане. В одной из задачек по программированию столкнулся с проблемой математического обоснования моего решения.

Задача :
Имеются два целочисленных массива из 8 элементов. Числа могут повторяться.
Для тех кто не знаком с массивами, массив - это упорядоченная последовательность элементов одной природы.
Пример:
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Если из одного массива можно получить другой, путём перестановки элементов, вывести yes.

Но суть не в этом. Суть в том, что я утверждаю: если сумма элементов первого массива равна сумме элементов второго массива и одновременно с этим условием, произведение элементов первого равно произведению элементов второго, эти массивы состоят из одних и тех же чисел.
Как мне это доказать?

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:20 
Аватара пользователя
-1 2 4 0 5 7 1 6
-3 2 6 0 9 1 3 6
Сумма и произведение одинаковы.
Ужесточайте требования к массивам.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:23 
Допустим было бы требование, что "0" в массиве нет.

Даже не так, требования остаются те же, целочисленный массив. Но после подсчёта сумм, заменим все "0" на "1". И после этого проверим равенство произведений.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:35 
Тогда $1,-1,1,-1,1,-1,2,2$.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:36 
EtCetera в сообщении #621332 писал(а):
Тогда $1,-1,1,-1,1,-1,2,2$.

А где второй массив?)

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:45 
Аватара пользователя
2 2 -2 -2 4 4 -4 -4
1 1 -1 -1 8 8 -8 -8

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:50 
Извиняюсь, не вчитался в условие. Тогда тут даже отрицательные не нужны.
$1,1,1,1,1,2,2,9$ и $1,1,1,1,1,1,6,6$.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 11:58 
gris в сообщении #621335 писал(а):
2 2 -2 -2 4 4 -4 -4
1 1 -1 -1 8 8 -8 -8

Этим примером Вы разбили мою гипотезу напрочь :mrgreen: Жаль.
Эту задачу можно решить и в лоб, просто найти каждому элементу свою пару, если не найдётся, то значит такой перестановки не существует. НО хотелось бы найти более изысканное решение. Может быть всё-таки есть какой-нибудь математический способ решения этой задачи?

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:03 
Аватара пользователя
Можно отсортировать, потом поэлементно сравнить. Но так, как Вы сказали даже быстрее. Только надо как-то помечать найденные элементы во втором массиве. Переставлять их вперёд.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:14 
Аватара пользователя
Sounds like $O(N^2)$.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:16 
Аватара пользователя
ИСН в сообщении #621347 писал(а):
Sounds like $O(N^2)$.

На массивах из 8 элементов действительно быстрее. Там сортировка меньше, чем за 16 сравнений не делается.

-- Чт сен 20, 2012 13:18:41 --

Кстати, если хочется все-таки поскладывать и поумножать, то можно вычислить все элементарные симметрические многочлены и сравнить их.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:19 
gris в сообщении #621344 писал(а):
Можно отсортировать, потом поэлементно сравнить. Но так, как Вы сказали даже быстрее. Только надо как-то помечать найденные элементы во втором массиве. Переставлять их вперёд.


В том то и дело, что сортировать массив запрещается, в гипотезе это было не важно, поэтому про это условие я не писал. Больше никаких важных условий нет.

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:21 
Аватара пользователя
Ну тогда типа каждый с каждым. Дополнительный массив понадобится, хоть булевский.
Зато одни сравнения. А то умножать да складывать. На все многочлены тыща умножений и тыща сложений. Да ещё 8 сравнений. :-)

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:39 
gris в сообщении #621352 писал(а):
Дополнительный массив понадобится, хоть булевский.

Не обязательно. Если элементы массивов положительны, то для их вычёркивания достаточно приписывать им минусы. Потом при желании массивы можно и восстановить.

Если произвольного знака, то задача сводится к предыдущей, если найти минимальный элемент и вычесть его значение минус один из каждого. В общем, снять кастрюлю, вылить воду, налить воду, поставить на плиту...

 
 
 
 Re: Доказать гипотезу.
Сообщение20.09.2012, 12:44 
Вместо произведения элементов можно использовать сумму квадратов и кубов. В практическом смысле совпадения трех сумм вполне достаточно. Достаточно ли этого теоретически? Интересно будет поискать контрпример.

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


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