Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Categories:

В один мешок помещается K яблок. Сколько мешков надо, если яблок - N штук.

Часто встречающаяся в программировании (тривиальная) задача:
В один мешок помещается K яблок. Сколько мешков надо, если яблок - N штук.
Нет, не N/K. И даже не (N/K)+1. На самом деле, (N+K-1)/K.

Убираем одно яблоко (т.е. остаётся N-1), если какой-то мешок заполнен не полностью, то убираем именно из него. Смотрим сколько полностью заполненных мешков нужно для такого количества. Это (N-1)/K. Добавляем обратно тот мешок, из которого вынули яблоко, получаем на 1 больше, т.е. 1 + (N-1)/K.
Почему именно одно яблоко? Потому что похожее рассуждение "уберем 0 яблок" не работает для N=42*K, а "уберём 2 яблока" не работает для N=42*K+1. Требуется чтобы мешок из которого убрали яблоки - был ровно один (для двух яблок это не так), и чтобы он перестал быть полным (для 0 яблок это не так).

Можно ещё рассуждать так: количество мешков увеличивается монотонно, и ровно на 1 при увеличении N на K. Отсюда визуальный способ мышления подсказывает, что график формулы - это "лесенка", где длина ступеньки равна K. Такая лесенка задаётся формулой N/K. Осталось только понять, как сместить вверх и вбок такой график для совпадения с искомой формулой. Значит формула должна быть вида константа1 + (N+константа2)/K, осталось подобрать константы. Разрыв в количестве мешков - в тот момент, когда яблок на одно больше, чем для полного заполнения всех мешков (т.е. N делится на K). Отсюда константа2=-1. константа1 подбирается на любом частном случае.

Чтобы формула корректно работала для N=0 и не делить отрицательное (N-1) - надо переместить слагаемое-единицу в знаменатель дроби, т.е. формула становится (N+K-1)/K.
В C/C++ отрицательные числа делятся не так, как в Python, в Python деление -1 на K сработает корректно и можно использовать 1+(N-1)/K, в C/C++ - нет, и лучше использовать (N+K-1)/K
Если K - степень двойки, то такой проблемы нет, битовые знаковые сдвиги отработают корректно в 1+((N-1)>>10).
Если N настолько большое, что есть риск IntegerOverflow - то N/K + bool(N%K)

Вроде тривиально, но как часто люди до этого не додумываются и лепят или каких-то монстров, или double-арифметику, или тратят один лишний мешок.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 86 comments