Циклы с переадресацией

Циклы с переадресацией – обобщающее название для всех итерационных конструкций, в которых поток управления перенаправляется (переадресуется) из середины тела цикла:

• на продолжение следующей итерации (continue, переход к проверке условия),

• на досрочное завершение цикла (break/выход из цикла),

• на выход из подпрограммы (return) изнутри цикла,

• на метку (неструктурированный переход goto/метки в языках с поддержкой),

• на внешний уровень (labelled break/исключение).

В экзаменационном контексте ЕГЭ по информатике такие конструкции важны по двум причинам:

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

2. они требуют строгой работы с инвариантами и границами, иначе легко допустить логическую ошибку (пропуск элемента, бесконечный цикл, нарушение постусловия).

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

Рассмотрим цикл с предусловием while C do S. Его классическая семантика:

• на входе проверяется C; если C=false, цикл не выполняется и управление передаётся дальше;

• если C=true, выполняется тело S, после чего повторная проверка C.

Переадресации потока внутри S:

• continue – немедленный переход к завершению текущей итерации и повторной проверке C;

• break – немедленный выход из цикла (к коду «после цикла»);

• return v – выход из подпрограммы с результатом v (цикл прекращается как побочный эффект);

• goto L – переход к метке L (может быть внутри/вне цикла);

• «меточный» break outer (в языках Java-стиля) – выход из внешнего цикла.

Эквивалентности (для рассуждений):

• continue эквивалентен goto Head, где Head – «точка проверки условия цикла»;

• break эквивалентен goto After, где After – «точка после цикла».

Эти эквивалентности удобно использовать при доказательствах корректности и при переводе кода в структурную форму.

Инварианты и контракты при переадресации

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

   Инвариант I – утверждение, которое должно быть истинным каждый раз в точке входа в тело (после проверки условия) и сохраняться любой исполняемой ветвью тела. При наличии continue/break требуется:

   • Сохранение для continue:

   • I ∧ C ∧ (ветвь с continue) ⇒ I   (в точке начала следующей итерации)

   То есть перед переходом к следующей проверке C инвариант обязан оставаться истинным.

   • Завершение для break:

   • I ∧ (ветвь с break) ⇒ Q

   где Q – постусловие цикла/программы. При выходе «вне проверки C» именно I должен вместе с фактами ветви гарантировать Q.

   • Контракт частичной корректности цикла while C do S:

   • {P} while C do S {I ∧ ¬C}   при условии:

   •  (1) P ⇒ I

   •  (2) I ∧ C ⇒ [S]I          (сохранение инварианта всеми ветвями, включая continue)

   Для break часть постусловия формируется в точке выхода: I ∧ BreakFacts ⇒ Q.

2. Вариант (функция спуска)
   

   Для гарантии завершения определяют вариант V ≥ 0, который строго убывает при каждой итерации, которая возвращается к проверке условия:

   I ∧ C ∧ (ветвь без break/return) ⇒ V' < V

   Если в ветви стоит break/return, завершение обеспечивается непосредственно.

Классификация «циклов с переадресацией»

1. С отбрасыванием элементов (filter-continue): часть входных данных пропускается с помощью continue.

2. С досрочным выходом (early-exit): остановка поиска по «сторожу», найденному элементу или нарушению условия – break/return.

3. Многоуровневый выход: выход из внутреннего цикла во внешний (labelled break/флаг/исключение).

4. Эмуляция do-while: while true + if not C then break.

5. Неструктурированные (goto): переводятся в структурные формы для доказуемости.

Правила корректного использования

Правило 1 (Инвариант до и после каждой ветви). Любая ветвь тела цикла, ведущая к continue, обязана приводить состояние к удовлетворяющему инварианту I.

Правило 2 (Завершение при break). Локальные факты ветви, ведущей к break, вместе с I должны давать постусловие Q:

(I ∧ Facts_branch) ⇒ Q

Правило 3 (Единая точка изменения счётчиков). Если итерационный счётчик/указатель обновляется в конце тела, обеспечить его обновление во всех ветвях, иначе возможен бесконечный цикл (особенно при continue).

Правило 4 (Предусловия для операций). Все потенциально опасные операции (деление, обращение к массиву, доступ к файлу) должны быть защищены условием перед переадресацией (иначе можно «перескочить» проверку).

Правило 5 (Многоуровневый выход без goto). Предпочтительно:

• либо меточный break (если язык поддерживает),

• либо флаг и проверка внешним циклом,

• либо вынос логики в функцию и return при срабатывании условия,

• либо исключение (для действительно исключительных ситуаций).

Правило 6 (Эмуляция post-condition цикла). Для «выполнить хотя бы раз» используйте:

while true:

    S

    if not C: break

и докажите сохранение I перед повторной проверкой.

Правило 7 (Запрет «скрытых» goto). Не смешивать break/continue с побочными эффектами, которые меняют логику проверки: читабельность и доказуемость важнее краткости.

Алгоритмические шаблоны

1. Фильтрация с continue (pattern «пропусти и иди дальше»)
   

   I: s = сумма принятых элементов; count = их число

   for x in поток:

       if not ПРИНИМАТЬ(x): continue     # переадресация к следующей итерации

       s := s + f(x); count := count + 1 # I сохраняется

   Чётко фиксируйте, какие переменные инварианта остаются неизменными при continue.

2. Поиск с досрочным выходом
   

   for i := 1..n:

       if a[i] = x: found := true; break

   I: found ⇒ существование a[1..i] = x; ¬found ⇒ в a[1..i] нет x

   Q: found ⇒ ∃j: a[j]=x;  ¬found ⇒ ∀j: a[j]≠x

3. Многоуровневый выход без goto (функция + return)
   

   function exists_pair(A, n, K):

       for i := 1..n:

           for j := i+1..n:

               if A[i]+A[j] = K: return true   # выход из обоих циклов

       return false

   Контракт функции – логическое постусловие: возвращает true ⇔ пара существует.

4. Эмуляция do-while через while-true + break
   

   while true:

       S

       if not C: break

   Инвариант I должен быть восстановлён к моменту проверки C каждый раз.

5. Сканирование до «сторожа» (sentinel + break)
   

   sum := 0

   while read(x):

       if x = 0: break

       sum := sum + x

   Q: суммированы все элементы до первого нуля

Анализ сложности и корректности

• Асимптотика не меняется от наличия break/continue в худшем случае;

• Лучший/средний случай могут улучшаться (ранний выход при нахождении/нарушении);

• Корректность обеспечивается через I и контракты ветвей:

• при continue – сохранение I,
• при break – I ∧ Facts ⇒ Q,
• при return – постусловие функции/процедуры.

Типичные ошибки и профилактика

1. Забытый инкремент индекса при continue ⇒ бесконечный цикл.

2. Нарушение инварианта в ветви continue (например, не сброшен временный флаг).

3. Лишний код после break/return (недостижимый, путает логику).

4. Многоуровневые goto без нужды ⇒ трудно доказать корректность.

5. Логика проверки «после» continue – код никогда не выполнится.

6. Неполная обработка краевых случаев (пустые коллекции, первый элемент сразу ведёт к break).

Связь с ЕГЭ по информатике

• В задачах часто нужно смоделировать исполнение фрагмента с break/continue и посчитать количество итераций/вывод.

• Важны инварианты: многие ответы требуют доказать, что «к моменту выхода» накопленная величина/флаг отражают истинное свойство данных.

• Перевод форм: «цикл с постусловием» ↔ while true + break (правильный перенос условий важен для баллов).

• Краевые случаи: пустой ввод, первый/последний элемент – частые «ловушки».

Мини-шпаргалка (копируемые формулы/шаблоны)

Контракт while с инвариантом:

{P} while C do S {I ∧ ¬C}

где  P ⇒ I  и  I ∧ C ⇒ [S]I

Ветвь с break:

(I ∧ Facts_branch) ⇒ Q

Эмуляция do-while:

while true:

    S

    if not C: break

Флаг и досрочный выход:

found := false

for ...:

    if cond: found := true; break

Пять упражнений 

Упражнение 1. Инвариант при continue
Дан фрагмент:

sum := 0; cnt := 0

for i := 1..n:

    if a[i] < 0 then continue

    sum := sum + a[i]

    cnt := cnt + 1

a) Сформулируйте инвариант I(t) после t рассмотренных элементов.
b) Докажите сохранение I в ветви continue.
c) Выведите постусловие: cnt – число неотрицательных элементов, sum – их сумма.

Упражнение 2. Досрочный выход и корректность
Фрагмент поиска первого нуля:
pos := 0

for i := 1..n:

    if a[i] = 0 then pos := i; break

a) Запишите I: «в a[1..i-1] нет нулей; pos=0».
b) Докажите, что при выходе pos=0 ⇔ нулей нет; иначе pos – минимальный индекс нуля.
c) Укажите сложность в лучшем/худшем/среднем случаях.

Упражнение 3. Многоуровневый выход без goto

Задача: определить, существует ли триада индексов i<j<k, где a[i]<a[j]<a[k].
a) Предложите функцию exists_increasing_triplet(a) с досрочными return.
b) Сформулируйте постусловие функции и докажите его.
c) Обсудите, почему goto здесь не нужен и ухудшил бы доказуемость.

Упражнение 4. Эмуляция post-condition

Построить цикл «выполнить хотя бы раз»: вводить числа и суммировать, пока они положительны.
a) Запишите решение через while true + break.
b) Сформулируйте инвариант и докажите, что при выходе сумма содержит только положительные слагаемые.
c) Покажите, как добавить защиту от переполнения суммы (предусловие/проверка).

Упражнение 5. Ошибка «забытый инкремент»

Фрагмент:

i := 1; s := 0

while i ≤ n do

    if a[i] mod 2 = 0 then continue

    s := s + a[i]

    i := i + 1

a) Объясните, почему возможен бесконечный цикл.
b) Исправьте код двумя способами (инкремент до continue; или перестроить условие).
c) Запишите инвариант исправленного варианта и докажите завершимость.

Заключение

Циклы с переадресацией – мощный, но требующий дисциплины инструмент. Их корректное применение опирается на строгие инварианты, аккуратное обращение с ветвями continue/break/return и ясные контракты («что истинно при выходе»). Для ЕГЭ владение этими принципами позволяет уверенно анализировать код с ранним выходом и пропуском элементов, избегать ловушек с границами и бесконечными циклами и формально обосновывать ответы – то есть стабильно набирать максимальные баллы в задачах на алгоритмы и программирование.