Применение инварианта цикла
Инвариант цикла помогает доказать, что циклический алгоритм работает правильно. Идея проста: найти свойство переменных или состояния исполнителя, которое сохраняется после каждой итерации, а затем использовать его для вывода о результате.
Перед изучением этой бет полезно повторить доказательство инварианта: там разбираются начальный шаг, сохранение свойства и завершение. Здесь внимание сосредоточено на применении уже найденного инварианта к алгоритмам, в том числе к задачам экзамена.
Идея применения инварианта
Цикл изменяет значения переменных много раз, поэтому проверять все итерации по отдельности неудобно. Вместо этого рассматривают состояние перед очередной итерацией. Если некоторое утверждение истинно в этот момент и после выполнения тела цикла остаётся истинным, оно является инвариантом.
Инвариант цикла — утверждение о переменных, элементах массива или положении исполнителя, которое истинно перед первой итерацией и сохраняется после каждой выполненной итерации.
Чтобы применить инвариант, нужно связать его с условием окончания цикла. Сам по себе инвариант описывает все промежуточные состояния, а условие завершения добавляет информацию о том, что цикл уже остановился.
Если инвариант верен перед началом цикла, сохраняется после каждой итерации, а при завершении цикла вместе с условием выхода влечёт требуемое свойство, то алгоритм выдаёт правильный результат.
Здесь \(I\) — инвариант, \(B\) — условие продолжения цикла, \(k\) — число итераций, а \(R\) — требуемый результат. В задачах часто достаточно не писать строгое доказательство, а распознать, что именно хранит переменная после нескольких повторений.
Как выбрать подходящий инвариант
Искомое свойство обычно связано с назначением переменной. Если переменная накапливает сумму, инвариант описывает сумму уже обработанных элементов. Если хранится максимум или минимум, инвариант говорит, что найденное значение является экстремумом на обработанном участке. В алгоритмах исполнителя инвариантом может быть положение, пройденное расстояние или форма обработанной части рисунка.
- Определите, что изменяется на каждой итерации: счётчик, сумма, границы участка, текущий максимум или состояние исполнителя.
- Разделите данные на обработанную и необработанную части.
- Сформулируйте, что уже известно об обработанной части.
- Проверьте начальное состояние: обработанная часть может быть пустой или состоять из бір элемента.
- После завершения цикла подставьте условие выхода в инвариант.
| Тип алгоритма | Возможный инвариант | Что следует при завершении |
|---|---|---|
| Суммирование | \(s\) равна сумме обработанных элементов | \(s\) равна сумме всех элементов |
| Іздеу максимума | \(m\) — максимум обработанной части | \(m\) — максимум всего массива |
| Подсчёт | \(c\) равен числу элементов с нужным свойством | \(c\) — искомое количество |
| Движение исполнителя | Первые \(t\) команд выполнены, состояние описано переменными | Получено конечное положение или рисунок |
При анализе положения исполнителя полезно отдельно фиксировать его координаты и направление. Страница состояние исполнителя объясняет, какие данные полностью описывают момент выполнения команды, а положение исполнителя помогает не путать координаты с направлением.
Разобранный пример: сумма элементов
Рассмотрим алгоритм, который проходит по элементам массива \(a_1, a_2, \dots, a_n\) и накапливает их сумму. Перед циклом \(s=0\), на каждой итерации к \(s\) прибавляется очередной элемент. Какое утверждение можно использовать как инвариант?
1s := 0 2for i := 1 to n do 3 s := s + a[i]
Инвариант здесь формулируется так: перед итерацией с номером \(i\) переменная \(s\) равна сумме элементов \(a_1,\dots,a_{i-1}\). Иногда в ответах используют эквивалентную формулировку: после обработки первых \(i\) элементов \(s\) равна их сумме. Важно согласовать формулировку с моментом, который рассматривается — до или после тела цикла.
В цикле после обработки первых \(i\) элементов переменная \(m\) хранит максимум этих элементов. Что будет дұрыс после окончания цикла, если обработаны все \(n\) элементов?
Цикл с условием и границами
В цикле вида «пока условие истинно» число итераций заранее может быть неизвестно. Например, алгоритм увеличивает \(x\) на единицу, пока \(x<N\). Инвариантом может быть связь между счётчиком итераций \(t\) и текущим значением: \(x=x_0+t\). При остановке известно \(x\ge N\), и из инварианта можно получить границу для \(t\).
В задачах на деление и остаток часто сохраняется не точное значение, а свойство вида \(x\equiv r\pmod m\). Если к числу каждый раз прибавляют величину, кратную \(m\), остаток по модулю \(m\) не меняется.
Не путайте инвариант с условием цикла: условие может меняться и исчезает при остановке, а инвариант сохраняется. Также важно проверить начальные значения и границы индексов.
Границы применимости
Инвариант доказывает корректность только при выполнении всех предположений: правильной инициализации, сохранении на каждом шаге и достижении условия завершения. Если цикл может выполняться бесконечно, инвариант описывает его состояния, но не доказывает получение ответа.
Проверь себя
Главное
- Инвариант — свойство, истинное перед началом цикла и сохраняющееся после каждой итерации.
- Для доказательства результата нужно объединить инвариант с условием завершения.
- В суммировании инвариант описывает сумму обработанной части.
- При отладке ищут первую итерацию, после которой инвариант нарушился.
- Инвариант сам по себе не доказывает завершение цикла и его скорость.