Накопление: сумма, произведение, количество

Задача: дано сто чисел, найдите их сумму. Числа приходят по одному, и вы видите каждое ровно один раз.

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

s = 0                    # место для ответа — до цикла

for i in range(1, 6):
    s = s + i            # каждый шаг что-то добавляет

print(s)                 # 15, один раз и в конце

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

Запись s = s + i встречается так часто, что для неё есть короткая форма: s += i. Так же работают -=, *=, //=.

Почти любая задача на цикл — это один из трёх накопителей или их сочетание.

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

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

count = 0

for i in range(1, n + 1):
    if i % 7 == 0:
        count += 1        # прибавляем не всегда, а по условию

print(count)

Программа должна перемножить пять введённых чисел. С какого значения нужно начать накопитель?

До сих пор входные данные помещались в одну-две строки. Теперь их много, и читать их надо в цикле:

n = int(input())          # сколько чисел будет
s = 0

for _ in range(n):        # ровно n раз
    x = int(input())      # очередное число
    s += x

print(s)

Подчёркивание вместо имени переменной — обычное соглашение: «номер шага мне не нужен, важно только количество повторений». Можно написать и for i in range(n), никакой ошибки не будет.

Обратите внимание, чего здесь нет: нигде не хранятся все сто чисел. Каждое живёт один шаг цикла и заменяется следующим. Накопитель — единственное, что переживает шаг.

Это не экономия ради экономии. В олимпиадных задачах чисел бывает миллион, и «сохраню всё, потом разберусь» упирается в память. Привычка собирать ответ по ходу пригодится дальше постоянно.

Поиск наибольшего — тот же накопитель, только вместо сложения сравнение:

best = 0

for _ in range(n):
    x = int(input())
    if x > best:
        best = x

print(best)

На числах 3, 8, 5 программа выдаст 8 — верно. На числах −3, −8, −5 она выдаст 0, которого во входных данных вовсе не было.

Причина в начальном значении: ноль оказался больше всех настоящих чисел, и ни одно из них не смогло его вытеснить. Ошибка коварная тем, что на «нормальных» тестах не видна.

Два надёжных способа

Первое число как начало. Читаем его отдельно, до цикла, и сравниваем с остальными.

Признак «ещё ничего не встречалось». В Python для этого есть None:

best = None

for _ in range(n):
    x = int(input())
    if best is None or x > best:
        best = x

Первое же число заменит None и станет отправной точкой. Способ работает и там, где подходящих чисел может не оказаться вовсе — например, «наибольшее чётное, а если чётных нет, скажи об этом».

Программа ищет наибольшее из введённых чисел, начиная с best = 0.

На вход подали −7, −2, −9. Что она выведет и почему?

Отдельный приём — когда важна не сама величина, а её сравнение с предыдущей: «сколько раз число выросло», «какая самая длинная серия одинаковых».

Хранить весь набор для этого не нужно, хватает одной дополнительной переменной:

previous = None
count = 0

for _ in range(n):
    x = int(input())
    if previous is not None and x > previous:
        count += 1
    previous = x            # ключевая строка: готовимся к следующему шагу

print(count)

Последняя строка тела — самая важная и самая забываемая. Без неё previous навсегда останется первым числом, и программа посчитает совсем другое.

На первом шаге предыдущего числа ещё нет — отсюда проверка на None. Пар всегда на одну меньше, чем чисел.

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

Печать внутри цикла. print сдвинут в тело — вместо одного числа выводится вся история накопления. Ответ в последней строке верный, но вердикт всё равно неверный.

Максимум с нуля. Разобран выше. Проверяется одним тестом: подайте только отрицательные числа.

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

У задач этого занятия есть три теста, которые ловят почти всё:

• одно число — работает ли программа, когда цикл выполняется один раз;
• все числа отрицательные — не выдумала ли программа ноль;
• все числа одинаковые — не потерялись ли повторы там, где сравнение строгое.

Прогоняйте их до отправки, а не после первого неверного вердикта.

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

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

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

Задача: «дано $n$ чисел, выведите их сумму и наибольшее из них».

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

n = int(input())

for _ in range(n):
    s = 0
    best = 0
    x = int(input())
    s += x
    if x > best:
        best = x

print(s, best)

Программа почти всегда отвечает неверно. Найдите обе ошибки, объясните, что именно она выведет на числах 4, −7, 2, и как её исправить.