Целое деление и остаток

Конфет $n$ штук, детей $k$. Сколько достанется каждому и сколько останется в вазе?

Попробуем в лоб: конфет 10, детей 3, делим — получается 3,333… Такого ответа не бывает: конфеты не режут. Обычное деление отвечает не на тот вопрос, который задан.

На самом деле вопросов здесь два, и каждому соответствует своё действие:

• сколько раз тройка помещается в десятку целиком — три раза;
• что осталось после этого — одна конфета.

Эти два действия и есть тема занятия. В Python они пишутся так:

Это не узкий приём для одной задачи. Через остаток проверяют чётность и делимость, через целое деление разбирают число по разрядам, а вместе они превращают секунды в часы, копейки в рубли и строки в страницы. До конца курса вы встретите их сотни раз.

Про целое деление и остаток достаточно помнить два факта — и почти все задачи занятия решаются сами.

Первое. Для любых целых $a$ и $b > 0$ верно

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

Второе. Остаток всегда меньше делителя и неотрицателен:

Остаток от деления на 7 — это число от 0 до 6, других вариантов нет. Остаток от деления на 2 — ноль или единица. На этом свойстве держится половина задач: «чётное ли число», «какой день недели», «в какой из семи корзин лежит предмет».

Заодно отсюда видно, почему проверка чётности не требует условия: n % 2 сама по себе равна нулю для чётных и единице для нечётных.

Чему равны 17 // 5 и 17 % 5?

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

3725 секунд — это сколько часов, минут и секунд?

n = int(input())

hours = n // 3600        # 1 час
rest = n % 3600          # 125 секунд сверх часа
minutes = rest // 60     # 2 минуты
seconds = rest % 60      # 5 секунд

print(hours, minutes, seconds)

Обратите внимание на переменную rest. Без неё легко написать n // 60 вместо rest // 60 и получить все минуты, включая те, что уже посчитаны часами. Это самая частая ошибка в таких задачах, и она не видна на маленьких примерах: на входе 125 обе записи дадут одинаковый ответ, а на 3725 — разный.

Тот же приём работает везде, где есть единицы разного размера: рубли и копейки (делитель 100), килограммы и граммы (1000), недели и дни (7), страницы и строки (сколько строк на странице).

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

n = 4271

print(n % 10)         # 1  — последняя цифра
print(n // 10)        # 427 — число без последней цифры
print(n // 10 % 10)   # 7  — цифра десятков
print(n // 100 % 10)  # 2  — цифра сотен

Схема общая: чтобы добраться до цифры на позиции $k$ справа, сначала отбрасывают младшие разряды целым делением, а потом берут нужный остатком:

Здесь 10 ** (k - 1) — оператор степени, который мы видели на прошлом занятии.

Почему не через строку? Через строку тоже можно, и иногда так короче. Но задачи на числа часто приходят с ограничением вроде $10^{18}$, где важна скорость, а ещё чаще требуется не «показать цифру», а что-то с ней сделать: сложить, сравнить, перенести в другой разряд. Арифметика для этого удобнее.

Чему равно 4271 // 10 % 10? Введите одну цифру.

Третий приём — и самый неочевидный. Задача: школьников $n$, в автобус помещается $k$, сколько автобусов заказать?

Целое деление отбрасывает остаток, а оставшихся школьников всё равно надо везти. Первое, что приходит в голову, — проверить остаток условием. Но есть запись без всякого условия:

print((n + k - 1) // k)

Разберём, почему она верна. Запишем $n = q \cdot k + r$, где $r$ — остаток, $0 \le r < k$.

Если $r = 0$ (делится нацело). Тогда $n + k - 1 = q \cdot k + (k - 1)$, а $k - 1$ меньше $k$ — до следующего кратного не дотягивает. Целое частное остаётся равным $q$: ровно столько автобусов и нужно.

Если $r > 0$. Тогда $n + k - 1 = q \cdot k + (r + k - 1)$. Поскольку $r \ge 1$, сумма $r + k - 1$ не меньше $k$, но меньше $2k$. Значит частное равно $q + 1$ — к полным автобусам добавляется один неполный, где поедут оставшиеся.

Прибавление $k - 1$ переводит число через ближайшее кратное ровно тогда, когда остаток ненулевой. Отсюда и берётся формула.

Запомнить проще так: «округление вверх» — это (n + k - 1) // k, и она понадобится не раз: сколько коробок, сколько страниц, за сколько заходов.

Дни недели нумеруются от 1 до 7, первый день года — понедельник. Какое выражение даст номер дня недели для n-го дня года?

Есть место, где // ведёт себя не так, как ожидает большинство. В Python целое деление округляет вниз, к меньшему числу, а не к нулю:

print(7 // 2)     #  3
print(-7 // 2)    # -4, а не -3
print(-7 % 2)     #  1, а не -1

Логика тут своя и последовательная: равенство $a = (a // b) \cdot b + (a \% b)$ должно оставаться верным, а остаток — неотрицательным. Проверим: $-4 \cdot 2 + 1 = -7$. Сходится.

В других языках это устроено иначе — например, в C++ -7 / 2 даёт -3. Поэтому решение, перенесённое с чужого разбора, может вести себя не так, как ожидалось.

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

Каким знаком в Python записывается остаток от деления? Напишите только сам знак.

Дробь вместо целого. print(10 / 5) печатает 2.0, и это неверный ответ там, где просили штуки. Если ответ считается в предметах, людях или коробках — деление только //.

Забытый остаток при разборе величины. n // 60 вместо rest // 60 даёт все минуты, а не минуты сверх часов. На маленьком примере из условия ошибка не видна — проверяйте на числе больше делителя следующего уровня.

Нумерация с единицы. Остаток от деления на 7 даёт значения от 0 до 6, а дни недели — от 1 до 7. Прямой остаток даст ноль там, где нужна семёрка. Лечится сдвигом: вычесть единицу до деления, прибавить после.

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

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

1. ноль — если он допустим по ограничениям;
2. точное деление — например 60 секунд, 100 копеек: остаток нулевой;
3. число заметно больше делителя — 3725 секунд, а не 125: покажет забытый остаток.

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

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

Разминка отрабатывает // и % в чистом виде. Основа — разбор величины по частям и разряды числа. Со звёздочкой — те, где приём нужно применить несколько раз подряд или догадаться, как обойтись без условия.

Ученик решал задачу «дано число секунд, выведите часы, минуты и секунды» и написал:

n = int(input())
print(n // 3600, n // 60, n % 60)

На примере из условия — 125 секунд — программа напечатала 0 2 5, что верно. Но решение не приняли.

Объясните, в чём ошибка, на каких данных она проявляется и как её исправить.