|
Главная | Правила | Регистрация | Дневники | Справка | Пользователи | Календарь | Поиск | Сообщения за день | Все разделы прочитаны |
|
Опции темы | Опции просмотра |
26.06.2015, 20:08 | #1 (permalink) |
Новичок
Регистрация: 26.06.2015
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Программирование. Задача о сторожах-2
Моя задача: «В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime]. Для заданного расписания стражи требуется: (а) проверить, в любой ли момент в галерее находится не менее двух сторожей. Если условие (а) не выполнено, то: (б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей). (в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а)). (г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства. (д) Если это возможно, то составить расписание с наименьшим числом сдвигов. ВХОДНЫЕ ДАННЫЕ: (Все моменты времени задаются в целых минутах.) EndTime - момент окончания стражи, т.е. охраняется отрезок времени [0, EndTime]. N -число сторожей. T1[i], T2[i], i=1,..N - моменты начала и окончания дежурства i-го сторожа. Length - длительность дежурства каждого дополнительного сторожа. ВЫХОДНЫЕ ДАННЫЕ: (1) Ответ на пункт (а) в форме да/нет. (2) При ответе “нет” на п. (а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1). (3) Число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа. (4) Ответ на пункт (г) в форме да/нет. Если “да”, то номера сторожей, смена которых сдвигается, и значения сдвигов. (5) В ответ на пункт (д): наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов. ПРИМЕЧАНИЕ Программа должна допускать независимое тестирование пунктов (в), (г), (д).”» Собственно, как ответить на пункты (а) и (б) я понимаю – пройтись в цикле по каждой минуте, считая количество сторожей, как предлагается в указанной выше теме, или еще можно для всех моментов начала/окончания дежурства (сначала создать из них массив и отсортировать его по возрастанию) получить ряд чисел, указывающих на то, как меняется количество стражей, например, +1, -1 (может быть и несколько), тогда суммируя эти числа можно будет получить количества стражей в каждый момент сдачи/приема дежурства и по ним найти интервалы с недостаточной охраной. Я буду очень благодарна, если кто-нибудь поможет мне с пунктами (в), (г) и (д). Что делать с пунктом (в) тоже более-менее понятно из единственного существующего пояснения к этой задаче: “…Увеличение количества сторожей осуществляется последовательно. Вначале добавляются сторожа в интервалы времени с недостаточной охраной и отстоящие друг от друга на время, большее времени дежурства сторожей. После этого вновь выполняется сортировка и осуществляется поиск интервалов времени с недостаточной охраной. Если они есть, то процесс продолжается, и так до тех пор, пока в любой момент времени в галерее не будут находиться не менее двух сторожей.” Правильно ли я понимаю, что на каждом шаге мы выбираем все интервалы, на которых 0 или 1 сторож (те, где 0, и те, где 1, рассматриваем отдельно) и время между которыми меньше заданного времени дежурства каждого доп. сторожа (пока возможно, на последнем шаге выбираем все оставшиеся интервалы с недостаточной охраной вне зависимости от времени между ними), и заполняем их до отказа, т.е. для тех, на которых 0, добавляем сразу двух? И если да, то можно ли как-то теоретически обосновать, что при таком подходе количество доп. сторожей будет минимальным? Как делать пункты (г) и (д) я совсем не понимаю…Единственная зацепка в том, что во всех источниках, где встречается эта задача, она находится в разделе «графы». В одной книге перед ней даны описания алгоритмов расстановки пометок при поиске максимального потока и алгоритма Дейкстры, но я не представляю, к чему они тут. Нужно ли в этих пунктах использовать эти или, может быть, какие-то другие алгоритмы на графах, и если да, то какие и как? |
26.06.2015, 20:08 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Содержательные ответы вы можете найти в похожих темах Программирование на C# Задача на языке С++. Программирование с помощью подпрограмм |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
Опции темы | |
Опции просмотра | |
|
|