Тапсырмалар № 22, 23 · ЕГЭ

Построение инварианта цикла

Как найти и доказать свойство, сохраняющееся при выполнении цикла

6 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

Что такое инвариант цикла

Перед анализом инварианта полезно повторить условие цикла: оно определяет, когда выполняются итерации и в какой момент цикл останавливается. Также нужно отдельно рассматривать тело цикла, потому что именно оно изменяет переменные.

Определение

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

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

Правило доказательства инварианта

Чтобы доказать, что свойство \(P\) является инвариантом, проверьте три пункта: 1) инициализация — \(P\) истинно до начала цикла; 2) сохранение — если \(P\) истинно до итерации, то после выполнения тела оно также истинно; 3) завершение — вместе с условием остановки инвариант даёт требуемый результат.

\[P_0 \Rightarrow P_1 \Rightarrow P_2 \Rightarrow \dots \Rightarrow P_k\]

Здесь \(P_i\) означает, что инвариант верен после \(i\) итераций. Если доказаны переходы от каждого состояния к следующему, свойство верно на всём пути выполнения цикла.

Как строить инвариант

Начинайте не с красивой формулы, а с вопроса: что уже обработано к этому моменту? Номер итерации, границы отрезка, сумма, произведение, количество найденных объектов или остаток от деления часто становятся частью инварианта.

Определите, какая часть данных обработана после \(i\) итераций.
Запишите смысл основных изменяемых переменных словами.
Составьте равенство или неравенство между переменными и обработанной частью данных.
Проверьте инвариант в начальном состоянии.
Проследите одну условную итерацию и убедитесь, что свойство сохраняется.
Используйте условие завершения, чтобы получить ответ.

Для цикла со счётчиком \(i\) часто подходит схема «после \(i\) қадам обработаны элементы с номерами от \(1\) до \(i\)». Если цикл начинается с другого значения или изменяет счётчик на несколько единиц, границы нужно записывать точно, а не угадывать по привычной форме.

\[S_i = \sum_{j=1}^{i} a_j, \qquad S_0=0\]

Для накопления суммы инвариант обычно имеет вид \(S=S_i\). Для поиска максимума это может быть утверждение «\(m\) — максимум среди первых \(i\) элементов», а для подсчёта — «\(c\) равно количеству элементов с нужным свойством среди первых \(i\) элементов».

Приём

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

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

Цикл последовательно прибавляет к \(S\) значения \(a_1,a_2,\dots,a_n\), начиная с \(S=0\). Какой инвариант наиболее естественен после \(i\) итераций?

Разобранный пример: сумма квадратов

Рассмотрим фрагмент алгоритма. Требуется понять, какое значение будет выведено при \(n=4\), и обосновать его с помощью инварианта.

Псевдокод

1s := 0
2for i := 1 to n do
3    s := s + i * i
4print(s)

№

Идея шешімдер

После \(i\) итераций переменная \(s\) должна содержать сумму квадратов первых \(i\) натуральных чисел. Это и будет инвариантом.

До первой итерации обработано ноль чисел, а начальное значение суммы равно нулю.

\(\displaystyle i=0:\quad s=0=\sum_{j=1}^{0}j^2\)

Предположим, что перед очередной итерацией уже выполнено \(i-1\) қадам.

\(\displaystyle s=\sum_{j=1}^{i-1}j^2\)

Тело цикла прибавляет квадрат текущего нөмір \(i\).

\(\displaystyle s_{new}=\sum_{j=1}^{i-1}j^2+i^2=\sum_{j=1}^{i}j^2\)

Значит, после итерации свойство сохраняется.

\(\displaystyle P(i-1)\Rightarrow P(i)\)

При завершении цикла \(i=n=4\), поэтому в сумме находятся квадраты от 1 до 4.

\(\displaystyle s=1^2+2^2+3^2+4^2=1+4+9+16=30\)

Показать трассировку Шешім

Момент	i	s	Инвариант
До цикла	0	0	\(s=\sum_{j=1}^{0}j^2\)
После 1-й итерации	1	1	\(s=1^2\)
После 2-й итерации	2	5	\(s=1^2+2^2\)
После 3-й итерации	3	14	\(s=1^2+2^2+3^2\)
После 4-й итерации	4	30	\(s=1^2+2^2+3^2+4^2\)

Главное в примере — не вычисление четырёх чисел, а связь между номером итерации и содержимым переменной \(s\). Такой подход особенно полезен в тапсырмаларда, где число повторений велико или цикл содержит ветвление.

Инвариант и условие завершения

Сам по себе инвариант не сообщает, когда цикл остановится. Он описывает только состояния, которые могут возникать после итераций. Чтобы получить результат, нужно соединить инвариант с отрицанием условия цикла. Например, если цикл выполняется, пока \(i\le n\), то после окончания обычно известно \(i=n+1\) или другая граница, зависящая от способа изменения счётчика.

Рассмотрим цикл, который уменьшает число \(x\) на 2, пока \(x>0\). Инвариантом является сохранение чётности: если начальное \(x\) чётно, то после каждого вычитания 2 значение остаётся чётным. Если начальное число нечётно, чётность также не изменится. Условие завершения добавляет информацию: остановка происходит при \(x\le0\), но конкретное конечное значение зависит от начального числа.

\[x_{k+1}=x_k-2 \quad\Rightarrow\quad x_{k+1}\equiv x_k \pmod 2\]

В задачах с несколькими переменными инвариант может быть составным: например, \(x+y=C\), \(x\ge0\) и «\(x\) — количество обработанных элементов». Нужно проверять каждую часть свойства после выполнения всего тела, включая условия ветвления внутри цикла.

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

1. Проверяют свойство только на нескольких примерах, но не доказывают переход. 2. Считают инвариантом условие цикла: условие может стать ложным и потому не обязано сохраняться. 3. Не учитывают начальную инициализацию переменных. 4. Путают состояние до итерации и после неё. 5. Игнорируют одну из ветвей тела. 6. Записывают слишком слабое утверждение, например «\(s\) — число», которое ничего не говорит о результате.

Запомните

Инвариант отвечает на сұрақ: что уже дұрыс после любого числа выполненных итераций? Условие цикла отвечает на другой сұрақ: нужно ли выполнять следующую итерацию? Не смешивайте эти роли.

Сложные случаи и проверка шешімдер

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

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

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

Жылдам тест по теме

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

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

Вопрос 1 / 4

Вопрос 1 из 4 · Инициализация

Что обязательно проверяют первым при доказательстве инварианта?

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

Итоги

Инвариант — свойство, истинное до цикла и после каждой его итерации.
Для доказательства нужны инициализация, сохранение и использование условия завершения.
Жиі кездесетіні инвариант описывает обработанную часть данных: сумму, максимум, количество или границы.
Вложенные циклы и ветвления требуют отдельной проверки соответствующих переходов.
Трассировка помогает найти инвариант, но несколько примеров не заменяют доказательство.