Вложенные циклы – Учебник

4.7

О чём этот урок

Электронные часы показывают часы и минуты: 0:00, 0:01, … 23:59. Сколько всего различных показаний они успевают показать за сутки – и как перечислить их все по порядку программой?

Со вторым вопросом обычный цикл не справляется. Все циклы, которые встречались до сих пор, проходили по одному ряду значений: числа от 1 до 100, цифры одного числа, кандидаты в делители. А здесь ряда два, и они не независимы: пока часовая цифра стоит на 7, минутная должна прокрутить все шестьдесят значений – и только потом час сменится на 8. Такой перебор называют двойным, и делается он циклом внутри цикла.

Разминка. Прежде чем читать дальше, прикиньте ответ на первый вопрос сами – а заодно вспомните, как считают количество вариантов в комбинаторике: складывают или умножают? Ответ на этот вопрос и определит, во что обходится вложенность.

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

Цикл внутри цикла

Нового синтаксиса для этого не нужно вообще. Тело цикла – обычный блок кода, отмеченный отступом, и внутри него может стоять что угодно: print(), if, ещё один цикл.

Вложенный цикл – цикл, записанный в теле другого цикла. Внешний цикл управляет «крупным» перебором, внутренний – «мелким».

Главное правило, из которого следует всё остальное в уроке:

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

Внутренний цикл не «продолжается с того места, где остановился» – он каждый раз стартует заново.

Минимальный вложенный цикл

for i in range(1, 4):
    for j in range(1, 3):
        print(i, j)

Внешний цикл даёт i значения 1, 2, 3. Внутренний для каждого из них – j = 1, 2. Вывод получается такой:

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

Всего строк – шесть: три итерации внешнего цикла, по две внутренних в каждой. Пройдите пример по шагам и проследите за моментом, когда j возвращается к единице, – там и происходит переход к новой итерации внешнего цикла.

Внешний цикл задаёт строки, внутренний – ячейки внутри строки: пока `i` стоит на месте, `j` пробегает весь свой диапазон.

Правило умножения

Отсюда простой способ считать работу вложенного цикла:

Если внешний цикл делает N итераций, а внутренний – M итераций на каждую, всего тело внутреннего цикла выполнится $N \cdot M$ раз.

Складывать не нужно, нужно умножать – и это отличает вложенные циклы от двух циклов, записанных подряд. Два цикла по 100 итераций, идущих друг за другом, дают 200 итераций. Те же два цикла, вложенные один в другой, – 10 000.

Вернёмся к часам. Внешний перебор – часы, range(24). Внутренний – минуты, range(60). Значит, показаний ровно $24 \cdot 60 = 1440$.

Все показания часов за сутки

for h in range(24):
    for m in range(60):
        print(h, m)

Обе границы начинаются с нуля, поэтому range(24) и range(60) записаны в короткой форме из урока 4.4 – верхняя граница не входит, а именно значений 24 и 60 на часах и не бывает.

Вывод получится не самым красивым: print(h, m) напечатает 7 5 вместо привычного 7:05. Аккуратное форматирование чисел – тема блока 8; сейчас важнее сам порядок перебора, а он верный: 1440 строк, от 0 0 до 23 59.

Таблица умножения: строки и ячейки

Двойной перебор естественно ложится на любую таблицу: внешний цикл – строки, внутренний – ячейки в строке. Возьмём таблицу умножения $9 \times 9$.

Мешает одна деталь. По умолчанию print() после вывода переходит на новую строку – поэтому все прошлые программы печатали столбиком. Это поведение меняется параметром end: он задаёт, что напечатать после значений вместо перевода строки.

print(x) – напечатать x и перейти на новую строку;
print(x, end=' ') – напечатать x и остаться на той же строке, отделив пробелом;
print() – не печатать ничего, только перейти на новую строку.

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

Таблица умножения

for i in range(1, 10):
    for j in range(1, 10):
        print(i * j, end=' ')
    print()

Три уровня отступа

В этой программе три уровня отступа, и каждый значит своё:

Строка	Отступ	Когда выполняется
`for j in ...`	4 пробела	9 раз – один раз на каждую итерацию внешнего цикла
`print(i * j, end=' ')`	8 пробелов	81 раз – тело внутреннего цикла
`print()`	4 пробела	9 раз – после каждого полного прохода внутреннего цикла

Сдвиньте последний print() на 8 пробелов – и он попадёт внутрь внутреннего цикла: перенос строки будет после каждого числа, таблица вытянется в столбик из 81 строки. Уберите отступ совсем – print() окажется за пределами обоих циклов и выполнится один раз в самом конце, когда все 81 число уже напечатаны в одну строку.

Ни в том, ни в другом случае Python не сообщит об ошибке: код останется корректным, изменится только результат. Отступ здесь – не оформление, а часть алгоритма.

Прямоугольник из символов

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

Прямоугольник 3 × 7

rows = 3
cols = 7
for i in range(rows):
    for j in range(cols):
        print('*', end='')
    print()

Когда внутренний цикл зависит от внешнего

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

Это второй важный приём урока. Внутренний цикл не обязан быть одинаковым – он может подстраиваться под текущий шаг внешнего.

Треугольник

n = int(input())
for i in range(1, n + 1):
    for j in range(i):
        print('*', end='')
    print()

Для n = 5 программа напечатает:

*
**
***
****
*****

Правило умножения здесь уже не работает: внутренний цикл делает то 1, то 2, то 5 итераций. Общее число звёздочек – сумма 1 + 2 + … + n, и у неё есть известная формула.

\[ S = \frac{n(n+1)}{2} \]

Для n = 5 это 15 звёздочек, для n = 100 – 5050. Величина всё равно растёт как квадрат n, просто вдвое медленнее полного прямоугольника.

Кстати, тот же треугольник можно напечатать и одним циклом – через дублирование строки из урока 1.8: print('*' * i). Это короче, и в реальном коде так и пишут. Но нам сейчас важен сам приём двойного перебора: как только вместо одинаковых символов в ячейках окажутся разные значения (как в таблице умножения), одним циклом уже не обойтись.

break выходит только из своего цикла

С break из урока 4.5 во вложенных циклах связана самая частая ошибка:

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

Разложим на два множителя число 91 – переберём все пары a и b и остановимся на первой подходящей. Один break во внутреннем цикле остановит перебор b, но внешний цикл честно возьмёт a = 8, a = 9 и так далее до конца. Чтобы выйти из обоих циклов, нужен флаг – как is_prime в уроке 4.6.

Разложение числа на два множителя

target = 91
found = False
for a in range(2, target):
    for b in range(a, target):
        if a * b == target:
            print(a, 'x', b)
            found = True
            break
    if found:
        break

Внутренний цикл начинается с range(a, target), а не с двойки: пары 7 · 13 и 13 · 7 – одно и то же разложение, и второй раз печатать его незачем. Это опять внутренний диапазон, зависящий от внешней переменной.

Проверка if found: break записана внутри внешнего цикла, но снаружи внутреннего – на том же уровне, где в таблице умножения стоял пустой print(). Место в отступах одно и то же, роль разная.

Коротко

За сутки электронные часы показывают 1440 различных значений – $24 \cdot 60$. Перечислить их все можно тремя строками кода, и ни одной новой конструкции для этого не понадобилось.

Задача	Внешний цикл	Внутренний цикл
Показания часов	часы, `range(24)`	минуты, `range(60)`
Таблица умножения	строка таблицы	ячейка в строке
Прямоугольник	строка	символ в строке
Треугольник	строка	символ, `range(i)` – зависит от внешнего

Вложенный цикл – цикл в теле другого цикла. Нового синтаксиса не требуется: тело цикла – обычный блок с отступом.
На каждой итерации внешнего цикла внутренний выполняется целиком, с самого начала, а не продолжается с того места, где остановился.
Правило умножения: внешний делает N итераций, внутренний M на каждую – тело внутреннего выполнится $N \cdot M$ раз. Два цикла подряд дают N + M, вложенные – $N \cdot M$.
Внешний цикл – строки таблицы, внутренний – ячейки в строке. Перевод строки делает print() без аргументов, записанный после внутреннего цикла, но внутри внешнего; print(x, end=' ') оставляет вывод на той же строке.
Границы внутреннего цикла могут зависеть от переменной внешнего – так из прямоугольника получается треугольник, и правило умножения перестаёт работать.
break прерывает только тот цикл, в теле которого записан. Чтобы выйти сразу из двух, нужен флаг.
У вложенности есть цена: два цикла по 1000 итераций дают миллион проходов, три – миллиард. Именно здесь программы начинают «тормозить»; измерять это научимся в блоке 10.