|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 18 Apr 2002 10:01:31
To : Max Alekseyev
Subject : задача про xor
--------------------------------------------------------------------------------
Wed Apr 17 2002 18:53, Max Alekseyev wrote to All:
MA> Есть набор чисел S, нужно найти базое число (или просто "базу") и
MA> минимальный набор масок M такой, что каждое число из S есть XOR базы и
MA> каких-то масок из M?
MA> Пример: для чисел 0x61..0x7A (представляющие ASCII коды букв a..z) в
MA> качестве базы можно взять 0x60 и положить M = { 0x01, 0x02, 0x04, 0x08,
MA> 0x10 }.
Легко заметить, что существует множество эквивалентных решений, относительно
которых задачу можно считать в некотором смфсле линейной. Так, если существует
решение B,M0,M1..Mn, то и B,M1..Mn,K тоже будет решением тогда и только тогда,
когда К является линейной (в смысле XOR) комбинацией из M0 и любого количества
Mi, например K = M0 XOR M2 XOR M5.
Следовательно, если в наборе S присутствуют два числа, отличающиеся только
одним битом, обязательно найдется решение, в котором одно из M равно тому
самому биту.
Hапример, если в S имеются числа 0х68 и 0х69, хотя бы одно из эквивалентных (и
минимальных ! ) решений содержит M0=0х01.
Более того, если в том же S присуствует число 0х6А (или 0х6В), то можно
утверждать, что М1=0х02.
По поводу вышеприведенного набора (0х61..0х7А) : выделяем "вектор" :
- "основа" (может быть принята в качестве базы В) - 0х68,
- отличающиеся от "основы" одним битом - 0х69, 0х6А, 0х6С, 0х60, 0х78,
- убеждаемся, что данный (минимавльный) вектор покрывает все числа из S.
Таким образом, приведенный (МА) выше вектор М является минимальным, точнее,
одним из множества эквивалентных минимальных, любое другое из которых может
быть получено из этого операцией "линейной комбинации" элементов, приведенной
мной в начале рассуждений.
MA> Частная проблема: можно ли для S = { 0x61..0x7A, 0x5F } найти базу и
MA> набор из 5 масок?!
Строим тот же вектор, приняв за основу опять-же 0х68. Видим, что вектор из
пяти масок (обязательных к применению) не покрывает числа 0х5F. Следовательно,
требуется введение шестой маски, и ответ на вопрос - нет.
Писано "с ходу" и не претендует на строгую доказуемость. Буду рад увидеть
опровержение.
С уважением
Сергей
...А за базар Солодов отвечать будет ? (с) реклама
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
задача про xor 
