Вложенные циклы

Вложенный цикл – это конструкция, в которой тело одного цикла содержит другой цикл (иногда несколько). Вложенные циклы формируют систематический перебор многомерных пространств состояний: пар, троек, k-кортежей, индексов матриц, комбинаций параметров. Компетентное владение вложенными циклами необходимо для решения задач ЕГЭ на перебор и подсчёт, анализ алгоритмов, матричные расчёты, обработку строк и чисел поразрядно. Ниже изложены строгие определения, правила корректной записи и оценки трудоёмкости, типичные схемы и приёмы оптимизации, а затем – пять тренировочных упражнений формата «теория + практика».

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

1. Базовое определение
   

   Пусть имеется внешний цикл с параметром i и внутренний с параметром j. Псевдокод:

   for i ← a..b (шаг s_i):

       <инициализация, зависящая от i>

       for j ← c(i)..d(i) (шаг s_j(i)):

           <действия над i, j>

   • Пространство перебора – декартово произведение всех допустимых значений параметров, учитывая зависимость границ c(i),d(i) от внешнего параметра.

   • Порядок обхода задаётся лексикографически: для каждого i последовательно перебираются все j. Замена порядка вложенности меняет порядок перечисления и иногда – число итераций, если границы зависят от внешнего параметра.

2. Инварианты вложенных циклов 
   

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

   1.3. Модели записи (языковые детали для ЕГЭ)

   • Pascal-подобный: for i := a to b do – границы включительные.

   • Python-подобный: for i in range(a, b+1): для включения верхней границы; range(a, b) – верхняя граница исключена.

   • while эквивалентен for, если корректно заданы и обновление параметра, и условие останова.

Подсчёт итераций и сложность

1. Прямоугольная область (независимые границы)
   

2. Треугольная область (зависимость границ)
   

3. k-мерный перебор
   k вложенных циклов по 10 значений каждый ⇒ 10^k итераций. Это показывает риск комбинаторного взрыва: проверяйте, что N укладывается в ресурс времени.

4. Влияние break/continue
   

   • break сокращает фактическое число итераций (лучший случай), но не меняет худшую оценку, если условие может не выполниться.

   • continue пропускает часть тела цикла, но не уменьшает числа проходов параметра.

Правильные границы и безопасность

1. Диапазоны включения/исключения: задавайте явно – «включительно» или «исключая верхнюю».

2. Шаг: проверяйте знак шага и условие (≤ при положительном шаге, ≥ при отрицательном).

3. Избегайте выхода за границы массива: если массив A[0..n-1], то индексируйте 0 ≤ i < n.

4. Зависимые границы: вычисляйте единожды и храните в локальных переменных, если выражение сложное – это повышает читаемость и стабильность.

5. Инициализация агрегатов (сумм, минимумов, флагов) – перед внутренним циклом, если агрегат относится к «строке/столбцу»; перед внешним – если к всей задаче.

Типовые паттерны вложенных циклов

1. Перебор пар (декартово произведение)
   

   count ← 0

   for i in X:             # множество/диапазон X

       for j in Y:         # множество/диапазон Y

           if условие(i, j):

               count ← count + 1

2. Перебор без повторов / без порядка (комбинации)
   

   for i = 1..n:

       for j = i+1..n:

           <обработка пары {i, j}>   # каждая unordered-пара встречается ровно 1 раз

3. Треугольный обход матрицы (с диагоналями)
   

   sum ← 0

   for i = 0..n-1:

       for j = 0..i:

           sum ← sum + A[i][j]       # нижний треугольник, включая диагональ

4. Поразрядный перебор числа (типично для ЕГЭ)
   

   count ← 0

   for a = 1..9:         # старший разряд (без нуля)

       for b = 0..9:

           for c = 0..9:

               x ← 100*a + 10*b + c

               if предикат(x, a, b, c):

                   count ← count + 1

5. Двумерный поиск с ранним прерыванием
   

   found ← false

   for i = 0..n-1:

       for j = 0..m-1:

           if A[i][j] == key:

               found ← true

               break                # выход из внутреннего

       if found:

           break                    # выход из внешнего

Оценка и оптимизация

• Перестановка циклов может менять кэш-локальность и фактическое время, но не меняет асимптотический порядок при независимых границах. Для матриц выгодно, чтобы внутренний индекс пробегал смежные элементы в памяти.

• Сужение области перебора: перенос условий в границы (for j = max(c, f(i))..d) уменьшает число итераций.

• Арифметические свёртки: если содержимое внутреннего цикла – сумма арифметической прогрессии, замените цикл формулой.

• Предвычисление: выражения, не зависящие от внутреннего индекса, выносите наружу.

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

1. Перепутаны включительные/исключительные границы (off-by-one).

2. Внутренний индекс используется вне допустимого диапазона массива.

3. Неверная зависимость границ (например, j=1..i-1, но используется A[i][j] на диагонали).

4. Условие break расположено неверно, из-за чего прерывание не влияет на внешний цикл.

5. Дублирование перебора (одно и то же условие проверяется дважды в разных порядках).

6. Отсутствие инициализации агрегатов в правильном месте вложенности.

7. Комбинаторный взрыв: 10510^5105 комбинаций ещё возможно, 10810^8108 – уже нет в типичном лимите времени.

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

• Перебор и подсчёт: задачи на подсчёт чисел/строк, удовлетворяющих условиям на разряды, делители, суммы цифр.

• Матрицы/таблицы: суммы по строкам/столбцам/треугольникам, поиск экстремумов.

• Анализ сложности: «сколько раз выполнится оператор» – типичный вопрос.

• Алгоритмизация: преобразование словесного описания области (i,j) в точные границы циклов.

• Проверка корректности: трассировка малого примера (например, n=3) для выявления off-by-one.

Пять упражнений (теория + практика)

Упражнение 1. Подсчёт итераций и сложность

Дан фрагмент:

for i = 1..n:

    for j = i..n:

        S ← S + f(i, j)

a) Выведите точную формулу для числа итераций через nnn.
b) Укажите асимптотику и объясните, почему она не изменится при перестановке циклов местами, если границы оставить семантически эквивалентными.
c) Модифицируйте границы так, чтобы суммировать только элементы строго выше диагонали, и пересчитайте число итераций.

Упражнение 2. Перебор по разрядам (ЕГЭ-стиль)

Найдите количество четырёхзначных чисел в десятичной системе, в записи которых:

1. цифры неубывают слева направо;

2. ни одна цифра не равна 7;

3. сумма цифр кратна 3.
   Требуется:
   a) Записать схему четырёх вложенных циклов по цифрам a,b,c,d с корректными границами (учтите, что a≠0 и a≤b≤c≤d).
   b) Ввести оптимизацию: заменить часть проверок на сужение границ (например, диапазон b от a до 9 и т.п.).
   c) Оценить порядок величины перебора до и после оптимизации.

Упражнение 3. Матричные треугольники

Пусть A – квадратная матрица n×n.
a) Запишите два варианта вложенных циклов для суммы нижнего треугольника: (1) включая диагональ, (2) строго ниже диагонали.
b) Преобразуйте код так, чтобы суммировать элементы антидиагонального треугольника (условие на i+j).
c) Объясните, как изменить порядок вложенности для лучшей кэш-локальности при построчном хранении.

Упражнение 4. Комбинации без повторов

Нужно перебрать все неупорядоченные тройки попарно различных индексов {i,j,k} из {1,…,n}, не считая перестановки различными.
a) Запишите вложенные циклы с границами 1≤i<j<k≤n.
b) Выведите формулу числа итераций тела ((n3)) через сумму по внешнему индексу.
c) Предложите проверку корректности на малых n (например, n=4): перечислите все тройки и убедитесь в отсутствии дубликатов.

Упражнение 5. Раннее прерывание и оценка случаев

Дан фрагмент:

found ← false

for i = 0..n-1:

    for j = 0..m-1:

        if P(i, j):         # редкое условие

            found ← true

            break

    if found:

        break

a) Оцените лучшую, среднюю (при равномерном появлении события) и худшую трудоёмкость по числу проверок P(i, j).
b) Объясните, почему наличие break не меняет худший случай, но критично влияет на средний.
c) Для матрицы с построчным хранением предложите порядок вложенности, минимизирующий фактическое время при условии, что P чаще срабатывает на малых j.

Заключение

Вложенные циклы – универсальный инструмент перечисления сложных пространств состояний и построения систематических переборов. Ключ к корректности – точные границы и инварианты; ключ к эффективности – разумная геометрия области, порядок обхода и ранние отсечения. Для ЕГЭ умение переводить словесные ограничения в границы циклов, считать итерации, избегать off-by-one и оценивать сложность превращает задачи на перебор, матрицы и подсчёты в рутинно решаемые и даёт уверенные баллы.