MAXimal | |
добавлено: 16 Jan 2009 0:58 Содержание [скрыть] Перебор всех подмасок данной маскиПеребор подмасок фиксированной маскиДана битовая маска Сразу рассмотрим реализацию этого алгоритма, основанную на трюках с битовыми операциями: int s = m; while (s > 0) { ... можно использовать s ... s = (s-1) & m; } или, используя более компактный оператор for (int s=m; s; s=(s-1)&m) ... можно использовать s ... Единственное исключение для обоих вариантов кода — подмаска, равная нулю, обработана не будет. Её обработку придётся выносить из цикла, или использовать менее изящную конструкцию, например: for (int s=m; ; s=(s-1)&m) { ... можно использовать s ... if (s==0) break; } Разберём, почему приведённый выше код действительно находит все подмаски данной маски, причём без повторений, за O (их количества), и в порядке убывания. Пусть у нас есть текущая подмаска Таким образом, этот алгоритм генерирует все подмаски данной маски в порядке строгого убывания, затрачивая на каждый переход по две элементарные операции. Особо рассмотрим момент, когда Перебор всех масок с их подмасками. Оценка Во многих задачах, особенно на динамическое программирование по маскам, требуется перебирать все маски, и для каждой маски - все подмаски: for (int m=0; m<(1<<n); ++m) for (int s=m; s; s=(s-1)&m) ... использование s и m ... Докажем, что внутренний цикл суммарно выполнит Доказательство: 1 способ. Рассмотрим Доказательство: 2 способ. Заметим, что если маска Посчитаем эту сумму. Для этого заметим, что она есть не что иное, как разложение в бином Ньютона выражения
|