В журнале наблюдений 30 показаний температуры, и приходят они по одному. Какая температура была самой низкой? И сколько дней было ниже нуля?
Разминка. Человек с блокнотом решает обе задачи в один проход и не выписывает все тридцать чисел. Попробуйте сформулировать сами: что именно он держит в голове, пока слушает показания? Записей ровно две, и обе – числа.
Хранить весь ряд чисел целиком мы пока не умеем – для этого нужны списки из блока 9. И выясняется, что для таких вопросов это не нужно вообще.
В этом уроке: переменная-накопитель, которая помнит лучший ответ, почему начальное значение «с потолка» опасно, несколько накопителей в одном цикле, полный перебор всех вариантов вместо вывода формулы, перебор диапазона с конца с досрочным выходом и когда перебор можно заменить арифметикой.
Перебор с накоплением – цикл, в котором отдельная переменная хранит ответ для уже просмотренной части данных и обновляется на каждой итерации, если новое значение этот ответ меняет.
Приём не новый. В уроке 4.3 так считались сумма и количество цифр числа: накопителями были total и count. Разница только в правиле обновления – сумму мы прибавляли всегда, а максимум перезаписываем только если новое число больше запомненного.
n = int(input())
best = int(input())
for i in range(n - 1):
x = int(input())
if x > best:
best = x
print(best)
Разберём по частям:
n - 1 итераций, а не n: одно число уже прочитано.> или >= – на ответ не влияет: при равенстве перезаписывать нечего. Разница появится только тогда, когда нужен не сам максимум, а номер первого или последнего из максимальных.n = 1, цикл не выполнится ни разу – range(0) пуст (урок 4.4), и программа напечатает единственное прочитанное число. Правильный ответ получается сам, без отдельной проверки на особый случай.Частая ошибка – начать с best = 0. Для температур это ломается: если все тридцать дней были морозными, программа напечатает 0 – значение, которого в данных вообще не было.
best = -1000 продержится дольше, но это «магическое число»: оно молча делает предположение о данных, и однажды данные его нарушат.
Надёжное правило: начальное значение накопителя-экстремума – первый элемент данных, а не выдуманное число. Тогда ответ гарантированно окажется одним из тех значений, которые программа действительно видела.
В трассе шесть показаний: -3, -7, -1, -8, -1, -12. Сравнение происходит на каждом шаге, а best меняется всего один раз – когда встречается -1. Второе значение -1 максимум уже не обновляет: оно не больше запомненного.
У всех задач такого рода один и тот же шаблон, меняются только начальное значение и правило обновления:
| Что нужно найти | Начальное значение | Обновление в теле цикла |
|---|---|---|
| максимум | первый элемент | if x > best: best = x |
| минимум | первый элемент | if x < worst: worst = x |
| количество подходящих | 0 |
if условие: count += 1 |
| сумма | 0 |
total += x |
Накопители друг другу не мешают, поэтому в одном цикле их может быть сколько угодно – и на оба вопроса из начала урока хватает одного прохода по данным. Прочитать числа дважды всё равно нельзя: input() не умеет вернуться назад.
n = int(input())
worst = int(input())
frosty = 0
if worst < 0:
frosty = 1
for i in range(n - 1):
t = int(input())
if t < worst:
worst = t
if t < 0:
frosty += 1
print(worst, frosty)
Первое показание участвует в обоих ответах, поэтому его приходится проверять отдельно, до цикла, – это плата за надёжную инициализацию первым элементом. Внутри цикла два if подряд, а не elif: условия независимы, и день может быть одновременно самым холодным и морозным.
От такой асимметрии избавляются либо циклом while со счётчиком, либо (гораздо аккуратнее) когда все данные лежат в списке и по ним можно пройти сколько угодно раз, – это блок 9.
До сих пор числа приходили извне, и цикл шёл по ним. Но перебирать можно и то, что никто не вводил, – весь диапазон возможных ответов. Задача:
Найти все трёхзначные числа, кратные 7, сумма цифр которых равна 15.
Формулу выводить не нужно: трёхзначных чисел всего 900, и человек может попросить проверить каждое по очереди.
Полный перебор – приём, при котором вместо вывода формулы перечисляются все возможные варианты, и каждый проверяется на соответствие условию.
Каркас всегда один: for по диапазону кандидатов, внутри if с условием.
for x in range(100, 1000):
if x % 7 == 0:
rest = x
digit_sum = 0
while rest > 0:
digit_sum += rest % 10
rest //= 10
if digit_sum == 15:
print(x)
range(100, 1000) – ровно все трёхзначные числа: 100 входит, 1000 нет (урок 4.4).rest: сам x портить нельзя, он ещё нужен для вывода.rest = x и digit_sum = 0 стоят внутри внешнего цикла – для каждого кандидата подсчёт начинается заново. Вынести их наружу – самая частая ошибка в таких задачах: сумма начнёт накапливаться по всем числам подряд, и условие больше никогда не выполнится.x % 7 == 0 (одна операция), и только для прошедших – разбор на цифры (три итерации). Ответ тот же, работы меньше в семь раз.Структурно это тот же вложенный перебор из урока 4.7, только внутренний цикл не перечисляет пары, а вычисляет величину для текущего кандидата.
Над одним и тем же перебором формулируются три разные задачи, и меняется только тело if:
| Вопрос | Что делаем внутри if |
|---|---|
| какие числа подходят | print(x) |
| сколько их | count += 1 |
| какое из них наибольшее | обновляем накопитель |
Третий вариант соединяет обе половины урока: экстремум ищется уже не среди введённых данных, а среди найденных перебором. И у него есть приём поизящнее накопителя – идти по диапазону с конца.
for x in range(999, 99, -1):
rest = x
digit_sum = 0
while rest > 0:
digit_sum += rest % 10
rest //= 10
if x % 7 == 0 and digit_sum == 15:
print(x)
break
else:
print('таких чисел нет')
-1 (урок 4.4) ведёт от 999 к 100, граница 99 не входит – снова «до, но не включая».break (урок 4.5) прекращает бессмысленный перебор остальных.else программа, ничего не найдя, не напечатает ничего – и по её выводу нельзя отличить «подходящих чисел нет» от «программа сломалась». else у цикла срабатывает ровно тогда, когда break не сработал; это его самое естественное применение.best здесь тоже сработал бы, но потребовал бы придумать начальное значение – а начинать «с потолка» мы решили не начинать.Ниже – трасса того же приёма на упрощённой задаче: наибольшее двузначное число с суммой цифр 15. У двузначного числа всего две цифры, поэтому сумма считается арифметикой, без внутреннего цикла, – так в трассе виден сам перебор, а не разбор на цифры.
Кандидаты 99, 98 и 97 не прошли проверку, четвёртый – 96 – подошёл, и break остановил цикл на четвёртой итерации из девяноста возможных. Блок else при этом не выполнился.
Полный перебор честно платит временем, и правило умножения из урока 4.7 действует и здесь: 900 кандидатов, у каждого до трёх итераций разбора цифр – меньше трёх тысяч операций, для компьютера незаметно. Но если бы диапазон был не трёхзначным, а девятизначным, кандидатов стало бы около миллиарда, и ответа пришлось бы ждать минуты.
Иногда перебор можно заменить арифметикой. Количество чисел, кратных k, в диапазоне от a до b считается сразу:
Квадратные скобки без верхних черт – округление вниз, то есть знакомое целочисленное деление //. Для трёхзначных чисел, кратных 7: 999 // 7 - 99 // 7 = 142 − 14 = 128.
Формула отвечает мгновенно – но только на простой вопрос. Для «суммы цифр, равной 15» такой формулы под рукой нет, и вот тогда перебор оказывается не грубым решением, а единственным разумным. Полезная привычка: если для части условия формула существует, используйте её как проверку – посчитайте перебором количество чисел, кратных 7, и сверьтесь с 128.
Обе задачи из начала урока решаются одним проходом: самая низкая температура и число морозных дней – два накопителя в одном цикле, ни одного повторного чтения данных.
Общая схема любой такой задачи – три вопроса к себе до написания цикла:
| Вопрос | Что он определяет |
|---|---|
| Что перебираем? | границы и шаг range – или чтение по одному через input() |
| Что помним? | список накопителей и их начальные значения |
| Когда обновляем? | условие внутри тела цикла |
input() это не роскошь, а необходимость – прочитать числа второй раз нельзя.for по диапазону кандидатов, внутри if с условием. Это полный перебор.range(999, 99, -1)) с break на первой находке; else у цикла отвечает, если не нашлось ничего.На этом блок про циклы заканчивается. В нём собрано всё, что нужно для таких задач: while – когда число повторений заранее неизвестно (4.2, 4.3), for и range – когда известно (4.4), break, continue и else – чтобы выйти раньше или заметить, что выхода не случилось (4.5), вложенные циклы – чтобы перебирать пары (4.7), накопители – чтобы из множества значений получить один ответ. Дальше меняются только задачи – и проверить это можно на практикуме блока.
Короткие вопросы по теме урока. Попыток сколько угодно, на прохождение блока они не влияют – это проверка для себя.