В этом параграфе вы познакомитесь с процессом решения задач по программированию: от понимания условия и проектирования алгоритма до реализации, тестирования и анализа результатов.
Ключевые вопросы параграфа
- Какие шаги проходит программист при решении алгоритмической задачи?
- Как проверить корректность и эффективность своего решения до его сдачи?
Пять простых шагов для решения задачи по программированию
Чтобы рассказать, как работает наша система автоматической оценки, мы по шагам разберём две простые задачи. А заодно покажем несколько распространённых проблем и способы их преодоления.
Итак, решение задач по программированию состоит из пяти шагов:
-
Разбор условия задачи. Формулировка задачи указывает формат ввода и вывода, ограничения для данных ввода и использования памяти. От вас требуется написать быструю программу, которая уложится в ограничения по времени и использованию памяти.
-
Проектирование алгоритма. Когда вы поняли, в чём состоит задача, начинайте проектировать алгоритм. Не забудьте доказать, что он работает правильно.
-
Реализация алгоритма. Когда алгоритм спроектирован, его можно реализовать в вашем языке программирования.
-
Тестирование и отладка. Тестирование — это искусство поиска багов. Отладка — это искусство устранения багов. Когда программа готова, приступайте к тестированию! А если обнаружите баг — исправьте его и протестируйте программу снова.
-
Отправка программы на оценку. Когда программа протестирована, сдайте её системе оценки. Если вы увидите сообщение
OK, значит всё в порядке. Если нет — возвращайтесь к предыдущим шагам.
Разбор условий задачи
Для начала прочтите формулировку задачи. В неё входят описание вычислительной части, ограничения по времени и использованию памяти и несколько демонстрационных тестов. Убедитесь, что вы понимаете, как вывод соотносится с вводом в каждом из демонстрационных примеров.
Если ограничения по времени и памяти не указаны прямо в формулировке задачи, используются следующие значения по умолчанию.
- Ограничение по времени (с): 1
- Ограничение памяти: 512 Mb
Проектирование алгоритма
Когда вы разработали алгоритм, докажите, что он работает верно, и попробуйте оценить время выполнения с помощью самых сложных вводных данных, указанных в секции об ограничениях.
Если ваш ноутбук выполняет около – операций в секунду, и максимальный размер набора данных в описании задачи , тогда алгоритм с квадратичным временем выполнения вряд ли уложится в ограничение по времени (так как ), в то время как решение с временем выполнения сможет это сделать. Тем не менее решение с подойдёт, если и если .
Сработать могут даже решения с . Хотя для некоторых трудных задач в книге полиномиальные алгоритмы и остаются неизвестными, решение с временем выполнения может уложиться в ограничение по времени при ниже .
Реализация алгоритма
Начните реализацию алгоритма на одном из языков программирования, которые поддерживаются нашей системой автоматической оценки. Напоминаем, это: C++, Java, Python3.
Для C++, Java, и Python3 есть примеры (авторские решения) с правильным решением задачи, учитывающие ее ограничения. Они тратят максимум 1/3 заданного лимита по времени и максимум 1/2 по памяти.
Тестирование и отладка
Сдавать вашу реализацию на оценку, не проверив её, — это плохая идея!
- Начните с маленьких наборов данных и убедитесь, что ваша программа выдаёт верный результат со всеми предложенными наборами данных.
- Затем проверьте, сколько времени занимает обработка большого набора данных.
Оценка времени
Для оценки времени выполнения имеет смысл реализовать ваш алгоритм как функцию — например, solve(dataset) — и потом реализовать дополнительную процедуру generate(), которая выдаст большой набор данных.
Например, если ввод задачи — это последовательность целых чисел длиной 1≤n≤1051≤n≤105, тогда сгенерируйте последовательность длиной 105105, передайте её функции solve() и убедитесь, что программа выдаёт правильный результат.
Проверка ограничивающих значений и экстремальных случаев
Проверьте ограничивающие значения, чтобы можно было гарантировать, что программа правильно обрабатывает и короткие (например, из 2 элементов), и длинные последовательности (например, из 105105 элементов).
Если последовательность целых чисел от 00 до 106106 даётся в качестве ввода — проверьте, как ваша программа ведёт себя с последовательностью 0,0,…,00,0,…,0 или с 106,106,…,106106,106,…,106. После этого проверьте программу на случайном наборе данных.
Дополнительно советуем проверить экстремальные случаи: пустой набор данных, три точки на одной строке, дерево из одного узла и так далее.
Стресс-тестирование
Убедившись, что ваша программа выполняет все эти тесты, переходите к стресс-тестированию.
- Реализуйте медленный, но простой и верный алгоритм.
- Проверьте, выдают ли две программы одинаковый результат, — однако обратите внимание, что это не применимо к задачам, в которых вывод не уникален.
- Сгенерируйте случайные тестовые сценарии, а также тесты с изменением параметров — например, с использованием только маленького диапазона больших чисел, строки с одной буквой
aили только двумя разными буквами (вместо строк, использующих все буквы латинского алфавита) и так далее. - Подумайте, какие ещё тесты могут быть в каком-то смысле необычными.
Например, если вы генерируете графы, попробуйте генерировать древовидные, несвязные, полные, двудольные и так далее.
- Если вы генерируете древовидные графы, попробуйте генерировать пути, двоичные деревья, звезды и так далее.
- Если вы генерируете целые числа, попробуйте генерировать и простые, и составные числа.
Использование системы проверки
Когда вы закончили тестирование, сдавайте вашу программу на проверку.
- Перейдите на страницу, где сдаются задания, и создайте новое выполненное задание.
- Загрузите файл с вашей программой (обязательно загрузите исходный файл, а не готовое приложение).
- После этого система оценки скомпилирует вашу программу и использует набор тщательно продуманных тестов, чтобы убедиться, что программа выдаёт правильный результат для всех тестов и что она укладывается в ограничения по времени и памяти.
- В большинстве случаев оценка занимает около минуты, но в редких случаях, когда серверы загружены, может потребоваться больше времени. Пожалуйста, наберитесь терпения. После загрузки решения можно спокойно уходить со страницы.
- В качестве результата вы получите обратную связь от системы оценки. Вам нужно получить вердикт
OK— он обозначает, что ваша программа прошла все тесты.
Сообщения Wrong answer, Time limit exceeded, Memory limit exceeded означают, что программа не прошла тест по одной из этих причин.
- Если ваша программа даёт сбой, проходя один из первых двух тестовых сценариев, система оценки скажет вам об этом и покажет тестовый сценарий и вывод вашей программы. Это должно помочь вам использовать правильный формат ввода/вывода.
- В остальных случаях система оценки не будет показывать вам тестовый сценарий, который ваша программа не смогла выполнить.
Что дальше
Теперь вы понимаете, как проходит полный цикл работы над задачей: от разбора условия до уверенного тестирования решения. Вы научились не только писать алгоритмы, но и проверять их корректность и производительность.
Далее — простейшая задача, с которой удобно начать практику. Вы увидите, как её можно решить на C++, Java и Python 3, и попробуете реализовать свой первый рабочий код.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Решение задачи по программированию проходит через пять ключевых этапов: разбор условия, проектирование алгоритма, реализация, тестирование и анализ результатов.
- Оценка корректности и эффективности алгоритма помогает убедиться, что решение работает правильно и укладывается в заданные ограничения.
- Хорошее тестирование — это не просто проверка на примерах, а систематический подход: граничные случаи, случайные данные, стресс-тесты.