Как разделить деньги без потери центов: метод наибольшего остатка

Почему один цент может разрушить ваше приложение

Разделите 10 евро на троих — и каждый получит по 3,33 евро. Итого 9,99. Один цент пропал, и вам нужно решить в коде, кто его заплатит. Это звучит как деталь округления, но на самом деле это разница между приложением, где цифры сходятся, и приложением, где они почти сходятся. Я столкнулся с этим, создавая приложение для учёта расходов, и решение оказалось алгоритмом из теории голосования 1790-х годов.

Три неправильных подхода

Округлить каждую долю

round(1000 / 3) = 333 на человека, итого 999. Вы на один цент короче. Каждый последующий баланс наследует эту ошибку, и она накапливается: пятьдесят разделов на троих — и книги группы разъезжаются на пятьдесят центов без единой строки, на которую можно указать.

Отдать остаток самой большой доле

Это частый фикс, и он работает для 10 евро. Но он не работает при неравных долях. Если кто-то ввёл точные суммы, которые не сходятся с итогом, «поглотить разницу самой большой долей» молча решает, что один человек платит на 15 евро больше, чем ввёл. Три цента округления остаются незамеченными. Пятнадцать евро тоже, пока кто-то не проверит.

Использовать float

0.1 + 0.2 != 0.3. Вы это знаете. Вся предметная область — это целые центы или ничего.

Правильное решение — метод 1792 года

Проблема (разделить целое число неделимых единиц пропорционально весам) — та же, что и распределение мест в парламенте между партиями по доле голосов. Александр Гамильтон предложил решение для Палаты представителей США в 1792 году. Оно называется метод наибольшего остатка и состоит из трёх шагов:

1. Вычислить точную (дробную) долю каждого участника.
2. Выдать каждому целую часть (floor).
3. Оставшиеся единицы раздать по одной тем, у кого наибольший дробный остаток.

Для 10 евро на троих: точная доля — 333,33 цента каждому, целая часть — 333, распределено 999, остался один цент. Все три остатка равны 0,33, поэтому один из них получает лишний цент: 334 / 333 / 333. Сумма точно равна 1000. Всегда. Не приблизительно.

Реализация на Python

Вот ядро алгоритма, работающее с целыми центами:

def prorate(total_cents: int, weights: dict[int, float]) -> dict[int, int]:
    """
    Распределяет total_cents пропорционально весам.
    Возвращает словарь: id участника -> центы.
    """
    total_weight = sum(weights.values())
    if total_weight <= 0:
        raise ValueError('Нет долей для разделения.')

    amounts = {}      # id -> целая часть
    remainders = {}   # id -> дробный остаток
    allocated = 0

    for participant_id, weight in weights.items():
        exact = total_cents * weight / total_weight
        floor = int(exact)  # отбрасываем дробную часть
        amounts[participant_id] = floor
        remainders[participant_id] = exact - floor
        allocated += floor

    left = total_cents - allocated  # сколько центов осталось

    if left > 0:
        # Сортируем участников по убыванию остатка, затем по убыванию веса, затем по id
        order = sorted(weights.keys(),
                       key=lambda pid: (remainders[pid], weights[pid], pid),
                       reverse=True)
        # Раздаём оставшиеся центы первым left участникам
        for pid in order[:left]:
            amounts[pid] += 1

    return amounts

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

Тайбрейкер — та часть, которую пропускают

Обратите внимание на сортировку: она не ограничивается сравнением остатков. Когда два остатка равны — а это как раз случай с 10 евро на троих, и вы столкнётесь с этим чаще всего, — происходит сравнение по весу, а затем по id. Без этого запасного варианта у вас недетерминированный раздел. Сортировка в Python стабильна, но даже стабильная сортировка оставляет вас во власти порядка вставки. Тот же расход, пересчитанный после редактирования, может отдать цент другому человеку. Балансы сдвигаются на цент без видимой причины. Кто-то замечает, перестаёт доверять приложению — и правильно делает.

Правило: цепочка тайбрейкеров должна заканчиваться чем-то полным и неизменным. id подходит. «Кто был добавлен в группу первым» подходит. «Какой порядок дала хеш-таблица» — нет.

Что это даёт: инвариант, который можно проверять

Как только каждый раздел точно сходится к сумме расхода, из модели бесплатно выпадает гораздо более сильное свойство. Баланс каждого участника:

balance = что заплатил - что должен + что отправил - что получил

Просуммируйте это по всем членам группы — и каждый член сокращается: каждый евро, заплаченный кем-то, кто-то должен; каждый перевод кем-то получен. Балансы группы всегда в сумме дают ровно ноль. Это не просто приятно иметь — это тестовый оракул. Он превращает «правильно ли я посчитал деньги» в одно утверждение, которое можно выполнять после каждой операции:

def test_balances_always_sum_to_zero():
    balances = calculator.for_group(group)
    assert sum(balance.cents for balance in balances) == 0

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

Три крайних случая, которые стоит позаимствовать

Отрицательные суммы

Возвраты и корректировки — это отрицательные расходы. floor(-333.33) даёт -334, а не -333, поэтому логика остатка инвертируется, и вы перераспределяете. Возьмите абсолютное значение, разделите его, а в конце примените знак. Две строки — и целый класс ошибок со знаками исчезает.

Точные суммы должны отклоняться, а не исправляться

Если режим позволяет вводить каждую долю вручную и итог не сходится, не исправляйте это молча. Отклоните ввод и назовите разницу: «Вы ввели 85,00 евро, расход составляет 100,00 евро, не хватает 15,00 евро». Тот, кто не хочет делать арифметику, может использовать другие режимы. Тот, кто хочет, заслуживает того, чтобы ему сказали об ошибке, а не тихо переписали.

Валюты с нулём десятичных

Храните всё в сотых долях независимо от валюты. ¥1500 — это 150000. Тогда одно целое число проходит через все вычисления, не зная, какая это валюта, а форматирование остаётся задачей представления.

Откуда это взялось

Я столкнулся со всем этим, создавая Kotisso — трекер общих расходов для совместного проживания, групповых поездок и разведённых родителей. Инвариант нулевой суммы — весь дизайн: всё остальное в приложении устроено так, чтобы его нельзя было нарушить.

Метод наибольшего остатка — старый, хорошо изученный и занимает около тридцати строк. Если вы где-то делите неделимые единицы пропорционально (деньги, места, запасы, лимиты запросов), вероятно, это тот алгоритм, который вам нужен, а тайбрейкер — та часть, о которой вы собираетесь забыть.

Практический вывод

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