ДП на подмножествах — различия между версиями
(→Битовые маски) |
(→Как работать с множествами, с помощью масок?) |
||
| Строка 8: | Строка 8: | ||
Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х. | Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х. | ||
===Как работать с множествами, с помощью масок?=== | ===Как работать с множествами, с помощью масок?=== | ||
| − | Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:< | + | <p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p> |
'''bool''' elem_in_subset ('''unsigned int''' mask, '''int''' pos) { | '''bool''' elem_in_subset ('''unsigned int''' mask, '''int''' pos) { | ||
return (mask >> pos) & 1; | return (mask >> pos) & 1; | ||
} | } | ||
| − | + | Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. | |
Версия 19:17, 30 апреля 2020
Содержание
Описание проблемы
Пусть у нас есть некоторое множесьво N = {0, 1, 2, ..., n - 1}, n ≤ 30
Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".
Битовые маски
Что такое битовые маски?
Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае.
Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 10112 = 1110. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа unsigned int, то сможем закодировать любое подмножество, размер которого не больше 32х.
Как работать с множествами, с помощью масок?
Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:
bool elem_in_subset (unsigned int mask, int pos) {
return (mask >> pos) & 1;
}
Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция __builtin_popcount (mask), которая возвращает количество единичных битов в двоичном представлении mask.
