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

Что происходит, когда один цикл целиком помещается внутрь тела другого, и почему тело при этом выполняется n·m раз.

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

Один цикл умеет перебирать линейку: дни недели, элементы списка, числа от 1 до 100. Но многие данные двумерные — таблица умножения, шахматная доска, матрица, пиксели картинки. Чтобы пройтись по таблице, одного счётчика мало: нужен один для строк и второй для столбцов. Так и появляется цикл внутри цикла.

Зачем это нужно

Любая «решётка» значений — это вложенный цикл. Распечатать таблицу умножения 9×9, найти максимум в матрице, сравнить каждого ученика с каждым, нарисовать прямоугольник из звёздочек — везде внешний цикл отвечает за строки, внутренний за то, что происходит внутри одной строки. Без вложенности пришлось бы писать девять почти одинаковых циклов подряд, а это не масштабируется.

Счётчик внешнего и внутреннего цикла

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

[начало]
  |
  V
<для i от 1 до 3> ----------------+
  |                               |
  V                               |
  <для j от 1 до 3> ----------+   |
    |                         |   |
    V                         |   |
    [печать i*j]              |   |
    |                         |   |
    +--- j := j+1, на проверку+   |
  |                               |
  +--- i := i+1, на проверку------+
  |
  V
[конец]

Прочитаем по шагам для диапазонов 1..3. При i = 1 внутренний цикл даёт j = 1, 2, 3 и печатает 1, 2, 3. Затем i становится 2, и j снова с самого начала идёт 1, 2, 3 — печатаются 2, 4, 6. При i = 3 — 3, 6, 9. Внутренний счётчик «обнуляется» столько раз, сколько шагов у внешнего.

Сколько раз выполнится тело

Это любимый вопрос ЕГЭ. Если внешний цикл делает n повторений, а внутренний при каждом из них — m повторений, то тело внутреннего цикла выполнится

$$ N = n \cdot m $$

раз. Для таблицы 3×3 это $3 \cdot 3 = 9$ операций умножения — ровно столько чисел мы и напечатали. Если диапазоны разные, перемножаем их длины: внешний $i$ от 1 до 5 и внутренний $j$ от 1 до 4 дают $5 \cdot 4 = 20$ выполнений тела. А вот сам внутренний цикл запускается $n$ раз (по разу на каждый шаг внешнего) — не путайте «сколько раз стартует внутренний цикл» ($n$) и «сколько раз выполнится его тело» ($n \cdot m$).

Когда границы внутреннего цикла зависят от i (треугольный обход), число повторений считают суммой. Например, если для каждого i от 1 до n внутренний идёт j от 1 до i, всего тело выполнится

$$ 1 + 2 + 3 + \dots + n = \frac{n \cdot (n+1)}{2} $$

раз. Для $n = 4$ это $\frac{4 \cdot 5}{2} = 10$.

Как это работает

Соберём таблицу умножения настоящим кодом. Внешний for i идёт по строкам, внутренний for j — по столбцам; внутри строки накапливаем числа в строку row, а после внутреннего цикла печатаем её:

for i in range(1, 4):
    row = ""
    for j in range(1, 4):
        row += str(i * j) + "\t"
    print(row)

Вывод:

1	2	3	
2	4	6	
3	6	9

Каждая строка вывода — один полный проход внутреннего цикла. Теперь обход матрицы: найдём её максимальный элемент. Матрицу хранят как список списков, внешний цикл берёт строку, внутренний — элемент строки:

matrix = [[3, 8, 1],
          [7, 2, 9],
          [4, 6, 5]]
maxv = matrix[0][0]
count = 0
for i in range(3):
    for j in range(3):
        count += 1
        if matrix[i][j] > maxv:
            maxv = matrix[i][j]
print("Просмотрено элементов:", count)
print("Максимум:", maxv)

Вывод:

Просмотрено элементов: 9
Максимум: 9

Счётчик count подтверждает формулу: матрица 3×3, тело выполнилось $3 \cdot 3 = 9$ раз. Если бы матрица была 10×10, тело отработало бы 100 раз — поэтому вложенные циклы «дороже» одиночных, и за их числом повторений следят.

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

Один счётчик на оба цикла. Если внешний и внутренний используют одну и ту же переменную, внутренний цикл испортит счётчик внешнего, и внешний завершится преждевременно. Внешнему — i, внутреннему — j.
Сброс накопителя не на том уровне. Если копим сумму строки, обнулять row или summa нужно внутри внешнего цикла, но до внутреннего. Поставите обнуление перед обоими циклами — суммы строк слипнутся в одну.
Путаница «n запусков» и «n·m выполнений». Внутренний цикл стартует n раз, но его тело срабатывает n·m раз. На экзамене спрашивают именно про тело.
Перепутанные границы при обходе матрицы. Для прямоугольной матрицы внешний цикл идёт по числу строк, внутренний — по числу столбцов; их легко поменять местами и выйти за границы.

Итоги

Вложенный цикл — цикл в теле другого цикла; на каждый шаг внешнего внутренний прокручивается полностью.
Внешний счётчик отвечает за строки, внутренний — за столбцы; внутренний начинает заново при каждом шаге внешнего.
Тело внутреннего цикла выполняется $n \cdot m$ раз; сам внутренний цикл запускается $n$ раз — это разные числа.
Если границы внутреннего зависят от внешнего, число повторений считают суммой, например $\frac{n(n+1)}{2}$ для треугольного обхода.
Вложенные циклы — основа работы с таблицами и матрицами; накопители обнуляйте на правильном уровне вложенности.