Задания № 23, 24, 25 · ЕГЭ

Проверка алгоритма

Как убедиться, что алгоритм даёт правильный результат на всех допустимых входных данных

6 мин чтенияСложность: Обновлено 29 сентября 2026

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

Что именно проверяют

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

Корректность алгоритма

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

Два уровня доказательства

Для алгоритмов с циклами обычно доказывают: 1) сохранение некоторого утверждения после каждой итерации; 2) завершение цикла; 3) соответствие результата условию после завершения. Это называют доказательством по инварианту цикла.

В задачах экзамена часто требуется не полное формальное доказательство, а рассуждение по таблице значений, состояниям исполнителя или набору тестов. Для такого рассуждения алгоритм удобно сначала перевести в точное описание: псевдокод помогает не пропустить порядок команд и условия. При необходимости сверяйтесь со страницами формализация алгоритма и псевдокод.

Тесты и границы области

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

Минимальные и максимальные допустимые значения.
Граничные случаи: 0, 1, равенство двух величин, переход через границу условия.
Обычный пример, для которого легко получить ответ вручную.
Случай, когда цикл выполняется 0 раз, 1 раз и несколько раз.
Наименьший случай, при котором появляются особые действия: препятствие, деление, невозможный переход.
Большие значения, если возможны переполнение, слишком долгий перебор или ошибка в оценке сложности.

\[\text{корректность} = \text{завершение} + \text{правильный результат на каждом допустимом входе}\]

Если задача связана с маршрутами Кузнечика, полезно отдельно проверять начало и конец отрезка, запрещённые клетки и клетки, в которые можно попасть несколькими способами. В вычислениях используют подсчёт маршрутов Кузнечика или динамику для маршрутов Кузнечика, но сам принцип тестирования остаётся тем же.

Как подобрать тест, который разоблачает ошибку

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

Микропроверка

Какой тест лучше всего проверяет условие `если x > 10`?

Инвариант и пошаговая проверка

Инвариант — утверждение, которое истинно перед первой итерацией и остаётся истинным после каждой итерации. В конце цикла к нему добавляется условие завершения. Вместе они позволяют установить, что найденный результат действительно правильный.

Инвариант цикла

Инвариант — свойство состояния алгоритма, сохраняющееся при переходе от одной итерации к следующей. Чтобы доказать его пригодность, проверяют начальный случай, сохранение при выполнении тела цикла и вывод о результате после остановки.

Для цикла суммирования естественный инвариант таков: после обработки первых \(i\) элементов переменная \(s\) равна сумме именно этих элементов. После обработки всех элементов \(s\) равна сумме всего массива.

Перед началом цикла обработано 0 элементов, поэтому сумма обработанной части равна нулю.

\(\displaystyle i=0,\quad s=0=\sum_{k=1}^{0}a_k\)

Предположим, после \(i\) итераций выполнено \(s=\sum_{k=1}^{i}a_k\). На следующей итерации прибавляется элемент \(a_{i+1}\).

\(\displaystyle s' = s+a_{i+1}=\sum_{k=1}^{i}a_k+a_{i+1}=\sum_{k=1}^{i+1}a_k\)

Цикл завершается при \(i=n\). Значит, обработаны все \(n\) элементов.

\(\displaystyle s=\sum_{k=1}^{n}a_k\)

Разобранный пример: поиск минимального элемента

Рассмотрим алгоритм поиска минимума в последовательности \(a_1,a_2,\ldots,a_n\). Начальное значение min берут равным первому элементу, а затем сравнивают его с каждым следующим.

Псевдокод

1min := a[1]
2for i := 2 to n do
3    if a[i] < min then
4        min := a[i]
5output min

№

Проверка по шагам

Возьмём последовательность \(7, 3, 5, 2, 2\). После каждой итерации проверяем, что min — наименьший среди уже просмотренных элементов.

Шаг	Просмотренные элементы	min
Начало	7	7
i = 2	7, 3	3
i = 3	7, 3, 5	3
i = 4	7, 3, 5, 2	2
i = 5	7, 3, 5, 2, 2	2

До цикла просмотрен первый элемент, поэтому текущий минимум равен минимуму просмотренной части.

\(\displaystyle \text{min}=a_1=\min(a_1)\)

На каждой итерации сравниваем новый элемент с текущим минимумом. После сравнения выбираем меньшее из них.

\(\displaystyle \text{min}'=\min(\text{min},a_i)\)

Если до итерации min был минимумом первых \(i-1\) элементов, то после неё он становится минимумом первых \(i\) элементов.

\(\displaystyle \text{min}'=\min(a_1,\ldots,a_{i-1},a_i)\)

После последней итерации просмотрены все элементы, значит, выведенное значение является минимумом всей последовательности.

\(\displaystyle \text{min}=\min(a_1,\ldots,a_n)\)

Алгоритм завершается, потому что счётчик \(i\) увеличивается на единицу и имеет конечную границу \(n\). Время работы — \(n-1\) сравнений, то есть линейное: \(O(n)\). Для доказательства важно отличать условие a[i] < min от a[i] <= min: оба варианта находят минимальное значение, но по-разному ведут себя при равных элементах, если дополнительно запоминается позиция.

Имитация, таблицы состояний и невозможность

Когда формальное доказательство слишком громоздко, алгоритм проверяют имитацией: выписывают значения переменных после каждой команды или итерации. Такой подход особенно полезен для имитации работы алгоритма и задач, где исполнитель перемещается по числовой оси или клеткам.

Для маршрутов составляют таблицу числа способов попасть в каждую позицию. Если переходы разрешены только из некоторых клеток, эти ограничения должны быть отражены в таблице, а не проверены «на глаз». При препятствиях см. препятствия на поле Кузнечика. Для задач с сосудами удобно хранить все достижимые состояния; отсутствие нужного состояния доказывает невозможность, а поиск кратчайшего пути — минимум операций. Полезны страницы невозможность получения объёма и минимальное число переливаний.

Частые ошибки

1. Считать несколько успешных запусков доказательством для всех входов. 2. Не проверять границу: использовать x >= 10 вместо x > 10. 3. Забывать случай пустой или одноэлементной последовательности. 4. Проверять только результат, но не завершение цикла. 5. При имитации пропускать изменение переменной на последней итерации. 6. Для маршрутов разрешать переход через препятствие или считать одну и ту же клетку несколько раз без основания.

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

Быстрый тест по теме

Быстрая самопроверка

~ 2 мин4 вопроса

Вопрос 1 / 4

Вопрос 1 из 4 · инвариант

Что обязательно входит в доказательство корректности цикла?

Главное за минуту

Главное

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