Даже самую простую программу необходимо проверить на нескольких тестовых данных, чтобы убедиться в правильности выбора алгоритма для поставленной задачи. Поэтому разработка тестов – это один из главных элементов при написании программ. Этот этап может занять даже больше времени, чем вы предполагали. Поэтому работу над написанием программы и тестированием лучше всего совмещать. Рекомендуем вам следить за работой и включать в нее следующие элементы:
- разбор входных и выходных данных для выбора алгоритма для решения поставленной задачи
- написание шаблона программы, включающий только процедуры ввода данных, самого решения и вывода данных.
- программирование алгоритма в виде созданных шаблонов-процедур.
- после написания и первоначальной отладки программы требуется проверить программу на граничные входные данные
- после проверки на идентичность выходных данных требуемым форматам может потребоваться изменить программу или даже сам алгоритм, после чего нужно будет заново проверить все разработанные ранее тесты.
- если ограничения превышают обычных входных данных, то необходимо самим написать программу для создания таких файлов входных данных.
- во время проверки разработанных тестов необходимо следить за временем исполнения программы для каждого теста - оно не должно превышать указанной величины.
Каждый этап предполагает определенных навыков в программировании и неограничен рамками этого раздела. Мы предлагаем рассмотреть только некоторые из них.
В самом начале полезно набрать приведенную ниже универсальную заготовку для решения олимпиадной задачи (она представляет из себя работающую программу), особое внимание следует обратить на директивы компилятора, приведенные в образце. С помощью команды <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:integer;
Procedure readdata;
Begin
Assign(input,'');
Reset(input);
Read();
End;
Procedure outdata;
Begin
Assign(output,'');
Rewrite(output);
Write();
Close(output)
End;
Procedure initial;
Begin
Fillchar(I, j, 0);
End;
Procedure run;
Begin
End;
Begin
Initial;
Readdata;
Run;
Outdata
End.
После этого скопируйте шаблон столько раз, сколько задач предложено на олимпиаде. Затем постепенно заполняйте процедуры инициализации, ввода и вывода данных, основного алгоритма, каждый раз проверяя программу на работоспособность.
Программировать алгоритм следует по методу «сверху вниз»: сначала подготавливайте заголовки процедур и функций для конкретного шага программы, а затем постепенно их заполняйте нужными операторами.
Выбор алгоритма должен сопровождаться разбором ограничений на входные данные. Например, если известно, что размер матрицы, отражающий пути в лабиринте, не должен превышать 100 на 100, то можно сразу предложить волновой метод прохода лабиринта, а не рекурсивный метод обхода бинарного дерева, построенного по найденным проходам в лабиринте, так как размер стека может превысить выделенный объем динамической памяти. Поэтому, еще до начала тестирования нужно внимательно исследовать входные данные. И только после выбора алгоритма и его реализации приступать к разработке тестов: построение файлов входных данных таким образом, чтобы в них были отражены всевозможные ограничения на входные данные. Например, если в задаче стоит ограничение на целое число N (0<N<=100), то нужно проверить программу и при N=1 и при N=100.
При разработке тестов могут потребоваться длинные строки или больших размеров матрицы или просто много целых чисел. Тогда для формирования таких тестов необходимо написать дополнительную программу, которая будет создавать случайным образом такие данные.
Например, для вывода матрицы из 0 и 1 размером 100х100, отражающую путь в лабиринте, можно предложить написать программу со следующим фрагментом:
Var i,j:integer;
…
Fro i:=1 to 100 do begin
For j:=1 to 100 do Write(random(2));
Writeln;
End;
…
Для вывода строки, длины 1000, можно вставить такой фрагмент в программу:
Var i:integer;
…
For i:=1 to 1000 do write(chr(32+random(127));
…
Для вывода в каждой строке 20 000 целых чисел в диапазоне от -500 000 до 500 000 можно предложить следующий фрагмент программы:
Var i:integer;
…
For i:=1 to 20000 do writeln(round(-5.0E+6 + random*1.0E+7));
…
Не забудьте включить в программу процедуру инициализации генератора случайных чисел Randomize и направить вывод в файл:
При программировании на языке Turbo Pascal практически необходимо вставлять директивы для компилятора в текст программы. В противном случае, при компиляции программы из командной строки (в этом случае используются те значения для ключей компилятора, которые установлены по умолчанию) или из среды программирования, в которой через меню были установлены не те значения для ключей, при которых отлаживалась программа, работа программы может не соответствовать ожиданиям. Наличие директив компилятора в тексте позволяет легко их редактировать, а компиляция такой программы будет производиться согласно установленным параметрам тех или иных ключей. Приведем значения ключей компилятора, наиболее оптимальные для отладки программы и прокомментируем наиболее важные из рекомендованных установок параметров:
{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,R+,S+,T+,Q+,P-,V+,X+}
{$M 65520,0,655360}
Собственно для отладки программы наиболее значимыми являются ключи D+ и L+. Именно благодаря им в исполнимый код программы вставляется отладочная информация и из среды программирования программу можно выполнять “по шагам”, просматривая значения тех или иных переменных на различных стадиях выполнения программы. Вот некоторые команды, применяемые при отладке программы.
F7 – Trace into – пошаговое выполнение программы с заходом в подпрограммы.
F8 – Step over - пошаговое выполнение программы без захода в подпрограммы.
F4 – Go to cursor – выполнение программы до текущего местоположения курсора в программе.
Ctrl-F2 – Program reset – прерывает выполнение программы.
F9 – Run – продолжает выполнение программы.
Перед отладкой программ можно добавить точки останова Debug/Breakpoints, т.е. установить метку на ту строку, до которой будет выполняться программа, с помощью Ctrl-F8 – Add breakpoints.
Во время выполнения и после окончания программы можно просмотреть значение переменных, которые добавляются для просмотра в специальном окне Debug/Watch с помощью Ctrl-F7 – Add watch.
Еще одна пара ключей — E+ и N+ необходима, если программа использует вещественные числовые типы данных, арифметические и логические операции над которыми производятся с помощью сопроцессора, а именно: comp, single, double и extended. Без упомянутых ключей программа, использующая эти типы, просто не будет компилироваться. Строго говоря, ключ E+ был необходим лишь для компьютеров, сопроцессор в которых отсутствовал и операции над вещественными числами осуществлялись с помощью так называемого эмулятора — программы, реализующей эти операции только через команды процессора. Однако, все процессоры класса Pentium, содержат встроенный сопроцессор, который будет использоваться при выполнении программы, написанной на языке Turbo Pascal, в случае установки ключа компилятора N+. Заметим, что одновременное “включение” и эмулятора и сопроцессора приводит к использованию последнего при наличии сопроцессора и эмулятора при его отсутствии. То есть такая комбинация ключей делает программу “переносимой”, не зависящей от компьютера, на котором она исполняется.
Установка ключа I+ приводит к тому, что при работе программы строго контролируется соответствие поступающих на вход программы констант типам переменных, которым значения этих констант будут присвоены. В случае несоответствия типов, например, при вводе символа вместо числа или вещественного числа вместо целого, выполнение программы будет прервано.
Совершенно незаменима при отладке программы следующая установка ключей компилятора: R+ и Q+. Они позволяют контролировать во время выполнения программы “выход за границу массивов” и “выход за границу допустимого диапазона значений” при операциях над целочисленными переменными. То есть при попытке обращения к несуществующему элементу массива или если во время выполнения операции (арифметической или присваивания) над целыми числами результат, в том числе и промежуточный, не является допустимым для соответствующего типа, то выполнение программы прерывается. При этом ключ R+ отвечает за корректную работу с массивами и присваивание только допустимых значений переменным типа byte и shortint, а Q+ — за корректное выполнение арифметических операций над целыми числами в рамках соответствующих типов. При отсутствии такого контроля поиск ошибки может быть затруднен тем, что промежуточные вычисления чаще всего производятся в целом типе наибольшего размера (обычно 32-разрядном) и лишь при присваивании полученного значения переменной меньшего размера лишние старшие разряды оказываются отброшенными. Как следствие, отладочная информация о значении арифметического выражения и его результат могут не совпадать.
Рассмотрим это на примере следующей простой программы:
{$Q-}
Var a:integer;
Begin
a:=1*2*3*4*5*6*7;
writeln(7!=,a);
a:=a*8;
writeln(8!=,a)
End.
Если после получения переменной a своего первого значения, равного 7!, мы посмотрим в отладчике значение выражения a*8, то оно будет равно 40320, а в результате второго присваивания значение a окажется равным –25216.
Наконец, при установленном ключе компилятора S+ в программу вставляется код проверки стека на выполнение. Максимальный размер стека устанавливается директивой компилятора $M. Заметим, что прерывание работы программы с диагностикой Stack overflow (переполнение стека) чаще всего означает, что в программе есть подпрограмма, использующая рекурсивные вызовы, работа которой в следствие ошибки завершиться не может.
После того, как программа отлажена, то ряд ключей компилятора следует заменить на противоположные, а именно: сдавать программу на тестирование следует с ключами D-, I-, L-, R-, Q-. Объясняется это двумя причинами. Во-первых, при отмене ряда проверок и отсутствии отладочной информации программа будет выполняться быстрее. Во-вторых, если часть ошибок при отладке не устранена, но не является для работы программы фатальной (например, обращение к несуществующему элементу массива может не влиять на правильное формирование реальных его элементов), то программа может вполне успешно пройти процедуру тестирования. Если же проверка корректного обращения с данными в исполняемом коде остается, то, скорее всего, на большинстве тестов выполнение программы будет прервано досрочно и результат ее работы просто не будет получен.
Рассмотрим теперь, на что влияет директива компилятора $M. В обычном режиме конфигурация памяти, отводимой для работы программы, характеризуется тремя числами. Первое число определяет максимальный размер в байтах для стека, который будет использоваться программой. Максимально возможный размер стека равен 65520 байтов, размер стека по умолчанию — 16384 байта, а минимально возможный — 1024 байта. Если в программе используется рекурсия, то, скорее всего, ей понадобится достаточно большой стек, вплоть до максимально возможного. Но и однократный вызов процедуры или функции требует наличия стека достаточного размера, особенно если в качестве параметра-значения в процедуру или функцию передается массив (по этой причине массивы и сопоставимые с ними по объему занимаемой памяти переменные рекомендуется передавать только по ссылке, в Паскале — с использованием ключевого слова var). Уменьшать размер стека с помощью директивы компилятора имеет смысл только в случае использования динамических переменных. На размер памяти, отводимой под глобальные статические переменные повлиять практически невозможно, все вместе они не могут занимать более 64 килобайт памяти (например, один массив из 10000 чисел типа real занимает 60000 байт, то есть почти всю допустимую память). Данное ограничение является не естественным для современных компьютеров, следовательно, системы программирования, его содержащие, будут вытеснены. Оставшуюся после размещения глобальных переменных и фиксации размера стека оперативную память можно использовать лишь для создаваемых во время работы программы динамических переменных. Показанные в нашем примере значения второго и третьего параметров в директиве $M как раз и позволяют использовать всю оставшуюся в распоряжении программы память. Ее размер в обычном случае работы DOS-приложения ограничен 640 килобайтами, часть из которых используют другие программы (командный процессор, драйвер русской клавиатуры и т.д.). В условиях олимпиады участникам обычно гарантируется наличие 350-400 килобайт свободной оперативной памяти для работы программы и именно на этот объем и следует ориентироваться при создании динамических переменных. К сожалению, каждая из создаваемых во время работы программы динамических переменных в отдельности не может занимать более все тех же 64 килобайт памяти.
В заключение рассмотрим директивы так называемой условной компиляции, которые иногда удобно применять при отладке олимпиадных задач. В зависимости от того была или нет определена с помощью директивы $define некоторая последовательность символов часть кода программы, ограниченная директивами $ifdef и $endif, может быть как включена, так и исключена из процесса компиляции. Если же два фрагмента программы являются альтернативными, то есть включен в программу должен быть строго один из них, то в дополнение к уже перечисленным можно использовать директиву $else. Рассмотрим это на примере организации ввода данных в программу или из файла или с клавиатуры (например, по условию задачи данные должны вводиться из файла, а при отладке входные параметры удобнее вводить с клавиатуры).
Var n:integer;
Begin
{$define debug}
{$ifdef debug}
assign(input,'con');
{$else}
assign(input,'input.txt');
{$endif}
reset(input);
read(n)
…
End.
Так как в приведенном фрагменте программы последовательность debug определена, то ввод данных будет осуществляться с клавиатуры, если же эту команду отменить (закомментировать или слово debug в ней заменить на, например, nodebug), то ввод данных будет производиться из файла input.txt.
Для организации ввода данных из текстового файла наличие файловой переменной типа text в программе вовсе не обязательно. Более того, перенаправление стандартного потока ввода input и потока вывода output в файлы является и более удобным при программировании и избавляет от ряда ошибок. После подобного перенаправления ввод данных из файла осуществляется с помощью обычных процедур read и readln, а вывод — с помощью write и writeln без указания в качестве первого параметра имени какой-либо файловой переменной. Такой подход избавляет от типичной ошибки при работе с текстовыми файлами, которая заключается в том, что в некоторых обращениях к процедурам ввода или вывода имя файловой переменной оказывается пропущенным. Это не нарушает работу программы в целом, так как часть информации может быть записана в файл, а часть — выведена на экран. Вторая типичная ошибка при работе с файлом, открытым на запись — отсутствие в конце программы команды, закрывающей файл. В таком случае, создаваемый программой выходной файл скорее всего окажется пустым. Дело в том, что реальная запись данных на жесткий диск происходит или при выполнении уже упомянутой команды close или, если количество выводимой информации велико, в момент переполнения буфера оперативной памяти, предназначенного для ускорения работы с файлами. Но и от этой ошибки работа со стандартным потоком вывода спасает. Дело в том, что файл output закрывается при окончании работы программы автоматически, вне зависимости от наличия или отсутствия команды close(output).
Рассмотрим теперь полезные приемы программирования ввода данных различных типов. Начнем с описания считывания из текстового файла или консоли (клавиатуры), которая с точки зрения программы также является текстовым файлом, числовых данных. В условии задачи ввод большого количества чисел может быть задан двумя способами. В первом способе сначала предлагается ввести количество чисел, а уж затем сами эти числа. В данном случае при программировании сложности не возникают. Во втором же случае количество чисел приходится определять в процессе их считывания. Пусть, например, для каждой строки входного файла требуется найти среднее арифметическое для чисел, расположенных в ней, количество чисел в каждой из строк и количество строк при этом неизвестно. Наиболее простым и правильным будет следующее решение такой задачи:
While not seekeof do
Begin
n:=0;
s:=0;
while not seekeoln do
begin
read(a);
s:=s+a;
n:=n+1
end;
{readln;}
if n>0 then writeln(s/n:0:2) else writeln
End;
Заметим, что обычно применяемые в таких случаях функции eof и eoln заменены на seekeof и seekeoln соответственно. Имя файловой переменной при этом опускается, что опять же возможно для стандартного потока ввода, даже после перенаправления его в файл. Только при показанном способе ввода чисел не возникают ошибки в работе подобной программы, связанные с наличием пробелов в конце строк и пустых строк в конце файла, так как для корректного использования функции eof требуется, чтобы признак конца файла стоял непосредственно после последнего числа в файле. То же требование относится к признаку конца строки при использовании функции eoln. Несмотря на то, что числа расположены в различных строках файла, процедуру readln при вводе именно чисел можно не использовать (в приведенном примере она взята в комментарий, снятие которого не изменит работу программы).
Наоборот, если во входном файле находится текст, размер которого неизвестен, то поступать следует несколько по другому. Использование seekeoln может привести к ошибке, так как в тексте пробел уже является значимым символом. С другой стороны, служебные символы, обозначающие конец строки в файле и перевод на новую строку (их коды 13 и 10), не могут считаться частью текста и не должны анализироваться алгоритмом его обработки. Поэтому, если известно, что длина каждой строки текстового файла не превосходит 255 символов, то удобнее всего считывание производить с использованием переменной типа string:
While not eof do
Begin
readln(s);
if s<>'' then {обработать строку s}
End;
В этом примере использование readln, а не read является уже принципиальным. Если же ограничения на количество символов в одной строке нет, то считывание следует производить посимвольно. Пример посимвольного считывания текста из файла:
While not eof do
Begin
n:=0;
s:=0;
while not eoln do
begin
read(с);
{запись символа с в массив или его обработка}
n:=n+1
end;
readln;{!!!}
if n>0 then {обработка строки} else {строка пустая}
End;
Именно использование оператора readln позволяет и в данном случае автоматически исключить из рассмотрения символы перевода строки.
Последний вариант считывания данных относится к случаю смешанной информации, то есть в файле присутствуют как числа, так и символы или последовательности символов. Формат такого файла обычно определен заранее, поэтому считывание можно организовать сразу в переменные соответствующих типов. Наоборот, считывание информации в одну строковую переменную, а затем выделение из нее отдельных элементов и преобразование строкового представления данных в числовое, делает программу более громоздкой и зачастую требует отладки. Пусть, например, в каждой строке файла записана фамилия человека, затем через пробел его год рождения и, наконец, опять же через пробел — его пол, обозначенный одной буквой. Приведем фрагмент программы, считывающий данные описанного формата из файла сразу в переменные соответствующих типов:
While Not Seekeof Do
Begin
Read(C);
S:='';
{формируем строку с фамилией}
While C<>' ' Do
Begin
S:=S+C;
Read(С)
End;
Read(N);{считываем год рождения}
Readln(C,C);{считываем пол}
…{обработка считанной информации}
End;
При считывание символа, обозначающего пол человека, предварительно следует пропустить пробел, который ему предшествует. Именно поэтому считываются два символа, а не один, и значение первого символа (пробела) теряется при считывании второго (значения пола).
Во время записи результатов работы программы в файл обычно проблем практически не возникает. Ошибки в формате вывода могут быть связаны с отсутствием разделителей (пробелов или символов перевода строки) между выведенными в файл числами или с формой записи вещественного числа. Если вещественные типы данных используются для работы с целыми числами, а при выполнении над целыми числами только операций сложения и умножения это часто позволяет получить точный результат, по количеству значащих цифр более чем в два раза превосходящий максимальный целый тип, то выводить результат следует так:
writeln(x:0:0)
Если же результат работы программы представляет из себя произвольное вещественное число, то формат его вывода обычно оговорен в условии задачи. Так, если требуется получить в дробной части три цифры, то печать можно производить по формату x:0:3.
Для инициализации данных в программе можно использовать процедуру FillChar, которая заполнит нулями необходимое количество байт, отведенное под указанную переменную.
Fillchar(i,ofs(Last)-ofs(i)+sizeof(Last),0)
Здесь i — имя обязательно первой из описанных в программе переменных, Last— последней. Таким образом, данная стандартная процедура заполнит нулями все байты памяти, которые используют статические переменные. После выполнения этой операции все числовые переменные, в том числе и элементы массивов, получат нулевые значения, всем символьным будет присвоен символ с кодом 0, а всем строковым — пустые строки, так как в байт, отвечающий за длину строки также занесен ноль и т.д. Если же количество глобальных переменных в программе невелико и не для всех из них ноль подходит в качестве начального значения, то инициализацию можно проводить для каждой переменной в отдельности. Для простых переменных это можно делать с помощью оператора присваивания или путем описания переменных как типизированных констант (в разделе описаний const, но с одновременным указанием и типа переменной и ее значения). Для массивов— с использованием все той же процедуры fillchar, но в пределах конкретного массива. Например:
Var a:array[1..1000]of integer;
c:array[1..10000]of char;
Begin
fillchar(a,sizeof(a),0);{заполняем массив a нулями}
fillchar(с,sizeof(с),'+');{заполняем символом плюс массив с}
…
End.
К сожалению, таким способом ненулевые значения можно присвоить лишь массивам, элементы которых по размеру не превосходят один байт (типы byte, shortint, char, boolean). Значения элементов массивов других типов задавать приходится в цикле. Однако если два массива одного и того же типа требуется проинициализировать одинаково, то заполнить в цикле можно только один из них, а второму массиву просто присвоить первый (присваивание — единственная допустимая операция над составными переменными, такими как массив или запись, как над целыми объектами). Иногда массивы удобно описывать и задавать в разделе констант путем непосредственного перечисления значений всех элементов массивов.
Как уже говорилось выше, для размещения всех глобальных переменных программе отводится не более 64 килобайт оперативной памяти. Однако при решении задач иногда требуется завести несколько массивов, размер каждого из которых не менее 32 килобайт. Покажем, как достаточно просто решить подобную проблему:
Const n=150;
Type aa=array[1..n,1..n] of integer;
Var a:aa; {a - массив}
b:^aa;{b - указатель на массив}
i,j:integer;
Begin
fillchar(a,sizeof(a),0);
new(b);{создание динамического массива}
b^:=a;{копирование массива a в динамический массив}
for i:=1 to n do
for j:=1 to n do
b^[i,j]:=i+j;{обращение к элементам динамического массива}
…
End.
Из примера видно, что работа с динамическими массивами не намного отличается от работы со статическими. Причем использовать данный прием можно “по образцу”, не вдаваясь в механизм работы с указателями. Если же размер двумерного массива превосходит 64 килобайта, то создать его с помощью динамических переменных можно, например, следующим образом:
Const n=500;
m=100;
Type aa=array[1..n] of integer;
Var b:array[1..m] of ^aa;
{b - массив указателей на одномерный массив}
i,j:integer;
Begin
for i:=1 to m do
new(b[i]);{создание m динамических массивов}
for i:=1 to m do
for j:=1 to n do
b[i]^[j]:=i+j;{обращение к элементам двумерного массива}
…
End.
Таким образом, использование динамических переменных позволяет практически не изменять алгоритм решения задачи в случае, когда использование статических массивов уже невозможно. Использование же таких переменных требует лишь небольшой аккуратности в их создании и корректного обращения с уже созданными динамическими переменными.
Если все тесты прошли успешно и уложились во времени, то задача решена. Поэтому для проверки программы на время можно включить такой текст:
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 {оставляем 0,5 секунд на запись результатов}
begin
…{запись текущего результата в файл
или сообщение об отсутствии решения}
halt
end else {собственно работа программы}
End.
Данная программа использует тот факт, что к значению четырехбайтовой целой переменной, расположенной по абсолютному адресу $40:$6С, раз в 1/18.2 секунды аппаратно прибавляется единица. Поэтому, если мы опишем в нашей программе переменную, привязав ее к этому адресу, то легко сможем определить время работы программы. А именно, запомнив в самом начале программы значение этой переменной (в нашем примере это оператор timeold:=timer), в процессе работы определить время выполнения в секундах можно по формуле (timer timeold)/18.2. Поэтому, если время тестирования известно, то прерывать поиск решения следует за некоторое время до его окончания (в нашем примере это 0,5 секунды), для того, чтобы успеть вывести результат.
Комментариев нет:
Отправить комментарий