Главная страница
Навигация по странице:

  • 7. Заметки о тестировании программ 327

  • 328 7. Заметки о тестировании программ

  • 7. Заметки о тестировании программ 329

  • 7. Заметки о тестировании программ

  • Заметки о тестировании программ 333

  • 7. Заметки о тестировании программ 335

  • Заметки о тестировании программ

  • Процедура сравнения соседних строк претерпит незначите- льные изменения. Приведем её для сравнения с предыдущей.

  • По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница25 из 26
    1   ...   18   19   20   21   22   23   24   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;
    1   ...   18   19   20   21   22   23   24   25   26


    написать администратору сайта