Оператор цикла с постусловием

Цикл с постусловием – это управляющая конструкция, в которой тело выполняется минимум один раз, а проверка условия продолжения/завершения происходит после тела. Классические формы:

• do { S } while (C); – продолжать, пока условие истинно (C/C++/C#/Java);

• repeat S until E; – завершить, когда условие истинно (Pascal).

С точки зрения экзаменационной математики алгоритмов этот цикл важен потому, что:

1. гарантирует как минимум одну итерацию (многие задачи это требуют);

2. естественно выражает схемы «читать → обрабатывать → проверять признак конца»;

3. тренирует строгость в инвариантах, вариантах и в преобразовании циклов к эквивалентным формам.

Формальная семантика и нотации

Пусть S – тело, C – булево условие «продолжать», E – булево условие «закончить». Тогда:

• Форма «продолжать, пока» (C-стиль):

• do S while (C);

Эквивалент по выполнению (без побочных эффектов в проверке):

S;

while (C) do S;

Минимум одна итерация гарантирована. Количество проверок равно числу выполнений тела.

• Форма «повторять до» (Pascal-стиль):

• repeat S until E;

Эквивалент:

S;

while (not E) do S;

Связь между формами: do S while (C); ⇔ repeat S until (not C);.

Базовые свойства:

• Минимальное число итераций: N ≥ 1.

• Условие проверяется после выполнения S.

• Для do … while (C) последняя проверка возвращает false. Для repeat … until (E) последняя проверка возвращает true.

Корректность: инвариант и завершимость

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

   Инвариант – утверждение I, истинное перед и после каждой итерации тела. Для постусловия удобно формулировать так:

   • Начало: после первой S инвариант должен стать истинным.
     Формально: если предусловие P истинно, то выполнение S один раз приводит к истинности I.

   • Сохранение: I ∧ C ⇒ [S]I для формы do … while (C) или I ∧ (not E) ⇒ [S]I для repeat … until (E).

   • Завершение: выход даёт постусловие Q, например I ∧ (not C) ⇒ Q или I ∧ E ⇒ Q.

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

   Для доказательства завершимости укажите вариант V – целочисленную величину, которая:

   • ограничена снизу: V ≥ 0;

   • строго убывает на каждой итерации в ветви продолжения: I ∧ C ⇒ V' < V.

   Это гарантирует конечность числа итераций.

Оценка стоимости (асимптотика)

Пусть t_body – время одной итерации тела, t_check – время проверки условия. Тогда при N итерациях:

T(N) = N * t_body + N * t_check

(последняя проверка тоже выполняется). В асимптотике: T(N) = Θ(N).

Языковые формы и эмуляция

• C/C++/Java/C#:

• do {

•     S;

• } while (C);

• Pascal:

• repeat

•   S;

• until E;

• Python (эмуляция, т.к. do-while отсутствует):

• while True:

•     S

•     if not C:   # эквивалентно 'until C' для Pascal

•         break

Важно: перевод между формами требует аккуратности с логическим отрицанием (C ↔ not E) и с побочными эффектами в C/E.

Типовые шаблоны применения

1. Цикл с «сторожевым» значением (sentinel): читать минимум один элемент, остановиться на «0», «END», EOF и т.п.

2. Меню пользователя: показать меню, хотя бы раз обработать выбор, затем продолжать по желанию.

3. Модели с итерационными уточнениями: повторять шаг до достижения точности |x_{k+1} − x_k| ≤ ε.

4. Непустые случаи: корректно обрабатывать «крайние» входы, где миттельная форма while дала бы 0 итераций (например, число 0 при подсчёте цифр).

Правила «чистого» использования

Правило 1 (минимум одна итерация – сознательно). Используйте цикл с постусловием, когда первая итерация нужна независимо от условия.

Правило 2 (единая полярность). Для repeat … until условие – это условие завершения, а для do … while – условие продолжения. Не путайте: until E ⇔ while (not E).

Правило 3 (инвариант после первой S). Инвариант должен стать истинным уже после первой S; иначе док-во корректности будет неполным.

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

Правило 5 (вход/выход). Считать входные данные → обработать → проверить – честно оформляйте в теле. Не превращайте проверку в чтение (EOF-зависимые ловушки).

Правило 6 (границы счётчиков). При «пороговых» критериях (≥, >, ≤, <) явно фиксируйте включённость границы. Записывайте неравенства в едином стиле.

Типичные ошибки

• Перепутаны while (C) и until (E): неверная полярность → бесконечный цикл или нулевая итерация в переводе.

• Двойное чтение ввода (в теле и в проверке) → пропуски элементов.

• Использование while вместо do … while в задачах с обязательной первой обработкой (например, n = 0 при подсчёте цифр).

• Порча инварианта внутри тела (изменение инвариантной структуры без восстановления).

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

На ЕГЭ регулярно встречаются:

• анализ фрагмента, определение количества итераций и результата;

• аккуратный подсчёт сумм/количеств до «сторожа»;

• перевод псевдокода между стилями (repeat … until ↔ while … do);

• доказательство завершимости (вариант), формулировка инварианта;

• работа с граничными случаями (минимум одна итерация).

Иллюстративные примеры

1. Подсчёт цифр числа (корректен для n = 0)
   

   Идея: у 0 должна получиться 1 цифра – нужен цикл с постусловием.

   • C/C++:

   int digits(unsigned int n){

       int k = 0;

       do {

           k++;

           n /= 10;

       } while (n > 0);

       return k;

   }

   • Pascal:

   function Digits(n: LongInt): LongInt;

   var k: LongInt;

   begin

     k := 0;

     repeat

       k := k + 1;

       n := n div 10;

     until n = 0;

     Digits := k;

   end;

2. Сумма до «сторожа» (0 завершает ввод)
   

   • C++:

   long long sum_sentinel() {

       long long s = 0, x;

       do {

           std::cin >> x;

           s += x;

       } while (x != 0);

       return s - 0; // последний ноль не влияет

   }

   • Pascal:

   function SumUntilZero: Int64;

   var s, x: Int64;

   begin

     s := 0;

     repeat

       readln(x);

       s := s + x;

     until x = 0;

     SumUntilZero := s;

   end;

3. Эмуляция в Python
   

   def menu_loop():

       while True:

           print(«1) суммировать  2) выйти»)

           choice = input().strip()

           if choice == «2»:

               break

           elif choice == «1»:

               print(«sum = ...»)

           else:

               print(«ошибка ввода»)

Мини-шпаргалка 

• Эквивалентность форм:

• do S while (C);   ⇔   S; while (C) do S;

• repeat S until E; ⇔   S; while (not E) do S;

• Минимум одна итерация:

• N ≥ 1

• Стоимость:

• T(N) = N * t_body + N * t_check

• Инвариант и завершение (для do … while):

• P ⇒ [S]I

• I ∧ C ⇒ [S]I

• I ∧ (not C) ⇒ Q

• и существует вариант V ≥ 0 со свойством I ∧ C ⇒ V' < V.

Пять упражнений (академический формат)

Упражнение 1. Перевод форм
Дан фрагмент (Pascal):

repeat

  s := s + a[i];

  i := i + 1;

until (i > n) or (a[i] < 0);

a) Запишите эквивалент на C++ с do … while.
b) Перепишите как цикл while без потери смысла (с сохранением «минимум одна итерация»).

Упражнение 2. Подсчёт цифр с граничным случаем
Определите, что выведет процедура при n = 0:

k := 0;

repeat

  k := k + 1;

  n := n div 10;

until n = 0;

writeln(k);

a) Объясните, почему решение корректно именно для постусловия.
b) Докажите инвариант: «после t итераций k = t и n – это исходное число после t делений на 10».

Упражнение 3. Сентинел и корректный ввод
Нужно прочитать последовательность целых, завершённую -1, и вывести среднее арифметическое без учёта -1.
a) Напишите цикл с постусловием (любая из форм).
b) Перечислите 2 типичные ошибки с вводом/подсчётом.
c) Укажите инвариант и вариант цикла.

Упражнение 4. Критерий точности
Итерационный процесс задаётся x_{k+1} = f(x_k). Останов критерий – |x_{k+1} - x_k| ≤ ε.
a) Запишите схему с постусловием.
b) Объясните, как выбрать начальное x_0, чтобы первая итерация была осмысленной.
c) Обоснуйте завершимость при сжатии f (существование предела и достижение критерия).

Упражнение 5. Анализ сложности
Дан цикл:

int i = 1, s = 0;

do {

    s += i*i;

    i++;

} while (i <= n);

a) Выразите число итераций через n.
b) Запишите суммарную трудоёмкость в виде T(n) = n * t_body + n * t_check.
c) Найдите замкнутую форму суммы s = 1^2 + 2^2 + ... + n^2 (подсказка: s = n(n+1)(2n+1)/6), и укажите асимптотику.

Заключение

Цикл с постусловием – не «экзотика», а строгий инструмент, который:

• обеспечивает корректную обработку обязательной первой итерации;

• естественно выражает задачи со сторожевым значением и критерием точности;

• требует дисциплины в инвариантах, вариантах и полярности условий.

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