ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ
Советы, приёмы и хитрости олимпиадного программирования.
Олимп. прогр. (300тг = 2у.е.)В данном разделе Вы можете приобрести
советы,
приёмы,
методы,
хитрости олимпиадного
программирования.
Советы будут полезны начинающим программистам, так как содержат примеры, редко описываемые в литературе, но часто встречающиеся в практике.
Хитрости пригодятся программистам, решающим олимпиадные задачи, т.к. помогают сократить код программ, упростить и ускорить их решение.
- Олимпиадное программирование. Перечень рассматриваемых тем.
|
|
Олимпиадное программирование - купить посредством SMS
- Порядок решения олимпиадных задач (пример)
1. В самом начале тура полезно набить приведенную ниже универсальную заготовку для решения олимпиадной задачи (она представляет из себя работающую программу!!!), особое внимание следует обратить на директивы компилятора, приведенные в образце. С помощью команды <Ctrl+O O> текущие директивы компилятора можно записать в начале текста программы и исправить те из них, которые не соответствуют приведенным.
{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T+,V+,X+,Y+}
{$M 65520,0,655360}
var
i,j,k:longint;
procedure readdata;
begin
assign(input,'');
reset(input);
end;
procedure outdata;
begin
assign(output,'');
rewrite(output);
close(output)
end;
procedure initial;
begin
fillchar(i,?,0);
end;
procedure run;
begin
end;
begin
readdata;
initial;
run;
outdata
end.
Далее можно скопировать эту заготовку столько раз, сколько задач предложено на туре и сразу назвать каждый файл так, как это требуется по условиям олимпиады. В результате вам не придется при переходе от решения одной задачи к другой начинать работу с нуля (а попытка править текст с решением одной задачи для ускорения набора текста другой ведет только к порождению ошибок, на исправление которых будет потрачено гораздо больше времени). В разделе OPTIONS\enviroment\preferences среды программирования Turbo Pascal полезно установить параметр Auto save [X]Editor Files (автосохраниние редактируемых файлов). Это гарантирует автоматическое сохранение текста программы при каждом ее запуске. Таким образом, если, например, программа зависнет и среду программирования придется запускать заново, то результат последнего редактирования будет сохранен (к сожалению, во время тура школьники зачастую забывают самостоятельно время от времени запоминать сделанные ими изменения в тексте программ.
2. Затем следует очень внимательно прочитать условия всех задач и
постараться правильно (!!!) понять в чем заключается каждая задача. Если что-то
непонятно, в том числе и в формате ввода и вывода, то лучше задать вопрос.
Несмотря на очевидность данного правила, научить школьников его выполнять очень
непросто. Иногда здесь просто нужна тренировка внимания и умения формально
подходить к тексту условия задачи, то есть понимать условие буквально, а не так,
как покажется при его поверхностном чтении. Если же с точки зрения формальной
логики в условие все же можно трактовать неоднозначно, то тогда и следует
задавать вопросы.
3. Если вы приступили к решению конкретной задачи и основная структура
данных для нее вам ясна, то можно описать основные глобальные переменные и
набить процедуру readdata ввода данных, чтобы она считывала все параметры задачи
так, как это указано в условии. Если не оговорено иное, то делать формальную
проверку считанных данных, то есть проверять соответствие введенных значений
переменных условию задачи не нужно (!!!). Объясняется это тем, что по правилам
проведения большинства олимпиад последних лет считается, что все входные данные
при тестировании будут корректны. Кроме того, заметим, что при считывании из
файла чисел обычно следует использовать только процедуру read (а не readln), для
случаев же считывания симовлов и строк (тип string) это не так. Если количество
числе во входном файле неизвестно, то нужно использовать функцию seekeof вместо
eof для проверки условия окончания считывания чисел. Для файлов, содержащих
произвольный текст, это опять же уже не так.
Проверка на корректность, несомненно необходимая в профессиональном
программировании действительно в последнее время на олимпиадах практически не
производится. Хотя на олимпиадах прошлых лет такая практика и существовала.
Объясняется это тем, что количество предлагаемых на одном туре задач и их
сложность со временем возрастали и во время олимпиады важнее определить не
степень профессиональной пригодности участника как программиста, а его
способность решать те или иные задачи. А отмена проверки входных данных
позволяет участникам больше времени потратить на обдумывание алгоритмов решения
задач и их реализацию. Что же касается приведенных в данном пункте “технических”
советов по организации ввода данных, то ниже будут даны различные рекомендации
по технике и приемам программирования при решении олимпиадных задач, поэтому
сейчас подробно обсуждать мы их не будем.
4. В процедуре initial следует обнулить или присвоить соответствующие
начальные значения всем (!!!) глобальным переменным, за исключением тех, которые
будут использоваться в качестве параметров циклов. Затем запрограммировать вывод
результата в процедуре outdata так, как это требуется в условии задачи. Это
поможет дальнейшей отладке программы и в дальнейшем не потребуется “простой”
вывод переделывать в “правильный”. Таким образом, к этому моменту у вас уже
должна быть “работающая” программа. Она, по крайней мере, должна
компилироваться, считывать данные и выводить результат, пусть и нулевой, но в
нужном формате.
Отсутствие привычки инициализировать все объявленные переменные можно отнести к
небрежностям при программировании, в результате часть программ школьников, как
уже упоминалось выше, не работают при тестировании именно по этой причине.
Использование же отладочных форм выдачи результата во время олимпиады также вряд
ли разумно. Так, если задача уже отлажена, на переделку формата вывода может
просто не хватить времени. Или подобная работа, выполненная в последний момент,
окажется сделанной с ошибками, то есть либо формат выходных данных будет не
соблюден строго, либо дополнительно будет выводиться часть отладочной
информации, а по правилам олимпиады даже в этом случае задача не будет зачтена.
Еще одна типичная ошибка из данного класса — задание временных имен для входных
и выходных файлов, и как результат, не работающая, с точки зрения автоматической
системы проверки, программа.
5. При выполнении пунктов 3, 4 данной памятки или после следует
подумать над подходами к решению задачи, для чего ответить себе на ряд вопросов
и проделать ряд действий.
1) Проверить данные на фактическую корректность, то
есть всегда ли задача имеет решение для введенного набора данных, например,
связан ли граф, нет ли деления на 0 и т.п., если только в условии не сказано,
что все данные и в этом смысле корректны.
2) Определить, относится ли данная задача к знакомому
вам классу или решение придется искать “с нуля”.
3) Попытаться найти на бумаге (!!!) точное решение,
возможно только для малых размерностей. Такой подход зачастую позволяет
обнаружить закономерности, которые затем можно попытаться распространить и на
общий случай. Отобразить на бумаге принципиально различные случаи, в том числе и
вырожденные. Это поможет при составлении тестов для самопроверки написанной
программы.
4) Попробуйте сформулировать условие существования
решения, пусть только необходимое или только достаточное.
5) Продумать и выпишите (!!!) достаточную систему
тестов.
6. Запрограммируйте решение задачи в виде вызовов процедур и функций,
которые пока следует описать в виде “заглушек” (мнимого или пустого действия или
имитации настоящего действия, которое должна выполнять ваша программа). Таким
образом вы сможете отладить логику вашей программы, которая опять же должна
оставаться “работающей”.
7. Затем следует по одной набивать и отлаживать уже описанные
процедуры и функции, добиваясь, чтобы свое действие каждая из них выполняла
правильно в любом случае. например, поиск максимумов, сортировка массивов,
комбинаторные подпрограммы и т.п. должны работать корректно при любых входных
параметров, вне зависимости от программного контекста, из которого они будут
вызываться3. Особое внимание следует уделять программированию вырожденных
случаев. Так, если у вас в программе встречается деление, то сразу подумайте, не
может ли делитель быть нулем и рассмотрите этот случай отдельно. При
программировании циклов добивайтесь, чтобы зацикливания не происходило ни при
каких начальных значениях переменных, использующихся в том или ином цикле, и т.
д. и т.п.
Создание программы по плану, описанному в пунктах 6 и 7 данных обычно называют
методом программирования “сверху вниз”.
8. Если вы не придумали эффективного решения задачи, то запрограммируйте его по-простому: например, с помощью полного перебора или простой эвристики (приближенного решения в ряде случаев дающего точный ответ). Если и это сложно, то упростите себе задачу, то есть отбросьте условия, которые вам мешают или добейтесь, чтобы программа проходила на самых простых, например, вырожденных тестах (большинство параметров равны 0 или 1). Аналогично следует поступить с задачами, на решение которых у вас не хватило времени.
9. Прежде, чем окончательно cоздавать exe-файл, замените ряд директив
компилятора на следующие: D-,I-,L-,R-,Q- и отрегулируйте размер необходимого
вашей программе стека.
10. Постарайтесь запустить ваш exe-файл непосредственно в операционной системе
хотя бы для одного теста, чтобы убедиться в его работоспособности и еще раз
перечитайте условие.
Причины, по которым работающая в среде программирования программа, может
оказаться не работоспособной в виде исполняемого файла уже упоминались выше и
заключаются, в основном, в неинициализации значений ряда переменных.
Рекомендация же прочитать условие задачи еще раз уже после решения задачи,
только на первый взгляд кажется парадоксальным. Часто оказывается, что школьники
решали все же немного не ту задачу, какую требовалось. Например, находили
минимум вместо максимума и т.п. Иногда даже в последний момент ошибки, связанные
с подобной невнимательностью удается исправить.
Олимпиадное программирование - купить посредством SMS Цена: 300 тенге = 2 у.е.
Copyright © 2008
