Логическая операция исключающее или (она же сложение по модулю два) имеет ряд неожиданных применений. Пусть дан массив чисел, в котором все числа кроме одного встречаются дважды, и только одно не имеет пары. Надо придумать алгоритм нахождения этого числа. Если кто-то догадался, как можно просто это сделать, высказывайте свои мнения.
Сообщение отредактировал IQFun - Сб, 29.01.22, 19:46
Переводим все числа в двоичную систему, складываем побитно все возможные пары в Z/2Z, если при сложении получается 0 то эти числа одинаковы их отбрасываем. Продолжаем пока не наткнемся на число которое при таком сложении с остальными не даёт 0, это и будет искомое число в данном массиве.
Сообщение отредактировал Фигаро - Чт, 03.02.22, 20:59
Ответ: надо просто поксорить все элементы массива, в результате получим искомое число. Потому что пары одинаковых чисел дадут в результате нули. Даже опытные программисты могут здесь предложить хеш-таблицу и прочие штуки для ускорения расчётов, а ларчик открывается просто с пом. xor.
IQFun, теперь я понял, вы не только ответы не можете понять, вы не понимаете даже то что пишите сами. Вы предложили внимательней почитать, так давайте это сделаем: Вот ваши слова:
ЦитатаIQFun ()
надо просто поксорить все элементы массива,
После чего пишите противоречащие этому слова:
ЦитатаIQFun ()
(В нём не надо складывать всевозможные пары.
Вы вменяемый вообще? xor , или как вы выразились «поксорить» — это и есть сложение в кольце вычетов по модолю два. Постарайтесь хотя бы со второй попытки ответить на тот же вопрос: «чем отличается то что написал я от того что написали вы?» И пожалуйста внятно и по существу.
Сообщение отредактировал Фигаро - Чт, 03.02.22, 20:59
Фигаро пишет "все возможные пары", IQFun, пишет "все элементы массива". Вы оба пишете разными словами об одном и том же? Предлагаю писать на родном языке: языке программирования, раз так трудно найти общий. Хотела поделиться опытом по поводу ИИ. Директор молзавода - молодой, продвинутый чел, имея автопарк и желая сократить расходы(читай уволить некоторых водителей), покупает крутую программу "Логистика". Однако, программа выдавая оптимальные маршруты доставки молока в торговые точки, никак не укладывается при имеющемся количестве персонала в необходимое время работы. И машин, и людей не достаточно! Мало вас, математиков, видимо проблема в этом)
Добавлено (03.02.22, 19:32) --------------------------------------------- P.s. я никак не могу понять - если сравнивать все возможные пары, зачем не использовать обычное математические равно, или вычитание с проверкой на ноль...а побитно все числа складывать попарно по модулю 2? Как этот xor работает с массивом? Алгоритм хоть бы опишите, пожалуйста
Сообщение отредактировал Vita - Чт, 03.02.22, 19:51
Фигаро пишет "все возможные пары", IQFun, пишет "все элементы массива". Вы оба пишете разными словами об одном и том же?
Да Вита, об одном и том же! Но вот IQFun не понимает этого, более того, по видимому он не понимает и того что пишет сам.
ЦитатаVita ()
Как этот xor работает с массивом?
Я конечно постараюсь доступно разъяснить о том что написал я и о том что это за xor, но не уверен что это получится, т.к. не знаю что вам знакомо а что нет.
Вот давайте все целые числа будем делить на 2, и смотреть какие остатки при этом получаются.Не трудно понять что у нас будут получаться в остатке либо 0, либо 1. Получается что все числа можно рассортировать на два множества, — множество чисел которые дают ноль в остатке при делении на 2, и множество чисел которые дают единицу в остатке при делении на два. Числа входящие в эти множества называют вычетами по модулю два, а сами эти множества обозначают следующим образом [0]2, [1]2, и называют классами вычетов по модулю 2.В арифметике остатков, вместо того чтобы складывать (или например умножать) числа из этих классов, можно просто сложить остатки.Например вместо того чтобы складывать 13 и 17 и искать какой остаток даёт сумма этих чисел при делении на два, мы просто можем сложить остатки.Число 13 даёт остаток 1 при делении на 2, и число 17 даёт остаток 1 при делении на два, значит сумма этих чисел даёт остаток 1+1=2, т.е. 0, т.к. 2 делится на 2 без остатка.Можем даже таблицу сложения соответствующую сделать:
Вот так лаконично выглядит таблица сложения всех целых чисел по модолю два.Можно так же и умножать эти остатки.В математике если над некими объектами можно осуществлять операции похожие на сложения (и обратимую к ней операцию) а так же операцию похожую на умножение, то говорят что относительно данных операций изучаемые элементы образуют конечное кольцо.Кольцо вычетов по модулю два обозначается Z/2Z.(На самом деле здесь выполняются все аксиомы поля, поэтому я бы мог обозначить это как GF(2), но я подумал IQFun не поймёт ничего, но в итоге он всё равно не понял).
Теперь думаю более ясно что написано в моём сообщении.
Теперь разберёмся с функцией xor.XOR, это и есть функция сложения по модулю два.Это функция встроена практически в любой язык программирования.В логике её называют «исключающее или» собственно от сюда и название функции.Сравните табличку сложения двух элементов по модулю 2 данную вверху и таблицу истинности для «исключающего или» так же для двух операндов:
Эта операция побитовая, т.е. она выполняется для каждого разряда.Чтобы вы не ввели в компьютер он каждый элемент кодирует в двоичный код.
Если вы введете некий массив чисел то компьютер будет оперировать ими в двоичной системе счисления.Пусть у нас есть два операнда например
001110001
и
001110001
Применяя к этим операндам функцию xor, — компьютер будет поразрядно складывать их (смотрите табличку сложения) , то есть произойдёт следующее:
Как видим если два операнда равны, то в итоге получится ноль, всегда, а если не равны, то ноля не получится ни при каких условиях.
Так вот если мы будем применять к массиву чисел функцию xor, то будут складываться все числа попарно, и в итоге мы выявим те которые в массиве присутствуют дважды и те которые в единственном экземпляре.
Теперь давайте перечитаем то что написал я:
ЦитатаФигаро ()
Переводим все числа в двоичную систему, складываем побитно все возможные пары в Z/2Z, если при сложении получается 0 то эти числа одинаковы их отбрасываем. Продолжаем пока не наткнемся на число которое при таком сложении с остальными не даёт 0, это и будет искомое число в данном массиве.
и то что написал IQFun:
ЦитатаIQFun ()
Ответ: надо просто поксорить все элементы массива, в результате получим искомое число. Потому что пары одинаковых чисел дадут в результате нули.
Как видим из всего выше описанного, разницы здесь нет никакой абсолютно, оба поста об одном и том же, но IQFun, с упорством достойным лучшего применения этого в упор не замечает.
Сообщение отредактировал Фигаро - Чт, 03.02.22, 21:21
------------------------------------------ P.s. я никак не могу понять - если сравнивать все возможные пары, зачем не использовать обычное математические равно, или вычитание с проверкой на ноль...а побитно все числа складывать попарно по модулю 2? Как этот xor работает с массивом? Алгоритм хоть бы опишите, пожалуйста
Я понимаю таблицу истинности, понимаю как из логических элементов собрать схему исключающее ИЛИ, я не понимаю - ЗАЧЕМ, чем это упростит задачу попарного перебора и сравнения?
Сообщение отредактировал Vita - Чт, 03.02.22, 21:36
