Циклы и перебор

While повторяет тело, пока условие истинно. Его берут там, где невозможно заранее сказать, сколько шагов понадобится. Классический пример — разбор числа по цифрам: ```

``` Сколько будет шагов, зависит от длины числа, и заранее она неизвестна — поэтому for здесь неудобен. Три вещи, без которых while зацикливается. 1. Переменная условия должна существовать до цикла. Если n не задана, программа остановится с ошибкой ещё до первого шага. 2. Внутри цикла условие должно приближаться к ложному. Строка n //= 10 здесь — не деталь, а сам смысл: без неё n никогда не станет нулём. 3. Проверка происходит перед каждым шагом, а не в середине. Если условие ложно с самого начала, тело не выполнится ни разу. Два слова управления циклом. break немедленно прекращает цикл. Нужен, когда искомое найдено и продолжать бессмысленно: именно так в задании 25 выводят ровно пять чисел. continue пропускает остаток тела и переходит к следующему шагу. Удобно, когда очередной элемент не подходит по условию. Частая ошибка на экзамене — забыть увеличить счётчик внутри while. Программа не падает, а зависает, и это выглядит как ошибка компьютера, хотя дело в одной пропущенной строке.

Цикл for используют, когда число повторений известно заранее или когда нужно перебрать элементы готовой последовательности.

Функция range задаёт последовательность целых чисел. Три её формы:

range(n) — числа от 0 до n − 1; range(a, b) — от a до b − 1, то есть правая граница не включается; range(a, b, step) — с заданным шагом; при отрицательном шаге счёт идёт вниз.

Невключение правой границы — источник ошибки «на единицу», самой частой в программировании вообще. Чтобы перебрать числа от 1 до 100 включительно, пишут range(1, 101).

Цикл while используют, когда число повторений заранее неизвестно, а известно условие продолжения.

Такой цикл — стандартный способ разобрать число на цифры: пока число не исчерпано, отрезаем последнюю цифру.

Опасность бесконечного цикла. Если внутри while переменная условия не меняется, программа зависнет. Проверяйте: есть ли в теле цикла строка, которая приближает условие к ложному?

break и continue. Оператор break немедленно выходит из цикла — удобен, когда ответ найден и продолжать бессмысленно. Оператор continue переходит к следующей итерации, пропуская остаток тела.

Перебор с накоплением — главная схема заданий 25–27. У неё всегда одна и та же форма: до цикла создаётся накопитель, в цикле он обновляется, после цикла выводится.

Накопителем может быть сумма, произведение, счётчик, максимум, минимум, список подходящих элементов. Важная деталь: начальное значение накопителя выбирается осмысленно. Для суммы это 0, для произведения 1, для максимума — либо первый элемент, либо заведомо малое число.

Практическое правило выбора: for — когда известно, сколько шагов; while — когда известно, при каком условии остановиться. Перебор диапазона, обход списка, проход по строке — это for. Поиск первого подходящего числа, деление до нуля, повторение до схождения — это while. Попытка выразить второе через for с искусственно большой границей и break работает, но читается хуже и чаще приводит к ошибке в границе.

Когда нужно рассмотреть все пары элементов, применяют вложенные циклы.

Такой перебор рассматривает n² пар, включая пары элемента с самим собой и обе перестановки каждой пары. Если пары неупорядоченные и элемент с самим собой не нужен, внутренний цикл начинают позже:

Число рассмотренных пар здесь равно n·(n − 1) / 2.

Когда вложенные циклы допустимы, а когда нет. Всё решает размер данных. При n порядка тысячи n² — это миллион операций, что выполняется мгновенно. При n порядка миллиона n² — это 10<sup>12</sup> операций, и программа не закончится никогда. Именно поэтому задание 27 требует одного прохода, а задание 26 с меньшим объёмом данных допускает сортировку и более тяжёлые приёмы.

Приём, заменяющий двойной цикл. Очень часто перебор пар не нужен: достаточно, идя по данным один раз, помнить нужную величину о предыдущих элементах. Например, чтобы найти наибольшую сумму двух элементов, не нужно перебирать пары — достаточно хранить максимум среди уже просмотренных и на каждом шаге пробовать сумму текущего элемента с этим максимумом. Из O(n²) получается O(n).

Этот приём — «идти один раз и помнить нужное» — ключ ко всей второй части, и к нему стоит возвращаться при каждой задаче на большие данные.

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

range(n) — числа от 0 до n − 1, всего n значений. Единица в конце не входит: range(5) это 0, 1, 2, 3, 4.

range(a, b) — от a до b − 1 включительно, всего b − a значений. range(2, 8) это 2, 3, 4, 5, 6, 7 — шесть чисел, а не семь.

range(a, b, s) — от a с шагом s, пока не достигнут b. range(10, 0, -1) идёт по убыванию: 10, 9, …, 1. Ноль в конец не входит, и это ловушка обратных переборов: чтобы дойти до единицы, границу пишут нулём.

Отсюда три места, где ошибаются постоянно.

Правая граница не включается. Чтобы перебрать числа от 1 до 100 включительно, пишут range(1, 101). Забытая единица теряет последнее число, и в задачах вида «наибольшее подходящее» это меняет ответ.

Соседние пары. Индекс i идёт до len(a) - 1, потому что внутри цикла берут a[i + 1]. При range(len(a)) последний виток обратится за конец списка.

Обратный перебор. range(9999, 999, -1) перебирает четырёхзначные числа по убыванию и доходит до 1000 — граница 999 не включается. Написав range(9999, 1000, -1), вы потеряете само число 1000.

И отдельно про то, чего range не умеет: он работает только с целыми. Перебрать значения с шагом 0,1 им нельзя, и это правильно — дробный шаг накапливал бы погрешность. Если такое понадобилось, перебирают целые и делят: for i in range(0, 100): x = i / 10.

Наконец, полезное свойство: range не создаёт список в памяти, а выдаёт числа по одному. Поэтому for i in range(10**9) не съест память — он просто будет долго работать, и это уже вопрос сложности, а не памяти.

Два оператора управляют ходом цикла, и путать их дорого.

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

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

Сравните два способа записать один и тот же отбор. Через вложенные условия:

for x in a:

if x % 2 == 0:

if x > 100:

summa += x

и через continue:

for x in a:

if x % 2 != 0:

continue

if x <= 100:

continue

summa += x

Второй вариант длиннее на строку, но у него есть важное достоинство: каждое условие проверяется отдельно и на одном уровне отступа. При отладке легко поставить печать перед любым continue и увидеть, что именно отсеялось. Именно поэтому в решениях линий 3, 17 и 26 удобнее continue, а не лесенка из вложенных if.

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

И полезное свойство, о котором мало кто знает: у цикла в Python бывает ветка else. Она выполняется, если цикл завершился без break. Это удобно для проверок вида «ни один элемент не подошёл»: тело else срабатывает ровно тогда, когда поиск ничего не нашёл.

И ещё об одном частом недоразумении: break выходит только из своего цикла. Во вложенных циклах он прерывает внутренний, а внешний продолжает работать. Если нужно выйти сразу из обоих, заводят флаг (nashli = True) и проверяют его в условии внешнего цикла, либо выносят поиск в отдельную функцию и выходят из неё через return — второй способ короче и читается лучше.