 |
Олимпиадные задачи, использующие комбинаторные конфигурации
|
|
|
|
Пример 1. На одном острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что к всеобщему удивлению даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции острова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите Островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.
Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4 £ N £ 150). Вам даны списки всех N партий Острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. (Олимпиада стран СНГ, г. Могилев, 1992 г.)
Решение: с теоретической точки зрения, данная задача совпадает с задачей генерации всех подмножеств из множества жителей острова новой демократии. Причем наиболее подходящим кажется первый подход к решению данной задачи, связанный с генераций различных сочетаний, начиная с одного жителя. Для полноты изложения этого подхода, опишем функцию сheck, которую следует применить в данной задаче. Исходные данные следует записать в массив s:array[1..150] of set of 1..150, заполнив каждый из n первых элементов этого массива множеством тех партий, в которых состоит тот или иной житель. Тогда функция проверки сочетания из элементов этого массива примет следующий вид:
function check(var p: list;k:integer): boolean;
var i:integer; ss:set of 1..150;
begin
ss:=[];
for i:=1 to k do ss:=ss+s[p[i]];
check:=(ss =[1.. n ])
end;
|
|
|
Как видно из описания функции, использование типа “множество”, позволяет не только упростить данную программу, но и существенно ускорить ее выполнение, по сравнению с работой с массивами. Однако большая размерность данной задачи не позволяет считать приведенное решение удовлетворительным во всех случаях. Так, уже для n = 100, перебор всех сочетаний из 4-х и менее жителей приводит к рассмотрению около 4-х миллионов вариантов. Для построения кода, пригодного для решения данной задачи при любых входных данных, несколько изменим описание массива s:
s: array[1..150] of
record name,number:integer;
partys: set of 1..150
end;
Здесь поле partys совпадает по смыслу с первоначальным описанием массива s, поле name cоответствует номеру (то есть фактически имени) жителя и первоначально данное поле следует заполнить числами от 1 до n cогласно индексу элемента в массиве записей, и поле number соответствует количеству элементов во множестве из поля partys, то есть имеет смысл сразу подсчитать, в каком количестве партий состоит тот или иной житель. Теперь следует отсортировать массив s по убыванию значений поля number. Верхнюю оценку для числа членов парламента (kmax) подсчитаем, построив приближенное решение данной задачи следующим образом: во-первых, включим в парламент жителя, состоящего в максимальном количестве партий, затем исключим эти партии из остальных множеств и заново найдем в оставшемся массиве элемент с максимальным значением поля number (уже пересчитанного) и включим его в парламент, и так далее, до тех пор, пока сумма значений пересчитанных полей number у жителей, включенных в парламент, не будет равна n. Найденное количество членов парламента и будет kmax.
Теперь следует рассматривать сочетания из (kmax – 1) элемента, затем из (kmax – 2) и т. д. элементов. Если для сочетаний из какого-то рассматриваемого количества элементов k, решение найдено не будет, то это означает, что точным является решение с количеством членов парламента k +1. Так как массив s упорядочен, то, если решение для того или иного значения k существует, то, скорее всего, оно будет найдено при рассмотрении в лексикографическом порядке первых же сочетаний по k элементов. Поэтому временная трудоемкость в переборе возникает, только если решения c данным значением k не существует. В такой ситуации можно воспользоваться следующим “ненаучным” приемом: на поиск решения для каждого k, меньшего, чем kmax отведем фиксированное количество времени, скажем, 2-3 секунды (точнее данное время стоит определить экспериментальным путем). Если за отведенное время решение не найдено, то следует считать полный перебор невозможным и закончить выполнение программы. В любом случае, мы будем иметь какое-либо решение исходной задачи: точное или приближенное, то есть, возможно, содержащее больше членов парламента, чем минимально возможно. Однако, на практике такой подход почти всегда приводит к точному решению, в силу перебора “с предпочтением”, проводимого для каждого k (невозможность проведения полного перебора для какого-либо k на практике соответствует отсутствию решения для данного k).
|
|
|
Пример 2. Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций '+', '-', '*', '/' (целочисленное деление) и скобки таким образом, чтобы значение полученного выражения было равно 100. Можно образовывать многозначные числа из стоящих рядом цифр. Выражение должно быть корректным с точки зрения арифметики. Допустимы лишние скобки, не нарушающие корректности выражения. При вычислениях используется стандартный приоритет операций, число цифр N в номере билета не больше 6. (5-ая Всероссийская олимпиада по информатике, г. Троицк, 1993 г.)
Решение. для построения универсального алгоритма решения данной задачи будем считать слияние двух соседних цифр одной из операций. Тогда между каждой парой соседних цифр может стоять одна из 5 операций. Для N цифр получаем 5 N -1 различных вариантов расстановки операций. Перебирать все варианты расстановки операций удобнее всего с помощью рассмотрения всех чисел в 5-ричной системе счисления, состоящих не более чем из N – 1 цифры, то есть для N = 6 от 00000 до 44444. Для перебора таких чисел необходимо написать процедуру прибавления 1 в 5-ричной системе счисления. Для каждого из вариантов расстановки операций перейдем от исходного массива из N цифр билета, к массиву из К чисел, где K = (N – количество операций слияния цифр в рассматриваемом варианте). Теперь мы должны рассмотреть все перестановки из K – 1 арифметической операции в данном варианте. Каждая перестановка соответствует одному из порядков выполнения арифметических операций. Так, для 4-х чисел, перестановка номеров операций 3, 1, 2 означает, что сначала нужно выполнить арифметическое действие между 3-м и 4-м числом, затем между 1-м и 2-м и затем оставшееся. Если результат выполнения действий данного варианта в порядке, соответствующем текущей перестановке, равен искомому числу 100, то задача решена и можно перейти к печати результата. Для данной задачи возможны и более эффективные решения, но в силу ее небольшой размерности, комбинаторный перебор оказывается вполне приемлемым.
|
|
|
Пример 3. Губернатор одной из областей заключил с фирмой " HerNet " контракт на подключение всех городов области к компьютерной сети. Сеть создается следующим образом: в области устанавливается несколько станций спутниковой связи, и затем от каждого города прокладывается кабель до одной из станций. Технология, используемая компанией требует при увеличении расстояния увеличения толщины кабеля. Таким образом, стоимость кабеля, соединяющего город со станцией, при используемой компанией технологии будет равна kL 2, где L - расстояние от города до станции, а k - некий коэффициент. Вам требуется написать программу, определяющую минимальные затраты компании на установку сети.
Входные данные. Во входном файле записано число n (1 ≤ n ≤ 10) - количество городов в области. Затем идут положительные вещественные числа: k - коэффициент стоимости кабеля и P - стоимость постройки одной станции. Далее следует n пар вещественных чисел, задающих координаты городов на плоскости.
Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i -ое число задает номер станции, к которой будет подключен i -ый город. (Кировский командный турнир по программированию, 2000 г.)
|
|
|
Решение. В силу небольшой размерности мы можем рассмотреть все возможные варианты разбиения городов на группы, подразумевая что для каждой группы будет установлена своя станция, причем оптимальным образом (найти оптимальное местонахождение станции для одной группы городов можно по формуле, аналогичной формуле нахождения центра масс). Затем нужно из всех разбиений выбрать то, для которого общая сумма затрат на установку сети будет минимальной.
Заключение
Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k -элементные подмножества множества, состоящего из n ³ k элементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения n пар открывающихся и закрывающихся скобок).
Большинство указанных конфигураций были подробно рассмотрены в [1-3]. Однако при генерации различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике.
Литература
1. Окулов С.М. Перестановки. “Информатика”, №7, 2000.
2. Окулов С. M. Комбинаторные задачи. “Информатика”, №10, 13, 2000.
3. Усов Б.Б. Комбинаторные задачи. “Информатика”, №39, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
5. Брудно A.Л., Каплан Л.И. Московские олимпиады по программированию. М.: Наука, 1990.
6. Кнут Д. Конкретная математика. Основание информатики. М.: “Мир”, 1998.
7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
8. Андреева Е.В. Еще раз о задачах на полный перебор вариантов. “Информатика”, №45, 2000.
|
|
|
