|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 17 Apr 2002 23:31:06
To : Sergey Kabikov
Subject : задача про xor
--------------------------------------------------------------------------------
Replying to a message of Sergey Kabikov to Max Alekseyev:
MA>> Есть набор чисел S, нужно найти базое число (или просто "базу") и
MA>> минимальный набор масок M такой, что каждое число из S есть XOR базы
MA>> и каких-то масок из M? Пример: для чисел 0x61..0x7A (представляющие
MA>> ASCII коды букв a..z) в качестве базы можно взять 0x60 и положить M
MA>> = { 0x01, 0x02, 0x04, 0x08, 0x10 }.
SK> Легко заметить, что существует множество эквивалентных решений,
SK> относительно которых задачу можно считать в некотором смфсле
SK> линейной. Так, если существует решение B,M0,M1..Mn, то и B,M1..Mn,K
SK> тоже будет решением тогда и только тогда, когда К является линейной
SK> (в смысле XOR) комбинацией из M0 и любого количества Mi, например K =
SK> M0 XOR M2 XOR M5. Следовательно, если в наборе S присутствуют два
SK> числа, отличающиеся только одним битом, обязательно найдется решение,
SK> в котором одно из M равно тому самому биту.
Согласен.
SK> Hапример, если в S имеются числа 0х68 и 0х69, хотя бы одно из
SK> эквивалентных (и минимальных !) решений содержит M0=0х01. Более того,
SK> если в том же S присуствует число 0х6А (или 0х6В), то можно утверждать,
SK> что М1=0х02.
Если пойти в твоих рассуждениях дальше, то можно утверждать, что существует
минимальный набор, который содержит _все_ однобитовые маски, получаемые как xor
двух элементов из S.
SK> По поводу вышеприведенного набора (0х61..0х7А) : выделяем "вектор" :
SK> - "основа" (может быть принята в качестве базы В) - 0х68,
SK> - отличающиеся от "основы" одним битом - 0х69, 0х6А, 0х6С, 0х60, 0х78,
SK> - убеждаемся, что данный (минимавльный) вектор покрывает все числа из
SK> S.
SK> Таким образом, приведенный (МА) выше вектор М является
SK> минимальным, точнее, одним из множества эквивалентных минимальных,
Это сразу следует из неравенства |M|>=log(|S|), которое можно усилить до
|M|>=ceil(log(|S|)).
Так как |S|=26, то ceil(log(|S|))=5.
MA>> Частная проблема: можно ли для S = { 0x61..0x7A, 0x5F } найти базу и
MA>> набор из 5 масок?!
SK> Строим тот же вектор, приняв за основу опять-же 0х68.
Почему? Может быть, с другой базой нам повезёт больше?
SK> Видим, что
SK> вектор из пяти масок (обязательных к применению) не покрывает числа
SK> 0х5F. Следовательно, требуется введение шестой маски, и ответ на
SK> вопрос - нет.
Я согласен, что ответ "нет", но вот как показать это не перебирая всевозможные
базы?
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
