Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 26.06.2015, 20:08   #1 (permalink)
Anna_K
Новичок
 
Регистрация: 26.06.2015
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
Exclamation Программирование. Задача о сторожах-2

Здравствуйте. В поисках решения своей задачи наткнулась на ваш форум – нашла решение другой задачи, похожей на часть моей -tehnari.ru/f41/t58807 , но целиком решить свою по-прежнему не могу, поэтому обращаюсь к вам за помощью.

Моя задача:

«В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т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, добавляем сразу двух? И если да, то можно ли как-то теоретически обосновать, что при таком подходе количество доп. сторожей будет минимальным?

Как делать пункты (г) и (д) я совсем не понимаю…Единственная зацепка в том, что во всех источниках, где встречается эта задача, она находится в разделе «графы». В одной книге перед ней даны описания алгоритмов расстановки пометок при поиске максимального потока и алгоритма Дейкстры, но я не представляю, к чему они тут. Нужно ли в этих пунктах использовать эти или, может быть, какие-то другие алгоритмы на графах, и если да, то какие и как?
Anna_K вне форума   Ответить с цитированием

Старый 26.06.2015, 20:08
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Содержательные ответы вы можете найти в похожих темах

Программирование на C#
Задача на языке С++. Программирование с помощью подпрограмм

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 21:07.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.