Иногда в тексте условия задачи указано максимальное время работы программы на одном тесте. Поэтому писать программу, которая будет работать при каких-либо входных данных дольше этого времени, смысла нет. Если же выбранный алгоритм в отведенное для работы программы время не укладывается, то зачастую помогает прием, называемый — отсечение по времени. Применяется он в основном в задачах, решение которых производится с помощью перебора вариантов. Пусть в условии задачи требуется найти любой допустимый или даже оптимальный вариант, а при отсутствии допустимого варианта выдать сообщение, что решение отсутствует. Тогда работу программы следует организовать так, чтобы по истечении отведенного на ее выполнение времени выполнение программы заканчивалась и печаталось лучшее из рассмотренных к этому моменту решений или сообщение, об отсутствии решения. Если перебор в такой программе организовать “с предпочтением”, то есть сначала рассматривать наиболее вероятные варианты, то такая программа может работать правильно почти на всех входных данных, несмотря на возможную неэффективность заложенного в нее алгоритма. Так как правильно организованный перебор зачастую быстро находит решение задачи, а рассмотрение остальных вариантов необходимо в нем лишь для того, чтобы доказать оптимальность уже найденного. Поэтому, если за отведенное время не найден никакой вариант, то будем считать, что решение в задаче отсутствует (конечно, это не всегда оказывается справедливым), а если какой-то вариант найден, но перебор еще не закончен, то опять же можно надеяться, что этот вариант и есть искомый. В любом случае такая программа всегда результативно заканчивает свою заботу за время ее тестирования и баллы, полученные за нее могут быть весьма высокими (иногда такая программ получает полный балл за решение задачи). Осталось показать, как программно реализовать описанный прием отсечения рассматриваемых вариантов по времени:
const timetest=10;{время тестирования программы}
var timer:longint absolute $40:$6c;
timeold:longint;
begin
timeold:=timer;
while true do
if timer-timeold>18.2*(timetest-0.5) then
begin
…{запись текущего результата в файл
или сообщение об отсутствии решения}
halt
end else {собственно работа программы}
end.
Данная программа использует тот факт, что к значению четырехбайтовой целой переменной, расположенной по абсолютному адресу $40:$6С, раз в 1/18.2 секунды аппаратно прибавляется единица. Поэтому, если мы опишем в нашей программе переменную, привязав ее к этому адресу, то легко сможем определить время работы программы. А именно, запомнив в самом начале программы значение этой переменной (в нашем примере это оператор timeold:=timer), в процессе работы определить время выполнения в секундах можно по формуле (timer timeold)/18.2. Поэтому, если время тестирования известно, то прерывать поиск решения следует за некоторое время до его окончания (в нашем примере это 0,5 секунды), для того, чтобы успеть вывести результат.
Опубликовал Kest
February 22 2010 21:17:42 ·
0 Комментариев ·
11863 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
