Иногда в тексте условия задачи указано максимальное время работы программы на одном тесте. Поэтому писать программу, которая будет работать при каких-либо входных данных дольше этого времени, смысла нет. Если же выбранный алгоритм в отведенное для работы программы время не укладывается, то зачастую помогает прием, называемый — отсечение по времени. Применяется он в основном в задачах, решение которых производится с помощью перебора вариантов. Пусть в условии задачи требуется найти любой допустимый или даже оптимальный вариант, а при отсутствии допустимого варианта выдать сообщение, что решение отсутствует. Тогда работу программы следует организовать так, чтобы по истечении отведенного на ее выполнение времени выполнение программы заканчивалась и печаталось лучшее из рассмотренных к этому моменту решений или сообщение, об отсутствии решения. Если перебор в такой программе организовать “с предпочтением”, то есть сначала рассматривать наиболее вероятные варианты, то такая программа может работать правильно почти на всех входных данных, несмотря на возможную неэффективность заложенного в нее алгоритма. Так как правильно организованный перебор зачастую быстро находит решение задачи, а рассмотрение остальных вариантов необходимо в нем лишь для того, чтобы доказать оптимальность уже найденного. Поэтому, если за отведенное время не найден никакой вариант, то будем считать, что решение в задаче отсутствует (конечно, это не всегда оказывается справедливым), а если какой-то вариант найден, но перебор еще не закончен, то опять же можно надеяться, что этот вариант и есть искомый. В любом случае такая программа всегда результативно заканчивает свою заботу за время ее тестирования и баллы, полученные за нее могут быть весьма высокими (иногда такая программ получает полный балл за решение задачи).
Осталось показать, как программно реализовать описанный прием отсечения рассматриваемых вариантов по времени:
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 секунды), для того, чтобы успеть вывести результат.
|
Главная
Каталог файлов
