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

топ 100 блогов _winnie22.08.2014 Часто встречающаяся в программировании (тривиальная) задача:
В один мешок помещается 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).

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

Оставить комментарий

Архив записей в блогах:
https://ru.aliexpress.com/wholesale?catId=0&initiative_id=&SearchText=led+flame+effect средняя цена за единицу около 8 долл и реклама в инста, с двумя постами об этой лампе и ссылкой на магазин туда же все накладные ресницы, нервущиеся колготки, и силиконовые формы для ...
Вы еще не забыли "народного губернатора Донецка" Губарева, баркашовца ? Похоже, гэбуха командировала на Украину членов РНЕ чуть ли не в полном составе. Сегодня целый день в блогах обсуждается разговор Александра Баркашова со своим представителем, засевшем в Донецке. Запись выложила Служ ...
Сдается мне, ой, не одну меня бесит назойливое трещание продавцов, консультантов ентих, растудыт твою через коромысло! По правилам торговли надо дать покупателю время осмотреться. Только нынче много шибко умных работников от торговли, свои правила выдумывают да у таких же идиотов ...
Если и есть идеальные штаны, то это, процентов на 80, брюки APEX от компании 5.11. Я довольно поздно пришёл к использованию одежды от 5.11. Так получилось. Потому что я же не настоящий сварщик не тактикульщик. Но пришёл и начал с рубашек. Рубашки - бомбические. Плотная ткань, карманы, ...
Еще во времена  царя Петр I по его указу было введено  в солдатский рацион так называемое «хлебное вино», офицерам, по их желанию, порцию водки заменяли на такое же количество коньяка. Во время боевых действий, а также  в длительных ...