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

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

Так и пишут: цикл внутри цикла.

for i in range(1, 4):        # строки
    for j in range(1, 4):    # столбцы, внутри каждой строки
        print(i * j, end=" ")
    print()                  # перевод строки — после внутреннего цикла

Результат:

1 2 3
2 4 6
3 6 9

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

Обратите внимание на пустой print(). Он стоит в теле внешнего цикла, но вне внутреннего — то есть выполняется один раз на строку. Сдвиньте его вправо — каждое число окажется на своей строке; уберите вовсе — вся таблица сольётся в одну строку.

И переменные должны быть разными. Написать for i внутри for i — это испортить счётчик внешнего цикла, а ошибку такого рода потом ищут долго.

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

n = int(input())

for i in range(n):
    row = ""                 # строка собирается в переменную
    for j in range(n):
        if i == j:
            row += "*"
        else:
            row += "."
    print(row)               # и печатается целиком

Собирать строку в переменную удобнее, чем печатать по символу: видно, что именно получилось, и не остаётся лишних пробелов в конце.

Вся разница между фигурами — в условии внутри:

Там, где строки разной длины — треугольник, ромб, — внутренний цикл вообще не нужен: " " * k + "*" * m строит строку сразу. Главное посчитать, сколько чего в строке номер $i$.

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

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

for i in range(5):
    for j in range(3):
        print(i, j)

Второе применение вложенных циклов — задачи вида «сколько пар обладают свойством».

count = 0

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i + j == s:
            count += 1

Здесь важно понять, что считается парой. Если $(1, 2)$ и $(2, 1)$ — разные пары, перебираются все сочетания, как выше. Если это одна и та же пара, внутренний цикл начинают не с единицы:

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):     # только j больше i

Такой перебор даёт ровно каждую пару по одному разу и заодно работает вдвое быстрее. Условие всегда говорит, какой вариант нужен, — читайте эту фразу внимательно, на ней теряют больше всего попыток.

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

Часто второе число определяется первым однозначно. В задаче про сумму $i + j = s$ достаточно перебрать $i$ и проверить, попадает ли $j = s - i$ в допустимые границы:

for i in range(1, n + 1):
    j = s - i
    if 1 <= j <= n:
        count += 1

Вместо $n^2$ шагов получается $n$. Приём общий: если внутренний цикл ищет то, что можно вычислить, — вычисляйте.

Двойной цикл — первое место в курсе, где верное решение может не пройти. Не из-за ошибки, а из-за объёма: при $n = 100\,000$ перебор всех пар — это десять миллиардов шагов.

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

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

Отсюда практическое правило: увидев в условии $n$ до тысячи, двойной цикл писать можно. Увидев $n$ до ста тысяч — нельзя, нужно искать способ обойтись одним.

Это не строгая теория — до оценок сложности мы дойдём в шестом модуле. Пока достаточно счёта на пальцах: перемножьте длины циклов и сравните с десятью миллионами.

Сколько пар $(i, j)$ переберёт этот цикл при $n = 100$?

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        ...

Введите целое число.

Одна переменная на два цикла. for i внутри for i ломает внешний счётчик. Признак: строк напечаталось меньше, чем должно, или цикл повёл себя необъяснимо.

Перевод строки не на месте. Пустой print() внутри внутреннего цикла — каждый символ на своей строке; отсутствие его вовсе — всё в одну строку. Само по себе это не заметно в коде, зато сразу видно в выводе.

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

Как проверять себя

• самый маленький размер: $n = 1$, а для прямоугольников — $1 \times 1$, $1 \times m$ и $n \times 1$. Узкие случаи ломают рамку и шахматную доску чаще всего;
• несимметричный размер: $3 \times 7$ и $7 \times 3$ должны дать разные фигуры. Если одинаковые — где-то перепутаны $n$ и $m$;
• счёт шагов: перемножьте длины циклов до отправки.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Задачи трёх видов: фигуры из символов, таблицы чисел и подсчёт пар. В фигурах внимательно относитесь к пробелам — они проверяются наравне со звёздочками.

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

Задача: «выведите таблицу умножения $n$ на $n$ — по строке на каждое $i$».

Ученик написал:

n = int(input())

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

Вместо таблицы получается столбик из одного числа в строке. Объясните, почему так выходит, где должна стоять строка print() и сколько всего чисел напечатает программа при $n = 4$.