Итерационные циклы

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

Теоретические основы

Математическая модель: предусловие, инвариант, вариант

Корректность циклов формализуется тройкой (предусловие, инвариант, вариант):

• Предусловие – что истинно перед первым заходом в цикл.

• Инвариант цикла – утверждение, сохраняющееся после каждой итерации (например: «переменная best содержит максимум среди уже обработанных элементов»).

• Вариант (функция убывания) – величина, которая строго уменьшается на каждой итерации и ограничена снизу (гарантия завершения). Примеры: «оставшееся количество необработанных элементов», «длина ещё не проверённого суффикса», «расстояние между границами окна».

Классификация циклов

• Счётный цикл (for): число итераций известно заранее. Удобен для прохода по диапазону индексов и коллекциям.

• Цикл с предусловием (while): повторение, пока условие истинно. Число итераций заранее неизвестно; типично для чтения до конца файла, «пока не найдено».

• Цикл с постусловием (do … while / repeat … until): тело исполняется минимум один раз, затем проверяется условие остановки.

Семантика границ и шагов

При счётном переборе важно фиксировать:

• Диапазон: полуинтервал [L, R) (включая L, исключая R) или отрезок [L, R].

• Шаг: положительный/отрицательный, величина шага (1, 2, …).

• Направление: прямой (возрастание индексов) или обратный (для стабильных удалений из списков, обхода разрежённых структур).

Управляющие операторы

• break – немедленный выход из ближайшего цикла (фиксируйте инвариант после выхода!).

• continue – переход к следующей итерации, пропуская остаток тела.

• pass (в Python) – заглушка без действий.
  Используйте их экономно, чтобы не размывать инвариант.

Типовые алгоритмические паттерны

• Агрегирование: сумма/среднее/счётчик, аккумуляторы.

• Поиск экстремума: поддержание текущего min/max с инвариантом.

• Фильтрация: пересборка последовательности по предикату.

• Скользящее окно/два указателя: обработка подотрезков в линейное время.

• Вложенные циклы: полный перебор пар/троек; оценка O(n²)/O(n³) и способы уменьшения сложности (матем. преобразования, предварительные структуры данных).

Оценка сложности

• Один линейный цикл по n элементам: O(n) по времени, O(1) по памяти (если без вспомогательных структур).

• Два вложенных полных цикла: O(n²).

• Цикл с логарифмическим сокращением диапазона (while l < r: mid = ...): O(log n).

• На ЕГЭ важно уметь обосновывать порядок роста, опираясь на верхнюю границу количества итераций.

Типичные ошибки (и как их избежать)

• Off-by-one (на 1 больше/меньше): договоритесь о полуинтервале [L, R) и следуйте ему.

• Неизменяемое условие: следите, чтобы в теле цикла менялась величина, от которой зависит выход.

• Модификация коллекции при итерации: перебирайте копию индексов или идите в обратном направлении.

• Счётчик с плавающей точкой: аккуратно – ошибки округления могут нарушить условие выхода; лучше целочисленный счётчик и преобразование внутри.

• Неинициализированные аккумуляторы: минимум/максимум инициализируйте первым элементом или «мин/макс» границами типа.

Практические правила (памятка)

1. Сначала инвариант: сформулируйте, что должно быть истинно после каждой итерации – это направит код.

2. Выбор конструкции: «заранее известное число шагов» ⇒ for; «пока условие» ⇒ while; «минимум один раз» ⇒ do/while.

3. Единый стиль границ: используйте [0, n) и шаг +1, если нет причин иначе.

4. Перенос инвариантов вне цикла: вычисляйте неизменные выражения до цикла (оптимизация).

5. Ранний выход: используйте break для экономии времени, но фиксируйте и описывайте постусловие.

6. Проверка крайних случаев: пустая последовательность, n=1, все элементы равны/разные, отрицательные/нулевые значения.

Связь с подготовкой к ЕГЭ

Задачи ЕГЭ часто требуют:

• линейных проходов по данным с подсчётом/поиском (обработка последовательности из файла/потока);

• анализа подотрезков (максимальная длина, сумма, количество по условию);

• аккуратной работы с индексами и пределами;

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

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

Линейный проход с инвариантом (максимум):

best = None

for x in data:                # инвариант: best == max(data_processed)

    if best is None or x > best:

        best = x

Скользящее окно (сумма длины k):

k = 5

window_sum = sum(a[:k])

best = window_sum

for i in range(k, len(a)):    # инвариант: window_sum == sum(a[i-k+1:i+1])

    window_sum += a[i] - a[i-k]

    if window_sum > best:

        best = window_sum

Чтение «пока не конец»:

while True:

    line = f.readline()

    if not line:              # инвариант: обработаны все прочитанные строки

        break

    process(line)

Пять упражнений (с подробным разбором)

Упражнение 1. Линейная обработка и инвариант «счёт + максимум»
Условие. Дан поток целых чисел, оканчивающийся значением 0 (сам ноль в обработку не входит). Требуется посчитать: (1) количество положительных чисел; (2) максимальное из них или вывести «нет», если положительных нет. Вход подаётся построчно.

Требуется. Реализовать цикл и чётко сформулировать инвариант.

Решение (Python).

cnt_pos = 0

best = None

while True:

    x = int(input())

    if x == 0:

        break

    if x > 0:

        cnt_pos += 1

        if best is None or x > best:

            best = x

print(cnt_pos)

print(best if best is not None else "нет")

Инвариант: перед каждой проверкой условия x == 0 величины cnt_pos и best соответствуют количеству и максимуму среди уже прочитанных положительных элементов.
Сложность: O(n) по числу значений.
Типичные ошибки: забыть обнулить счётчик; сравнивать с >= (не критично), некорректно обработать ситуацию «нет положительных». 

Упражнение 2. Максимальная длина неубывающего фрагмента (скользящее окно)
Условие. По последовательности a[0..n-1] найдите длину самого длинного неубывающего непрерывного фрагмента (каждый следующий элемент ≥ предыдущего).

Требуется. Линейный алгоритм.

Решение.

best = 0

cur = 0

prev = None

for x in a:

    if prev is None or x >= prev:

        cur += 1

    else:

        cur = 1

    prev = x

    if cur > best:

        best = cur

print(best)

Инвариант: cur – длина текущего неубывающего хвоста, оканчивающегося в prev; best – максимум среди всех хвостов, рассмотренных ранее.
Сложность: O(n).
Замечание по ЕГЭ: типичный шаблон «один проход + счётчик текущего сегмента + глобальный максимум». 

Упражнение 3. Поразрядная обработка числа в десятичной записи (цикл while)
Условие. Для натурального числа N вычислить: (a) сумму цифр; (b) произведение нечётных цифр (если нечётных нет – вывести 0); (c) количество цифр 0.

Требуется. Использовать классическое деление/остаток и цикл while.

Решение.

N = int(input())

s = 0

prod_odd = 1

has_odd = False

cnt_zero = 0 

if N == 0:

    s = 0

    cnt_zero = 1

    prod_odd = 0

else:

    while N > 0:

        d = N % 10

        s += d

        if d == 0:

            cnt_zero += 1

        if d % 2 == 1:

            prod_odd *= d

            has_odd = True

        N //= 10

    if not has_odd:

        prod_odd = 0 

print(s, prod_odd, cnt_zero)

Инвариант: после каждой итерации учтены все уже «снятые» младшие цифры; суммы/произведения/счётчики отражают их агрегаты.
Крайние случаи: N=0 требует специальной обработки (ровно одна цифра «0»).
Сложность: O(k), где k – число цифр. 

Упражнение 4. Вложенные циклы и снижение сложности (делители числа)
Условие. Для положительного M требуется найти количество его делителей. Наивно – проверять все 1..M (O(M)). Улучшить до O(√M) и объяснить корректность.

Требуется. Переписать вложенный подход в один цикл по корням с учётом парности делителей.

Решение.

import math

M = int(input())

cnt = 0

r = int(math.isqrt(M))  # floor(sqrt(M))

for d in range(1, r + 1):

    if M % d == 0:

        cnt += 2  # d и M//d

if r * r == M:

    cnt -= 1      # если квадрат, центральный делитель посчитан дважды

print(cnt)

Идея: делители идут парами (d, M/d). Достаточно проверить d ≤ √M.
Сложность: O(√M) против O(M).
Инвариант: к моменту завершения цикла учтены все пары делителей с меньшим членом d в диапазоне [1..⌊√M⌋]; корректировка при полном квадрате устраняет двойной учёт. 

Упражнение 5. Двоичный поиск как пример цикла с инвариантом и вариантом
Условие. Дан отсортированный по неубыванию массив a и значение x. Найти левую границу (первую позицию i, где a[i] ≥ x).

Требуется. Реализовать while с инвариантом и обосновать завершение.

Решение.

def lower_bound(a, x):

    l, r = 0, len(a)          # полуинтервал [l, r)

    while l < r:

        m = l + (r - l) // 2

        if a[m] < x:

            l = m + 1

        else:

            r = m

    return l

Инвариант: искомая позиция всегда лежит в полуинтервале [l, r). На каждой итерации длина интервала уменьшается (вариант – r - l), следовательно цикл завершится.
Сложность: O(log n). 

Заключение

Итерационные циклы – фундаментальная конструкция, вокруг которой строится подавляющее большинство практических алгоритмов, встречающихся на ЕГЭ и в реальной разработке. Их корректное применение опирается на:

• чёткий инвариант (что гарантированно верно после каждой итерации),

• вариант (что уменьшается и обеспечивает завершение),

• строгую дисциплину границ (единый выбор [L, R)),

• осознанный выбор конструкции (for/while/do-while) и управляющих операторов.

Отработка типовых схем – «агрегирование», «поиск экстремума», «скользящее окно», «два указателя», «поиск с бинарным делением» – формирует мышление на уровне инвариантов и даёт устойчивые шаблоны, позволяющие решать широкий класс задач ЕГЭ корректно и эффективно.