Автор Тема: Найти уникальное множество  (Прочитано 256 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Найти уникальное множество
« : Январь 18, 2018, 11:55:48 pm »
Есть 2N+1 подмножество. Известно, что каждое подмножество, кроме одного, имеет парное, равное ему. Да, к тому же троек равных множеств нет. Как найти это уникальное подмножество?
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #1 : Январь 19, 2018, 01:19:24 pm »
Байт, интересная задача... Но, если два множества равны, то это одно множество. Или я что-то не понимаю?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #2 : Январь 19, 2018, 07:29:17 pm »
если два множества равны, то это одно множество.
Хорошо, давайте так. Прилетела птичка, и клюет подмножества. Почти все она клюнула 2 раза(или 4, или 6). А одно - не успела, вспугнули птаху. Клюнула только один раз. Но все, что она клюнула, в животике остались (вот такое клевание с возвратом). Клюнет раз - в пузике копия. Клюнет другой - еще одна. Есть ли разумные варианты определить клюнутое однократно множество?
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #3 : Январь 19, 2018, 07:34:20 pm »
Просто хотел перевести на язык множеств одну симпатичную задачку, но внятно изложить, видимо. не удалось.
Тогда вот первоначальная постановка.
Есть ряд из 2N+1 чисел. Все числа в этом ряду, кроме одного, имеют пару. Требуется найти это уникальное число.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #4 : Январь 20, 2018, 12:30:12 pm »
Требуется найти это уникальное число.
Байт
Немного не понял. Имеется в виду отыскать алгоритм, приводящий к этому числу? Так? Или что-то другое?
И, наверное, имеется в виду сделать это за один проход по всей последовательности. Так или нет? Если нет, то многократный перебор рано или поздно приведёт к нужному результату.
Развейте мои сомнения.
Весь предшествующий опыт убеждает нас в том, что природа представляет собой реализацию простейших математически мыслимых элементов................Альберт Эйнштейн
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #5 : Январь 21, 2018, 01:25:33 pm »
Имеется в виду отыскать алгоритм, приводящий к этому числу? Так?
Да, конечно.
И, наверное, имеется в виду сделать это за один проход по всей последовательности.
Имеется в виду - найти наиболее эффективный алгоритм. В частности, да, линейный вполне устроит. Довольно интересен, хотя и прост, алгоритм сложности N*lnN. Но есть и лучше. Линейный есть.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: ARRY

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #6 : Январь 25, 2018, 11:56:16 am »
Ну что ж, если задача не привлекла внимания почтенной публики, остается только дать решение и о теме забыть.
XOR - вот что спасет отца русской демократии. Кажется, у вас это называется "Симметрическая разность" или "Исключающее ИЛИ"
 :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: ARRY

Оффлайн ARRY

  • Пользователь
  • Сообщений: 223
  • Поблагодарили: 173 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #7 : Январь 25, 2018, 03:13:12 pm »
XOR - вот что спасет отца русской демократии.
Байт
Точно. А я ведь думал над этой задачей. Не хватило самой малости - сообразить, что одинаковые разряды числа при сложении по модулю 2 взаимно уничтожаются.
Если, скажем, в том числе, которое не имеет пары, какой-то разряд равен 1, то во всём данном ряде чисел он будет равен 0 в чётном числе разрядов. А, стало быть, XOR этого разряда равно 0. И наоборот.
Т.е. надо искать XOR всех чисел.
Спасибо, хорошая задача.
Кажется, у вас это называется "Симметрическая разность" или "Исключающее ИЛИ"
А мне больше по душе так, как называется, по-моему, у Клини - strict disjunction (строгая дизъюнкция)

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

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #8 : Январь 25, 2018, 05:48:02 pm »
А я ведь думал над этой задачей.
Энто приятно. А уж думал, никому это все не интересно. Я тоже догадался не сам. А когда увидел - Боже мой! - как же все просто! А наш туповатый взгляд этого не видит! Вот потому-то я положил задачку именно в этот раздел. типа того, что логикам эта операция ближе.
В любом случае, увидеть простоту в зарослях - это польза и для ума, и для здоровья :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 929
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
Re: Найти уникальное множество
« Ответ #9 : Январь 25, 2018, 05:49:39 pm »
Бог создал натуральные числа,
И кто-то добавил - "Он создал их достаточно..." :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?