ЕГЭОГЭ
Задания № 6, 8 · ЕГЭ

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

Как формулируют свойство, сохраняющееся в цикле
2 мин чтенияСложность: Обновлено 29 сентября 2026

Инвариант цикла — это утверждение, которое остаётся истинным перед каждой итерацией цикла. Он помогает описать, что сохраняется во время выполнения [[cycle-algorithm:циклического алгоритма]], и используется для доказательства его правильности.

Инвариант цикла
Утверждение о значениях переменных и состоянии алгоритма, истинное перед началом цикла и перед каждой его итерацией, если цикл выполняется.

Как записывают инвариант

Инвариант обычно обозначают буквой \(P\). Для цикла важно проверить три свойства: \(P\) истинно до первой итерации; если \(P\) истинно перед итерацией, то оно остаётся истинным после неё; когда цикл заканчивается, инвариант вместе с условием завершения позволяет сделать вывод о результате.

\[P_{0}\ \text{истинно},\qquad P_{i}\Rightarrow P_{i+1}\]

Первое свойство называют инициализацией, второе — сохранением инварианта. Последний шаг связан с [[invariant-proof:доказательством инварианта]] и завершением цикла: сам по себе инвариант не гарантирует, что цикл когда-нибудь остановится.

№
Пример: сумма первых чисел

Рассмотрим цикл, который последовательно складывает числа \(1,2,\ldots,n\). Перед каждой итерацией можно утверждать: «в переменной \(s\) хранится сумма уже обработанных чисел». В начале обработанных чисел нет и \(s=0\). После добавления очередного числа утверждение сохраняется. После обработки всех чисел получаем \(s=1+2+\cdots+n\).

!
Не путайте с условием цикла

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

Проверьте себя

Какое утверждение может быть инвариантом цикла поиска максимума в первых \(i\) элементах массива?

Зачем нужен инвариант

Инвариант позволяет объяснить работу цикла не перебором всех итераций, а общим рассуждением. В задачах на трассировку полезно искать, какая величина уже вычислена или какие элементы обработаны. Для полного доказательства правильности нужно также обосновать [[loop-termination:завершение цикла]].

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

Главное

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