Next:3.8 Отладка
Up:3 Общие рекомендации по выполнению заданий
Previous:3.6 Кодирование алгоритма (программирование)

3.7 Выбор и обоснование набора тестов

1. Во-первых, из-за того, что задача была понята неверно, может оказаться, что решена совсем не та задача, которая была поставлена.

2. Неверным может оказаться и первоначальный замысел алгоритма, его спецификация (скажем, из-за неверно понятого условия задачи выбранный алгоритм будет давать правильное решение не для всех исходных данных, а только для их узкого подмножества).

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

4. Наконец, много ошибок типа описок появляется в программе в процессе набора текста программы или каком-либо ином переносе текста программы на машинные носители.

С разработкой алгоритма и программы тесно связано и построение набора тестов, на которых работа программы будет проверяться во время ее отладки. При совместной разработке программы и набора тестов легче добиться полноты этого набора -- того, чтобы каждый имеющийся в программе переход был пройден на одном из тестов набора.

Отметим сразу же, что тест представляет собой не только некоторую совокупность входных данных для программы, но и точное описание всех результатов, которые должна выработать программа на этих данных в том виде, как эти результаты должны быть расположены на выдаче. Естественно, что в понятие "результат" включаются при этом и те сообщения, которые должны напечатать размещенные в программе для повышения ее надежности операторы печати. Нарушение этого требования приводит к тому, что оценка правильности работы программы на выбранных данных становится невозможной. Например, если речь идет о программе, проверяющей свойства простоты натурального числа  (см. пример ниже), то нет смысла тестировать ее для , если заранее не известно, каким является это число -- простым или составным.

Обычно уже из формулировки задачи вытекает необходимость проверки работы программы по крайней мере на двух тестах. Пусть, например, в задаче требуется подсчитать количество окружностей, каждая из которых проходит хотя бы через три различные точки из заданного множества, в котором не меньше трех точек. Тогда в качестве тестов заведомо необходимо взять множество точек, лежащих на одной прямой (с ожидаемым сообщением об отсутствии искомых окружностей), и множество, в котором не все точки лежат на одной прямой (в этом случае тест должен содержать ответ -- сколько требуемых окружностей должна обнаружить программа с учетом приближенности вычислений, о которых говорилось ранее).

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

П р и м е р. Пусть требуется построить программу, которая печатает сообщение N--ПРОСТОЕ, если натуральное число N является простым, и сообщение N--СОСТАВНОЕ в противном случае.

Сразу же отметим, что в наборе тестов должно быть хотя бы одно простое и одно составное число. Далее, число N по определению простое, если оно делится лишь на себя и на 1; но при этом 1 по определению составное. Такое определение разбивает все числа на две группы: 1 (особый случай) и остальные числа. Значит, число 1 заведомо должно быть среди тестов для разрабатываемого алгоритма. Далее, простоту N можно проверить, последовательно разделив его на числа от 2 до ; если хотя бы одно такое деление удалось, то N -- составное, иначе N -- простое. С точки зрения эффективности алгоритма предпочтительно разбивать числа на четные и нечетные; при этом четные разбиваются в свою очередь на две группы -- число 2 (простое) и остальные (составные), а делители нечетного N можно искать среди нечетных чисел от 3 до . Отсюда ясно, что в наборе тестов должны присутствовать число 2, некоторое четное число, отличное от 2, и хотя бы два нечетных числа -- простое и составное. А теперь приведем программу решения этой задачи.

module PRIME;
    var N, DEL, KOREN : integer;
begin read(N);
    if N=1 then writeln('1 - СОСТАВНОЕ')
    elsif N=2 then writeln('2 - ПРОСТОЕ')
    elsif N mod 2 = 0 then writeln(N, '- СОСТАВНОЕ')
    else KOREN:=SQRT(N)+1; DEL:=3;
            while (DEL =KOREN)&(N mod DEL 0)do  DEL:=DEL+2 end;
            if DEL =KOREN then writeln(N, '- СОСТАВНОЕ')
            else writeln(N, '- ПРОСТОЕ')
            end
    end
end PRIME.

В этой программе тело оператора цикла выполняется для всех нечетных N > 3, но не выполняется для N=3. Значит, число 3 также нужно включить в набор тестов. Окончательный набор тестов мог бы выглядеть следующим образом:

{ (1, '1--СОСТАВНОЕ'), (2, '2--ПРОСТОЕ'), (3, '3--ПРОСТОЕ'), (6, '6--СОСТАВНОЕ'), (11, '11--ПРОСТОЕ'), (77, '77--СОСТАВНОЕ') }

Другой важный вопрос, решаемый при выборе тестов, -- это количественные ограничения на размеры используемых в программе исходных и промежуточных данных, на величину значений. Здесь необходимо учитывать следующее.

Во-первых, в программе должны быть предусмотрены проверки соблюдения количественных ограничений, а в наборе тестов должны быть тесты, на которых эти ограничения нарушаются и в которых ожидаемый ответ содержит диагностическое сообщение об этом факте.

Во-вторых, имеется еще и ограничение на время выполнения программы на формулируемых тестах. Обычно нетрудно получить оценку порядка роста времени выполнения программы в зависимости от размера теста. Такая оценка позволяет не включать в набор тестов таких данных, для которых машинное время решения задачи заведомо не укладывается в разумные рамки (для студенческой задачи, скажем, более минуты). Например, если алгоритм перебирает все подмножества заданного множества, то следует отказаться от тестов, приводящих к обработке множеств мощности, превосходящей 20, поскольку у множества мощности  имеется  различных подмножеств. Переборные задачи, для которых наиболее важен учет отмеченного соображения, содержатся в разделах, посвященных графам, логическим формулам, играм.

Next:.3.8 Отладка
Up:3 Общие рекомендации по выполнению заданий
Previous:3.6 Кодирование алгоритма (программирование)