Множество
Множество – это совокупность элементов с обычными теоретико-множественными операциями: проверка вхождения элемента (принадлежности) данному множеству, пересечения, объединения, вычитания множеств и т. п.
Рассмотрим два основных подхода к представлению множеств: в виде таблицы и в виде характеристического вектора.
1. Таблица содержит описание каждого элемента, принадлежащего множеству. Операции над элементом и множеством - проверка принадлежности элемента, его присоединение или удаление из множества - соответствуют поиску, включению и исключению в таблице. Объединение, пересечение и вычитание множеств удобно реализовать слиянием упорядоченных таблиц.
2. Для хранения подмножеств некоторого базового множества удобен характеристический вектор - битовый вектор длиной N, i-й разряд которого соответствует i-му элементу базового множества и равен 1, если этот элемент принадлежит хранимому (под)множеству, и 0, если не принадлежит. Характеристический вектор позволяет представлять 2N возможных подмножеств базового множества c мощностью (количеством элементов) N.
Операции над множествами реализуются в этом случае очень быстрыми поразрядными (битовыми) операциями: объединение - дизъюнкцией (ИЛИ, в языке Си обозначается одной вертикальной чертой |), пересечение - конъюнкцией (И, в Си &), вычитание из базового множества (дополнение) - инверсией (отрицанием, в Си ~). Эти операции во многих случаях выполняются одной машинной командой. Таким же образом в множество легко включать и исключать элементы, представляя их как одноэлементные множества.
Характеристический вектор эффективен для "плотных" подмножеств базового множества при наличии простого соотношения между элементом и его номером i. Этот метод обычно применяется для реализации множеств, имеющихся в языке Pascal. Их мощность не превышает 256.
Пример 3.24. Дни недели. Для хранения подмножества дней недели достаточно одного байта: Пусть, например, бит с номером 0 представляет понедельник, бит 1 - вторник,..., бит 6 - воскресенье. Бит 7 остается неиспользованным и будет равен нулю. На рис. 3.16 показаны несколько примеров представления множеств дней недели битовым вектором и операций над ними. Эти множества реализуются следующим фрагментом С-программы.
typedef char dni; /* Тип - множество дней недели: 0..6 */
dni rab_dni = 0x1F, /* Рабочие дни - биты: 0001 1111 */
/* Номера дней (битов) 7654 3210 */
vyh_dni = 0x60, /* Выходные дни - биты: 0110 0000 */
zan, dezh, svob; /* Дни занятий, дежурств, свободные */
...
svob = ~(zan | dezh) & 0x7F; /* Свободные дни */
if (svob & vih_dni) ... /* Есть свободные выходные дни? */
| Дни недели:
| -всп чсвп
|
| Номера битов:
| 7654 3210
| Дни занятий: {пн,ср,пт}
| zan
| 0001 0101
| Дни дежурств: {ср,сб}
| dezh
| 0010 0100
| Занятые дни
| zan | dezh
| 0011 0101
| Незанятые дни
| ~(zan | dezh)
| 1100 1010
| Маска использованных битов (в 16-й системе)
| 0x7F
| 0111 1111
| Свободные дни:
| svob = ~(zan | dezh)&0x7F
| 0100 1010
| Выходные дни:
| vyh_dni = 0x60
| 0110 0000
| Есть свободные выходные дни
| (svob & vyh_dni)
¹ 0
| 0100 0000
¹ 0
|
Рис. 3.16. Множества дней недели
|
Пример 3.25. Простые числа < 1000000. Задача: проверить, является ли заданное целое X < 1000000 простым числом (делится только на 1 и на себя).
Решение 1. Деление на все нечетные числа, не превышающие корень квадратный из X (до 500 делений - медленно!)
Решение 2. Хранить таблицу простых чисел меньших 1000000 в виде упорядоченного по возрастанию вектора из 78498 чисел по 4 байта, всего 313992 байта. Поиск требует до log 2 78498 = 17 делений пополам. Много памяти!
Решение 3. Хранить таблицу простых чисел меньших 1000000 как подмножество нечетных чисел в виде характеристического вектора из 500000 бит = 62500 байт (в 5 раз меньше, чем в решении 2!).
Используем массив tpr из 31250 двухбайтовых чисел без знака типа unsigned. Тогда j-й бит i-го элемента массива tpr соответствует нечетному числу X = 2*(16*i+j)+3.
Обозначим: y = 16*i+j. Тогда при данном X найдем:
y = (X-3)/2, i = y/16, j = y%16.
Отсюда получается подпрограмма проверки простоты числа:
/* Таблица: j-й бит tpr[i] = Число 2*(16*i+j)+3 - простое */
unsigned tpr[31250] =
{ 0x65B7, /* 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 */
/* 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 */
...
};
/* Таблица степеней 2: st2[i] = 2**i (I = 0..15) */
unsigned st2[16] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024,
2048, 4096, 8192, 16384, 32768};
...
/* Функция: X - простое число (X < 1000000) */
int prostoe_chislo (long X) {
if (X == 1) return 0; /* 1 не считают простым числом */
if (X%2) { X = (X - 3) / 2; return tpr[X / 16] & st2[X % 16]; }
return 0;
}
Быстрее и проще заменить в операторе return деление и степень сдвигом: return tpr[X >> 4] & (1 << (X % 16)).
Тогда не нужна таблица степеней 2.
Еще быстрее вычислять остаток от деления на 16 выделением четырех младших бит: X%16 заменить на X & 0xF.
Решение 4. Компромисс между решениями 1 и 3: для проверки простоты выполнять деление X на простые числа, не превышающие квадратного корня из X, который меньше 1000. Для этого хранить таблицу из 168 двухбайтовых простых чисел, меньших 1000. Требует до 168 делений.
Дата добавления: 2015-09-27 | Просмотры: 459 | Нарушение авторских прав
|