Информация из этой статьи явно пригодится вам, если вы планируете или уже участвуете в соревнованиях, олимпиадах из перечня РСОШ или ВСОШ по предмету информатика (программирование).

Я расскажу о самых популярных и удобных способах тестирования, которые должен знать каждый, а также дам пару практических советов о том, что делать, когда вердикт вашего решения WA (wrong answer) или TL (time limit).

Методы тестирования

1. Стресс-тесты

Основная идея – сравнение ответов, которые выдает ваше решение и медленная реализация, в то время как входные данные подбираются случайным образом.

Такой способ используется, когда:

  • Входные данные легко генерируются;

  • Медленное решение существует и пишется относительно недолго;

  • Ваша цель — найти тест, где программа получает неверный ответ или вовсе происходит ошибка выполнения.

У такого вида тестирования есть достаточно много реализаций. Кто-то пишет специальные скрипты, но на олимпиадах актуальнее и проще всего использовать обычные функции. Вот пример на языке Python:

import random
def my_solution(k: int):
    answer = k // 2
    return answer

def slow_solution(k: int):
    answer = 0
    for i in range(0, k + 1):
        if i % 2 == 0:
            answer += 1
    return answer

for i in range(100):
    n = random.randint(1, 100)
    if my_solution(n)!= slow_solution(n):
        print(n)

Как медленное решение советую использовать перебор, несмотря на то, что решение работает за O (n) или вообще O (n²), но главное — оно будет заведомо верное.

В каждом языке есть свои предустановленные модули для получения случайных значений: 

# в Python
import random 
n = random.randint(a, b)
// в C++
#include <iostream>; #include <cstdlib>; #include <ctime>
using namespace std;
int main() {
    int a = 0; int b = 10;
    int n = a + rand() % (b - a + 1);
    cout << n << endl;
    return 0;
}

2. Встроенные дебаггеры

В каждой среде разработки есть возможность выполнять программу построчно. В классической реализации вам предоставляется возможность поставить точки останова — это значит, что в определённый момент программа прервётся и вы сможете просматривать значение переменных, входить/выходить из циклов, видеть всё поведение в общем.

На практике использовать дебаггер полезно, когда:

  • Есть тест с непонятным поведением программы;

  • Ваше решение объёмное — в нём с ходу не найти ошибку;

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

Подробнее почитать про особенности дебаггеров в разных средах советую здесь:

По ссылкам вы найдете официальную документацию с подробным описанием различных особенностей.

3. Проверка граничных случаев

Нередко, ошибки в решении связаны со специфическими случаями. Вот целый список подобных ситуаций:

  • Переполнение – встречается при работе с большими числами в некоторых языках программирования (С++ и т.д.);

  • Превышение глубины рекурсии – ее надо либо увеличивать (как в Python) или менять решение;

  • Нехватка памяти – часто бывает, если вы создаете большой массив или храните объемные данные;

  • Необработанные граничные случаи – например программа не выводит -1 или не обрабатывает часть входных данных;

  • Нестабильное поведение при работе с отрицательными числами -следовательно, найденное вами решение некорректно;

  • Деление на 0 или неправильная работа с вещественными числами: их сравнение, деление, округление, потеря точности.

Чтобы предотвратить все ошибки и исправить их на начальной стадии стоит:

  1. Запустить свое решение на минимальных значениях.

  2. Повторить то же самое с максимальными значениями.

  3. Если это удовлетворяет условиям сделать тесты с отрицательными числами \ отрицательными и положительными.

  4. Придумать тесты на другие граничные случаи исходя из условий.

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

4. Дополнительные советы

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

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

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