Информатика · объяснение и практика
Как инвариант объясняет правильность накопления суммы
Как инвариант объясняет цикл накопления суммы: начальное состояние, сохранение свойства одним шагом и вывод после конечного числа итераций.

В теме Переменные, ветвления, циклы и функции · Учебная карта
Главная мысль
Инвариант цикла — утверждение о состоянии, которое истинно в выбранный момент каждой итерации. Для накопления суммы удобно связывать значение аккумулятора с уже обработанной частью. Нужно проверить начальный случай, сохранение на шаге и отдельно завершение цикла; одного удачного примера недостаточно.
Как назвать уже выполненную часть работы
В Python переменную total сначала делают равной нулю, затем для k из range(1, n + 1) выполняют total += k. Пусть уже обработаны числа от одного до m. Полезный инвариант говорит: total равен сумме именно этих чисел. Он описывает связь состояния с количеством выполненных шагов, а не просто желание получить правильный ответ в конце.
До первой итерации обработанных чисел нет, поэтому m равен нулю, а сумма пустого набора принимается равной нулю. Начальное total = 0 удовлетворяет свойству. Если по ошибке записать начальное значение один, инвариант нарушится ещё до работы цикла. Дальнейшее аккуратное прибавление чисел не исправит исходную лишнюю единицу: она сохранится в результате.
Почему один шаг сохраняет утверждение
Предположим, перед очередным шагом total действительно содержит сумму первых m чисел. Следующим обрабатывается m + 1. Команда прибавляет ровно это число, поэтому после неё total равен сумме от одного до m + 1. Утверждение восстановлено для увеличившейся обработанной части. Так обосновывается каждый шаг независимо от конкретного большого значения n.
Для n = 4 состояния аккумулятора после шагов равны одному, трём, шести и десяти. Это пример работы общего рассуждения, а не его замена. Если один из шагов пропускается из-за неверной границы, аккумулятор по-прежнему может правильно описывать фактически обработанную часть, но эта часть уже не совпадёт с требуемыми числами до n. Поэтому границы цикла входят в доказательство задачи.
Пример
Начало total = 0; после k = 1, 2, 3, 4 получаем total = 1, 3, 6, 10.
Каждое состояние равно сумме уже пройденных чисел. Последняя итерация включает четвёрку, потому что правая граница range равна пяти.
Как связать свойство с завершением
Сам инвариант не доказывает, что произвольный цикл остановится. В рассматриваемом коде range задаёт конечное число шагов при неотрицательном целом n. После их выполнения обработаны все числа от одного до n. Совместив этот факт с инвариантом, получаем требуемую сумму. Для n = 0 цикл пуст, и нулевое начальное значение уже является правильным ответом.
Момент проверки свойства нужно выбирать последовательно. Можно формулировать его перед итерацией или после неё, но тогда номера уже включённых чисел будут различаться. Не подменяйте число обработанных элементов текущим значением переменной автоматически. Например, после Python-цикла переменная k не обязана принимать значение n + 1 только потому, что оно служило исключённой границей.
Полезный инвариант достаточно конкретен, чтобы из него можно было вывести ответ. Фраза «цикл всё делает правильно» ничего не сообщает о состоянии и не позволяет проверить отдельный шаг. Связь аккумулятора с обработанной частью пригодится и для других алгоритмов: количества найденных элементов, максимума пройденного префикса или построенной части результата.
От чтения к действию
А теперь — вы
Частые вопросы
Инвариант должен содержать готовый ответ?
Нет. Обычно он описывает уже обработанную часть. Готовый ответ получается после соединения этого свойства с фактом завершения всей требуемой обработки.
Достаточно ли доказать сохранение, не проверяя начало?
Нет. Свойство может сохраняться при каждом шаге, но изначально быть ложным. Поэтому нужна отдельная проверка начального состояния.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как найти ошибку на границе цикла
Как находить ошибку на один шаг в цикле Python: включённое начало, исключённая правая граница range и допустимые индексы списка.
Открыть темуКак линейный поиск обрабатывает найденный и отсутствующий элемент
Как линейный поиск проверяет элементы по порядку, возвращает первую подходящую позицию и обозначает отсутствие так, чтобы не спутать его с индексом ноль.
Открыть тему