Тестирование программ

Рассмотрим следующую задачу, сформулированную для олимпиады.

Задана квадратная матрица А размерности n x n из натуральных чисел до 100, где n<1000. Составить программу построения вектора В и вычисления суммы его элементов, где B_i= min A_lk для 1 < l < i и i < k < n.

Входной файл: input.txt, в первой строке которой задается размерность матрицы N, затем построчно задаются элементы матрицы, в N строках по N символов.

Выходной файл: в выходной файл Output.txt выдается сумма элементов вектора В.

Ограничения по времени: 1 секунд

Ограничения по памяти: 256Kb

Пример:

INPUT.TXT

1 12 4 2

12 34 11 7

4 1 2 12

1 1 1 1

OUTPUT.TXT

Для оценки работ этой программы жюри нужно определить следующие аспекты:

· метод решения задачи, удовлетворяющий данным ограничениям;

· создания системы тестов, учитывающих все типы особых случаев и их оценки;

· создание автоматизированной системы проверки правильности решенной программы с использованием данной системы тестов, которая на каждом тесте, определяя правильность программы, оценивала бы работу участника олимпиады.

На данном примере все аспекты мы рассмотрим.

1. Если воспользоваться рассмотренными методами решения данной задачи, то потребуется 1 Мгб памяти для массива, что невозможно в Турбо Паскале. Также, если определять для каждого B_i= min A_lk (1 < l < i, i < k < n), требуется около 10⁹операций сравнения, что тоже недопустимо ограничениями времени.

Поэтому рассмотрим для ускорения процесса задачи следующую задачу построения вектора D=(d₁,d₂,d₃,…,d_n) по заданному вектору C=(c₁,c₂,c₃,…,c_n), где d_i=min c_j для i < j < n

For i:=1 to n-1 do

Begin

d[i]:=c[i];

for j:=i+1 to n do

if c[i]>d[j] then c[i]:=d[j]

End

Данный метод определения вектора D требует n(n-1)/2 операций сравнения. Но если сменить порядок определения элементов вектора D, то число сравнений будет n.

d[n]:=c[n];

For i:=n-1 downto 1 do

if c[i]>d[i+1] then d[i]:=d[i+1]

else d[i]:=c[i]

Этот подход сокращает вычисления время вычисления данного вектора в n раз.

При решении нашей задачи можно произвести преобразования заданной матрицы по каждой строке к данному виду

A₁₁ A₁₂ A₁₃ … A_1n A’₁₁ A’₁₂ A’₁₃ … A’_1n

A₂₁ A₂₂ A₂₃ … A_2n A’₂₁ A’₂₂ A’₂₃ … A’_2n

A= A₃₁ A₃₂ A₃₃ … A_3n=> A’= A’₃₁ A’₃₂ A’₃₃ … A’_3n

. . .

A_n1 A_n2 A_3n … A_nn A_n1 A_n2 A_3n … A’_nn

где A’_ij = min A’_il для i < l < n. Это преобразование сохраненяет результат решения и B_i= min A_lk (1 < l < i, i < k < n) = min A’_lk (1 < l < i, i < k < n) = min (min A’_i _i₊₁,A’_j _i) для 1 < j < i-1, соответственно появляется возможность сокращения времени решения данной задачи в n раз. Данный подход позволяет уложится в ограничения по времени.

Для решения проблемы нехватки памяти также можно решить, используя данную преоброзованию матрицу следующим образом. Поскольку при вычислении B_i требуется только два элемента или два вектора – текущий преобразованный и интегрированный A’’, где элементы содержат A’’_k=min A_lj для 1 < l < k, k < j < n . При смене i на i+1 новая интегрирующая строка A’’ i+1 строки получается из A’’ i строки и текущей строки матрицы А.

If A1[n]<A[n] {A1 – A’’}

then A1[n]:=A[n];

For j:=n downto i+1 do

Begin

If A[j]>A[j+1] then A[j]:=A[j+1];

If A[j]<A1[j] then A1[j]:=A[j];

End;

Таким образом, задача решается двуми векторами. Вектор В будет вычисляться по мере обработки вектора A’’, где при заданном i в A1 элементы A1_i для элементов от 1 до i будут соответствовать вектору В, а для элементов от i+1 до n будут соответствовать вектору A’’. Общий вид программы будет следующим.

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R-,S+,T-,V+,X+,Y+}

{$M 16384,0,655360}

const maxn=1000;

var a:array[1..2,1..maxn]of integer;

n,i,j:integer;

q:longint;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

readln(n);

{Ввод строки для формирования интегрированной строким}

for i:=1 to n do {ввод первой строки }

read(a[1,i]);

readln;

{установка минимумов по первой строке }

for i:=n-1 downto 1 do

if a[1,i]>a[1,i+1] then a[1,i]:=a[1,i+1];

{работа с остальными строками }

for i:=2 to n do

begin

{чтение}

for j:=1 to n do

read(a[2,j]);

readln;

{поиск минимумов}

for j:=n downto i do

begin

if a[2,j]<a[1,j] then a[1,j]:=a[2,j];

if a[2,j]<a[2,j-1] then a[2,j-1]:=a[2,j];

end

end;

{суммирование}

q:=0;

for i:=1 to n do

q:=q+a[1,i];

write(q); {результат – нәтиҗә}

close(input);

close(output);

end.

2. Далее рассмотрим следующую систему тестов для проверки правильности программы участников олимпиады.

1-ый тест берется из примера, приведенного в условии задачи;

далее тесты генерируются следующей программой

program gen_test_1;

var

i,j,n,n_test,n_task,

max_zn,min_zn:integer;

f_out:text;

name,zn:string;

begin

write(‘n=’);readln(n); {определение размера массива}

write(‘Номер задачи=’);readln(n_task);

write(‘Номер теста=’);readln(n_test);

write(‘самое малое значение=’);readln(min_zn);

write(‘самое болшое значение=’);readln(max_zn);

str(name, n_task,I);

str(zn, n_test,I);

name:=name+’_’+zn;

rewrite (f_out,name);

for i:=1 to n do

begin

for j:=1 to n do

write(‘ ‘,random(max_zn - min_zn)+min_zn);

writeln(f_out)

end;

close(f_out)

end.

2-ой тест – матрица размерности 10х10 из элементов равных 1;

3-ий тест – матрица размерности 10х10 из элементов равных 2 кроме A₁_n = 1;

4-ый тест – матрица размерности 10х10 из 99;

5-ый тест – матрица размерности 10х10 из случайных значений от 1 до 99;

6-ой тест – матрица размерности 1000х1000 из элементов равных 1;

7-ой тест – матрица размерности 1000х1000 из элементов равных 2 кроме A₁_n = 1;

8-ой тест – матрица размерности 1000х1000 из 99;

9-ый тест – матрица размерности 1000х1000 из случайных значений от 1 до 99.

Оценка тестов можно сделать по 10 5 10 5 10 5 10 5 10 балов. В данном случае ценность отдельного случая опредеяется сложностью реализации. Для отдельной оценки полностью завершенной задачи можно внести баллы бонусы – 10 баллов. Таким образом, ценность данной работы 70 баллов.

3. Инструкция по использованию тестирующей системы

Подготовка системы к работе

· завести каталог TEST, где будет производится тестирование;

· завести каталог TESTS, где будут храниться файлы с тестами, ответами, оценки и проверочные программы;

· каждую предложенную на олимпиаду работу членам жюри надо решить и приготовить следующие файлы:

· 1_<номер задачи>.pas – исходный текст программы участника олимпиады странслировать и получить файл 1_<номер задачи>.exe. Затем разместить в каталоге TEST;

· приготовить тесты и занести их в файлы <номер задачи>_<номер теста>.tst. Затем разместить в каталоге TESTS;

· Каждый приготовленный тест использовать для получения ответа программой, приготовленной членами жюри. Эти ответы занести в соответствующий файл <номер задачи>_<номер теста>.ans. Эти файлы с правильными ответами также разместить в каталоге TESTS;

· Приготовить программу сравнения ответа участника олимпиады с ответом приготовленным членами жюри в файле <номер задачи>.exe и разместить в разместить в каталоге TESTS;

· Затем приготовить для каждой задачи файл оценки <номер задачи>.inf, где записывается следующая информация

.Название = C.

.Количество тестов = 9

.Входной файл = input.txt

.Выходной файл = output.txt

.Ограничение времени = 3

.Баллы за тесты = 10 5 10 5 10 5 10 5 10

.Bonus за все тесты = 10

Этот файл разместить в каталоге TESTS;

Приготовить программу проверки правильности ответа в файле <номер задачи>.exe. Затем разместить в каталоге TESTS.

При подготовке проверки ответа можно использовать следующие фрагменты программы:

uses testlib;