N — к-о чисел, неч. и из-но, что среди вв-х чисел кажд. имеет ровно одно, равн. себе, а одно число — нет. Н-е это число?

Fearless, 123 просмотра

-1

Пусть N — количество чисел, нечетно и известно, что среди вводимых чисел каждое имеет ровно одно, равное себе, а одно число — нет. Найдите это число?

Примечание:
Причем хранение последовательности из N чисел, не требуется вообще, следовательно ее длина может быть очень велика!

Примечание:
Условие задачи полное. Надо написать алгоритм.

Примечание:
Алгоритм обещает быть достаточно сложным так, что не спешите с ответами и оценками.

Примечание:
Я не знаю ответ. Я знаю, что как-то через XOR можно сделать.

Примечание:
Так любой идиот может, а вот если сделать это за O(N) сравнений это уже другое дело...

Ответы:

AC-130U Spectre

Ну какие числа то? Так просто задачу не решишь.

rinat8032

Условие задачи неполное, да и корректным не является.
После дополнения #2 задача, наконец, обрела смысл.

adasiko

Да ну тебя, в теге Xor написал - так не интересно
"Алгоритм обещает быть достаточно сложным" ничего сложного не вижу
А смысл задавать вопрос, на который ты знаешь ответ?

Ant1973

Хоть убей, не понимаю смысла слов "известно, что среди вводимых чисел каждое имеет ровно одно, равное себе". Поясните, пожалуйста.

mpiz

Динамические списки.
Берём число очередное, если такого числа в списке нет, то добавляем число в список, если такое число в списке есть то удаляем его из списка. В итоге после ввода всех чисел в списке останется только одно число, которое нам и будет нужно.

11111000

Берём первое число в массиве ищем его до конца массива, если находим, переходим на следующее число и так до конца массива. Первое число дубликат которого не найден, и есть то число которое мы нищим, если я правильно понял.

Теперь применимы все классические алгоритмы, где веса у ребер.

баян в кубе: мы знаем сумму всех чисел (как арифметическая прогрессия, хотя в условии что-то мало сказано, но я подразумеваю).
просуммируем все числа на входе, вычтем и получим результат

Trubor

ребят, вы чего, задача-то тривиальная - дело в том, что операция XOR - коммутативна и ассоциативна. a ^ b = b^a, (a^b)^c=a^(b^c), 0 - нулевой элемент в этой полугруппе
А из этого следует, что надо просто выполнять последовательно XOR со всеми элементами последовательности.
если N=2*n+1, то получится 0^0^.....^0^x - где нулей n штук. т.е просто равно x

13 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.