Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Входные данные. Во входном файле записано число n (1 ≤ n ≤ 10) - количество городов в области. Затем идут положительные вещественные числа: k - коэффициент стоимости кабеля и P - стоимость постройки одной станции. Далее следует n пар вещественных чисел, задающих координаты городов на плоскости.

Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i-ое число задает номер станции, к которой будет подключен i-ый город. (Кировский командный турнир по программированию, 2000 г.)

Решение. В силу небольшой размерности мы можем рассмотреть все возможные варианты разбиения городов на группы, подразумевая что для каждой группы будет установлена своя станция, причем оптимальным образом (найти оптимальное местонахождение станции для одной группы городов можно по формуле, аналогичной формуле нахождения центра масс). Затем нужно из всех разбиений выбрать то, для которого общая сумма затрат на установку сети будет минимальной.

Заключение

Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из nk элементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения 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.

Характеристики

Список файлов реферата