АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Множество

Множество – это совокупность элементов с обычными теоретико-множественными операциями: проверка вхождения элемента (принадлежности) данному множеству, пересечения, объединения, вычитания множеств и т. п.

Рассмотрим два основных подхода к представлению множеств: в виде таблицы и в виде характеристического вектора.

1. Таблица содержит описание каждого элемента, принадлежащего множеству. Операции над элементом и множеством - проверка принадлежности элемента, его присоединение или удаление из множества - соответствуют поиску, включению и исключению в таблице. Объединение, пересечение и вычитание множеств удобно реализовать слиянием упорядоченных таблиц.

2. Для хранения подмножеств некоторого базового множества удобен характеристический вектор - битовый вектор длиной N, i-й разряд которого соответствует i-му элементу базового множества и равен 1, если этот элемент принадлежит хранимому (под)множеству, и 0, если не принадлежит. Характеристический вектор позволяет представлять 2^N возможных подмножеств базового множества 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) ... /* Есть свободные выходные дни? */

Пример 3.25. Простые числа < 1000000. Задача: проверить, является ли заданное целое X < 1000000 простым числом (делится только на 1 и на себя).

Решение 1. Деление на все нечетные числа, не превышающие корень квадратный из X (до 500 делений - медленно!)

Решение 2. Хранить таблицу простых чисел меньших 1000000 в виде упорядоченного по возрастанию вектора из 78498 чисел по 4 байта, всего 313992 байта. Поиск требует до log ₂ 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 | Просмотры: 429 | Нарушение авторских прав