Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Анкор: Окулов.Программирование.в.алгоритмах.pdf
• Дата: 26.04.2017
• Размер: 5.46 Mb.
• Имя файла: Окулов.Программирование.в.алгоритмах.pdf
• Тип: Документы; #5718
• страница: 25 из 26

326
7. Заметки о тестировании программ
End.
Создаем систему тестов. В текущий директорий записываем
файлы с каждым тестом (имена i.tst, где i — номер теста) и ре-
зультирующие файлы (имена i.ans, где i — номер теста).
файла
2.tst
3.tst
5.tst
Тест
2 5 45 45 3 5 10 10 20 0
файла
2.ans
3.ans
5.ans
Результат
7 91 8
20 20
Переименование входных файлов в файл с именем input.txt
и пятикратный запуск программы при очевидных результатах утомительно и не очень удобно. Требуется минимальная авто- матизация процесса тестирования программ. Ниже приведен текст программы. Следует набрать и сохранить его в файле
Checker.dpr (текущий директорий), а затем откомпилировать,
используя среду Delphi. После этого запустите программу Chec-
ker.exe. Её входными параметрами (они задаются в командной строке) являются: имя исполняемого файла (рассмотренный выше пример следует откомпилировать в текущий директорий,
например, с именем количество тестов; ограничение по времени (в секундах). Вид командной строки — Checker.exe
ту.ехе 5 2 (5 тестов, 2 секунды на тест). Результат очевиден.
Итак, имея программу Checker, мы значительно упрощаем про- цесс отладки решений.
{$apptype
приложение.*}
uses
var
:
{* Установки для
функции
*}
:
Информация
о созданном
*}
TickCount : Longint;{* Количество миллисекунд.*}
:
тестируемой
программы. *}
PightAnswer :
Программа разработана студентом 4-го курса факультета информатики Вят- ского государственного педагогического университета Московкиным Алек- сеем Александровичем.

7. Заметки о тестировании программ 327
FileName : String;{*Имя тестируемой
программы.*}
Feedback :
тестирования.*}
TestCount :
тестов.*}
: Integer;{*Ограничение
по времени.* }
: Boolean;{*Индикатор окончания
лимита времени. *}
ExitCode : Cardinal;{*Код завершения
тестируемой программы. *}
i -.Integer;
begin
FileName := ParamStr
; { *Первый параметр - имя
*}
TestCount := StrToInt
-
количество тестов.*}
TimeLimit :=

ограничение
времени. *}
for i:=l to TestCount do begin
входной тест в
*}
:=
*}
:=
StartUpInfo
SInf
;=
{ *Сделать окно
процесса
*}
CreateProcess
false,{*3апуск тестируемой программы. *}
or
;
TickCount :=
время.*}
IsTimeLimit := true;
While ((TickCount+TimeLimit*1000) >= GetTickCount)
and IsTimeLimit do
if
пока программа
закончит работу или истечет
*}
IsTimeLimit := false;
if IsTimeLimit then begin {*Если истек
закончить работу
*}

328 7. Заметки о тестировании программ
:=
limit
лимита времени. *}
end
else begin
;
{*Получить код завершения программы. *}
if ExitCode<>0 then FeedBack := 'Run-time error!'
{*Если код завершения не равен нулю, то
ошибка времени
* }
else begin
;=
RightAnswer
{*3агрузить файл с ответами тестируемой
*}
Загрузить файл с правильными
* }
if
TextoRight Answer
then
Feedback := 'Wrong answer . . .' {*Если они
не совпадают, то тест не
*}
else FeedBack ;=
все в порядке.*}
end;
end;
;
входной тест.*}
'+FeedBack);
(*Выдать результат теста.*}
end;
ненужный
файл. *}
writeln
...');{*Выдать сообщение об
окончании. *}
Readln;
end.
7.3. Тестирование программы решения задачи (на примере)
Рассмотрим следующую задачу. Даны два квадратных кле- точных поля. Размер клетки 1*1. Клетки поля закрашены в бе- лый или черный цвет. Совпадающая часть квадратов — это

7. Заметки о тестировании программ
329
множество клеток, имеющих одинаковый цвет. Она разбивает- ся на какое-то количество связных областей. Найти площадь наибольшей связной области совпадающей части квадратов.
Пример
1-й квадрат
2-йквадрат
Результат связная область
(окрашен в черный цвет) имеет площадь 4
Пример.
Photol.txt
4 0100 1000 1110 1101
Photo2.txt
4 0111 1011 0010 0001 4
Описание квадратов хранится в текстовых файлах. Символ во входных файлах соответствует черной клетке, символ '0' — белой. В выходном файле должно быть одно целое число,
равное площади наибольшей связной области общей части.
Ограничения. Размер поля N в интервале от 2
до 1000. Время работы — не более 5 секунд.
Анализ и решение задачи. В идейном плане задача очень простая. Её суть сводится к следую- щему:
If
2 квадрата
Then
результата>: = 1
Else
результата>: = 0,
а затем найти связную область с наибольшей пло- щадью.
Проработав этот учебник до данной страницы,
программное решение представленное ниже, пи- шется за считанные минуты.
Структуры данных.
Size =
квадрата. *}
Dx: Array
.4] Of Integer = (0, -1, 0,
массивы Dx, Dy
используются в волновом алгоритме обхода
связной области. *}
Dy:
4] Of Integer = (-1, 0, 1, 0)
Type
Array
Of Byte;
{*Для хранения результирующего
*}
1)

330 7. Заметки о тестировании программ
Helper = Array [1..Size*Size] Of Integer;
тип для хранения очереди
при обходе в ширину. *}
Var
PhotoM :
квадрат. *}
Ох,Оу: Helper;
Result,
Integer;
Напомним логику волнового алгоритма (п. 3.2).
Function
: Byte):
совпавшей части
*}
Var i,
nx,
up : Integer;
Begin
:= k;
:= p; dn := 1 ; up := 1;
{ *3аносим координаты первой клетки
в
*}
PhotoM [k,p]:=0;
Repeat
For
4 Do Begin
nx
Ox [dn] + dx [i]; ny
Oy [dn] + dy [i];
If (nx>0) And (ny>0) And (nx<=N) And (ny<=N)
And
Then
в очередь. *}
PhotoM [nx, ny]
0;
(up) ; Ox [up] := nx;
Oy [up] := ny;
End;
End;
Inc
к очередному элементу
очереди. *}
Until dn>up;{*Пока очередь не пуста.*}
Get := up; {*Количество элементов в очереди равно
площади общей части. *}
End;
Процедура ввода данных.
Procedure
Var photol,
Text;
char2 : Char;
x,y : Integer;
Begin
Assign (photol,
Reset
файлы. *}
Assign (photo2,
;

7. Заметки о тестировании программ 331
For у := 1
N Do Begin
For х ;= 1
N Do Begin
Read
char2);
PhotoM
"закраска" совпадает, то ...*}
End;
ReadLn (photol); ReadLn (photo2);
End;
End;
Главная процедура.
Procedure Solve;
Var i, j , t
Begin
For
1 To N Do
For
1 To N Do
If (PhotoM[i,j]=l) Then Begin
t:=Get(i,j) ;
If t>Result Then
наибольшей связной области. *}
End;
End;
Вывод результата.
Procedure
Var f: Text;
Begin
Assign (f ,
; Write
(f, Result);
End;
Основная программа.
Begin
Solve;
WriteAnswer;
End.
Итак, часть тестов, вне всякого сомнения, проходит, и есть база для проведения экспериментов. Изменение значения кон- станты Size до требований задачи (даже до значения 200) при- водит к сообщению Error 22: Structure too large.
хватает

332
7. Заметки о тестировании программ
оперативной памяти. Напомним, что в среде Турбо Паскаль для задачи выделяется порядка 64 Кбайт*.
Размерность задачи такова, что результирующее клеточное поле хранить в оперативной памяти можно только с использо- ванием динамических структур, битовых записей, или ещё ка- ким-нибудь оригинальным способом. А требуется ли хранить?
Возможна построчная обработка поля. Пусть обработана стро- ка. При обработке следующей строки возможны ситуации: об- ласть 1 продолжается в следующей строке; область 2 закончи- лась; области 3 и 4 «сливаются» в одну; область 5 только начинается. Единственная небольшая сложность — правильно отслеживать изменение значений площади при слиянии облас- тей. Основные процедуры этого варианта программы приводят- ся ниже по тексту.
Const Size =
поля.*}
Answer = Array
Of
ответов (ячейки с площадями). *}
PhotoLine = Array
Of Integer;{*Для
обработки строки поля. *}
OldLine, NewLine :
-
NewLine - новая строки. *}
:
ячейка, для поиска
свободного номера связной области. *}
Procedure
Begin
FillChar( OldLine,
wrlnd := 1;
End;
, 0);
, 0);
В настоящее время происходит отказ от среды Турбо Паскаль на олим- пиадах по программированию. В новых таких жестких ограничений по оператив- ной памяти, как правило,
Автор считает, что ограничения - один из «двигателей»
развития. Вспомним 1 -й и 2-й этапы развития технологий программирования. Ограниче- ния по ресурсам ЭВМ являлись мощнейшим рычагом создания эффективных алгорит- мов и их исследования.

Заметки о тестировании программ 333
Result :
TempRes : Answer;
file2 : Text;
Procedure Change
Integer);
номера устаревших связных областей
на новое
*}
Var i : Integer;
Begin
For i ;= 1 To Size Do Begin {*Выполняется при
слиянии двух связных областей. *}
If NewLine[i] = Dellnd Then
;= Newlnd;
If
= Dellnd Then
:= Newlnd;
End;
End;
Procedure
предыдущей и
новой строк. Находим, какие связные области
сливаются или дают "потомство". *}
Var i -.Integer;
char2 :Char;
Begin
FillChar ( NewLine,
0);
For i := 1 To Size Do Begin
Read(filel, charl); Read(file2, char2);
charl = char2 Then Begin {*Правило одинаковой
*}
If (NewLine
= 0) Or (i = 1) Then Begin
{*Новая связная область. *}
While
Do
If wrInd
( wrind ) Else wrind
:= 1;
:= wrind
End
Else
:=
дополнение к связной области. *}
If
Then
или
*}
TempRes
[i] ]
TempRes
[ OldLine [i] ] +
[ NewLine [i] ];
{*Сложение значений
*)
If
Then Begin
*)
NewLine [i] ] := 0;
{*Уничтожение устаревшего описания
связной
*)

334
7. Заметки о тестировании программ
End Else NewLine [i] := OldLine [i] ;
*}
End;
(
] );
End
Else
:= 0;
End;
ReadLn
ReadLn (file2);
End;
Procedure Solve;
Var i, j : Integer;
Begin
Assign (filel,
Reset (filel);
Reset (file2);
For i
1 To Size Do Begin
строки. *}
For j := 1 To Size Do
If
[j]<>0) And
> Result)
Then Result
OldLine ;=
строку считаем
старой. *}
End;
;
End;
Продолжим тестирование решения. Вопросы с оперативной памятью решены. Остались временные ограничения — 5 се- кунд на работу программы с одним тестом. С этой целью необ- ходимо разработать достаточно полную систему тестов. Один тест максимального размера еще не говорит о том, что выполняются требования за- дачи. Один из файлов (для простоты) можно заполнить единицами (первая вспомо- гательная программа). А затем? Напрашивается создание фай- лов максимального размера по принципам, приведенным на рисунке, и, конечно, файла со случайными значениями, а это еще четыре вспомогательные программы (не ручным же спосо- бом заполнять файлы). Этим, вероятно, не исчерпываются все возможности, но ограничимся приведенными тестами — их до- статочно для нашего изложения. Затем необходимо организо- вать учет времени решения задачи одним из способов, описан-

7. Заметки о тестировании программ 335
ным выше (лучше,
естественно, вторым).
Что выясняется? Ока- зывается, только на од- ном из тестов времен- ное ограничение не выполняется, а именно на тесте со следующей структурой —
«на
Почему именно на этом тесте? Вернемся к решению. Ответ просматривается — частота слияния связных областей на тесте значительно возрастает, что вызывает работу процедуры Chan-
ge , е. лишний цикл (подсчитайте — сколько раз выполняется процедура Change для области 1000*1000, заполненной по принципу «зубьев»). Можно ли без принципиальных измене- ний на идейном уровне и в программной реализации добиться выполнения требований задачи? Оказывается, да! Используем идею косвенной адресации. Исключим, точнее изменим, проце- дуру Change из решения. В процедуре просматривался весь массив с целью поиска существующих «родственников». Изме- ним смысловую нагрузку элемента массива. Она будет содер- жать:
• или данные о площади;
• или ссылку (информацию) на ту ячейку, в которой запи- сано значение площади при слиянии связных областей;
• или ссылку на ссылку при многократном слиянии связ- ных областей.
Как их отличить друг от друга? Стандартный прием — отри- цательное значение является признаком косвенной адресации.
Исключение многократного просмотра длинных цепочек (при слиянии большого количества связных областей) осуществля- ется одноразовым прохождением по цепочке, после которого во всех ячейках указывается адрес конечной ячейки со значением площади. Еще один момент рассматриваемой идеи требует упо- минания. В предыдущем варианте признаком свободного номе- ра связной области являлось значение элемента в мас- сиве TempRes. В данном варианте этот массив используется для косвенной к ячейкам со значением площади, поэто- му требуется введение дополнительного массива с элементами логического типа для этой цели, назовем его Used.
Type
= Array
Of
для
хранения информации об использованных номерах
связных областей. *}
Var

Заметки о тестировании программ
При этом предположении поиск свободного номера связной области выглядит следующим образом.
Procedure
Used необходим,
значение Used[i], равное False, говорит о том,
что значение i - свободный номер связной
области. *}
Begin
While
Do
If wrInd
(
) Else
:= 1;
TempRes [ wrlnd ] ;= 0;
End;
Ключевая функция поиска номера ячейки, указывающей на значение площади. При выходе из рекурсии изменяем значе- ния
Function
ind : Integer
итоговый номер, указывающий на значение
площади. *}
Begin
If TempRes [ ind ] > 0 Then FindLast ;= ind
Else Begin
TempRes [ ind ] ;= -FindLast (
( TempRes
[ind] ) ) ;
FindLast := Abs ( TempRes [ ind ] ) ;
End;
End;
Процедура сравнения соседних строк претерпит незначите-
льные изменения. Приведем её для сравнения с предыдущей.
Procedure
Var i : Integer;
char2 : Char;
Begin
FillChar ( NewLine,
0) ;
For i := 1 To Size Do Begin
charl); Read(file2,
2) ;
If charA = charB Then Begin
If
= 0) Or (i = 1) Then Begin
NextWrlnd;{*Новый вариант поиска
свободного номера связной области. *}
newLine [i] := wrlnd;
End Else
:= NewLine [i-1];
If
And
Then

7. Заметки о тестировании программ 337
If
[
] > 0 Then Begin
(*Простое
*}
площади. *}
NewLine [i] ] := - OldLine [i];
ячейку со значением
площади в ячейку ссылочного типа. *}
:= OldLine [i]
End Else NewLine [i] := FindLast ( OldLine
[i] ); {*При слиянии со связной
областью, которая при данном
значении i помечена ячейкой
ссылочного типа, находим ячейку со
значением площади этой связной
области. *}
( TempRes [ NewLine [i] ] );
Used [NewLine [i] ] := True ;
End;
End;
;
End;