ЕГЭОГЭ
Задания № 12, 16 · ЕГЭ

Подсчёт итераций вложенных циклов

Как находить число повторений, значения счётчиков и результат работы вложенных циклов
6 мин чтенияСложность: Обновлено 29 сентября 2026

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

1. Что называют итерацией

Итерация — одно выполнение тела цикла. Если тело выполнилось 7 раз, цикл совершил 7 итераций. У внешнего и внутреннего циклов количество итераций может быть разным.

D
Определение

Во вложенных циклах внутренний цикл полностью выполняется для каждого значения внешнего цикла. Поэтому общее число выполнений тела внутреннего цикла равно сумме его итераций по всем запускам.

Например, в конструкции for i = 1..4 и внутри неё for j = 1..3 внешний цикл запускается 4 раза. При каждом запуске внутренний цикл делает 3 шага, поэтому тело внутреннего цикла выполняется \(4\cdot 3=12\) раз.

\[N=\sum_{i=1}^{m} n_i\]1

Здесь \(m\) — число итераций внешнего цикла, а \(n_i\) — число итераций внутреннего цикла при \(i\)-м значении внешней переменной. Если внутренний цикл всегда одинаков, \(n_i=n\), то формула упрощается:

\[N=m\cdot n\]2

Правило счёта цикла особенно важно для циклов с условием, шагом, изменяемой границей или включёнными конечными значениями.

2. Постоянное и переменное число повторений

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

Внутренний циклЧисло итераций при целых значениях
\(j=1,2,\ldots,k\)\(k\)
\(j=a, a+1,\ldots,b\)\(b-a+1\), если \(a\le b\)
\(j=a, a+d,\ldots,b\)\(\left\lfloor\frac{b-a}{d}\right\rfloor+1\), если \(a\le b\)
\(j=1,2,\ldots,i\)\(i\)
\(j=i, i+1,\ldots,n\)\(n-i+1\)

В формулах для шага 1 конечные границы включаются. Если цикл записан как while j < k, значение \(j=k\) уже не обрабатывается. Поэтому сначала нужно точно установить, какие значения принимает переменная, а не просто сравнить границы.

T
Основное правило суммирования

Если при \(i=1,2,\ldots,m\) внутренний цикл выполняется \(n_i\) раз, то число итераций внутреннего тела равно \(N=n_1+n_2+\ldots+n_m\). При линейной зависимости \(n_i=i\) возникает сумма \(1+2+\ldots+m=\frac{m(m+1)}2\).

Такая оценка связана с анализом вложенных циклов: важно исследовать не только глубину вложенности, но и зависимость границ циклов.

Проверь себя

Сколько раз выполнится тело внутреннего цикла: for i = 1..5, внутри for j = 1..i?

3. Алгоритм подсчёта по таблице

Когда границы зависят друг от друга, удобно действовать механически. Это снижает риск пропустить один из запусков или перепутать начальное значение счётчика.

  1. Запишите все значения внешней переменной в порядке их обработки.
  2. Для каждого значения найдите первое, последнее и последующее значение внутренней переменной.
  3. Определите число итераций внутреннего цикла.
  4. Сложите полученные количества.
  5. Если требуется результат программы, отдельно проследите, что изменяется внутри тела: сумма, произведение, счётчик, максимум или вывод.

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

Удобная таблица

Для нескольких значений внешней переменной используйте столбцы: \(i\), диапазон \(j\), число итераций, вклад в результат. Таблица сразу показывает, какие слагаемые нужно сложить.

4. Разобранный пример: число итераций и сумма

Рассмотрим алгоритм. Внешний цикл перебирает \(i\) от 2 до 6, внутренний — \(j\) от 1 до \(i-1\). Внутри увеличивается переменная \(s\) на значение \(j\).

Псевдокод
1s := 0
2for i := 2 to 6 do
3    for j := 1 to i - 1 do
4        s := s + j
5    end for
6end for
№
Что требуется найти

Найдём общее число итераций внутреннего цикла и конечное значение \(s\). Внешняя переменная принимает значения \(2,3,4,5,6\).

1
При \(i=2\) внутренний цикл принимает только значение \(j=1\).
\(\displaystyle n_2=1\)
2
При \(i=3\) значения \(j\) равны 1 и 2.
\(\displaystyle n_3=2\)
3
Аналогично для остальных значений внешней переменной.
\(\displaystyle n_4=3,\quad n_5=4,\quad n_6=5\)
4
Складываем число итераций всех запусков внутреннего цикла.
N=1+2+3+4+5=15
5
Вклад одного запуска равен сумме значений \(j\) от 1 до \(i-1\).
\(\displaystyle 1+2+\ldots +(i-1)=\frac{(i-1)i}{2}\)
6
Складываем вклады при \(i=2,3,4,5,6\).
s=1+3+6+10+15=35

Ответ: тело внутреннего цикла выполнится 15 раз, а после завершения алгоритма \(s=35\). Обратите внимание: число итераций и конечное значение переменной — разные величины. За одну итерацию к \(s\) прибавляются разные числа.

\[N=\sum_{i=2}^{6}(i-1)=15,\qquad s=\sum_{i=2}^{6}\sum_{j=1}^{i-1}j=35\]

5. Циклы while, шаг и условие остановки

Для цикла while число повторений находят по значениям переменной перед проверкой условия. Нужно учитывать начальное значение, изменение после тела и момент, когда условие становится ложным.

Если переменная \(x\) начинается со значения \(a\), на каждом шаге увеличивается на \(d\), а тело выполняется, пока \(x\le b\), то при \(d>0\) число итераций равно:

\[N=\left\lfloor\frac{b-a}{d}\right\rfloor+1\quad (a\le b)\]

Если внутренний цикл зависит от внешнего, это выражение нужно применять для каждого значения внешней переменной, а затем суммировать. Для убывающей переменной аналогично учитывают отрицательный шаг.

!
Частые ошибки

1. Умножать числа итераций, когда внутренний цикл зависит от внешнего. Нужно использовать сумму. 2. Забывать, что конечная граница может включаться. 3. Считать проверку условия итерацией: проверка и выполнение тела — не одно и то же. 4. Путать число запусков внутреннего цикла с общим числом его итераций. 5. Считать только количество действий, хотя вопрос спрашивает конечное значение переменной.

При подсчёте результата полезно вести значения переменных после каждого внешнего запуска. Если вычисления становятся громоздкими, можно заменить повторяющуюся часть известной суммой, но границы этой суммы следует проверить вручную.

Запомните

Сначала определите диапазон внешнего цикла, затем число повторений внутреннего для каждого внешнего значения. Только после этого считайте сумму, произведение или другой результат.

6. Связь с другими алгоритмами

Вложенные циклы часто реализуют полный перебор вариантов: внешний цикл выбирает один параметр, внутренний — другой. Если число вариантов на каждом уровне постоянно, количество проверок находится умножением; если зависит от уже выбранного параметра, возникает сумма.

Похожая логика используется в сравнении рекурсии и итерации: нужно считать реальные вызовы или повторения, а не только уровни записи алгоритма. При задачах на перебор с возвратом полезно дополнительно учитывать сложность перебора с возвратом.

Q
Быстрый тест по теме

Итоговая проверка

~ 2 мин4 вопроса
Вопрос 1 / 4
Вопрос 1 из 4 · постоянные границы
Внешний цикл выполняется 4 раза, внутренний — 6 раз при каждом запуске. Сколько выполнений внутреннего тела?
Главное за минуту

Главное

  • Итерация — одно выполнение тела цикла.
  • При постоянном числе повторений внутренних циклов используйте умножение \(m\cdot n\).
  • Если границы внутреннего цикла зависят от внешней переменной, складывайте числа итераций.
  • Для результата алгоритма отдельно отслеживайте вклад каждой итерации.
  • Проверяйте включение границ, шаг и условие остановки; при сомнении составляйте таблицу.