|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 19 Apr 2002 17:08:56
To : Max Alekseyev
Subject : задача про xor
--------------------------------------------------------------------------------
Thu Apr 18 2002 03:33, Max Alekseyev wrote to Sergey Kabikov:
[skip]
MA> Согласен, что базы 0x60 ... 0х7F все эквивалентны между собой. Hо есть же
MA> другие...
[skip]
MA> Ты доказал, что для любой базы из набора 0x60...0х7F не существует
MA> набора из пяти масок, покрывающего данное S.
А никакая другая база не даст решения из 5 масок даже для простого набора
0x61..0x7A ! Доказываю.
Выберем произвольную базу ВВ. Ее можно представить в виде ВВ = В XOR MM, где В
- одна из известных оптимальных баз (чисел в диапазоне 0x60...0х7F), ММ -
число, содержащее только биты 0х80б 0х40 и 0х20.
Для решения задачи на заданной базе ВВ одна или более масок должны содержать
бит(-ы), входящие в ММ. Разумеется, что для получения любого числа К из набора
0x60...0х7F по формуле
К = BB XOR Mi ... XOR Mj
число входящих в произведение масок, содержащих бит(-ы) из ММ, должно быть
нечетным. А это сужает количество К, которые можно получить подобным способом,
ровно вдвое, т.е. до 16 комбинаций, в то время как нужно-то 26.
С уважением
Сергей
...Всаднику без головы требуется сферический конь
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
