Как минимально поделить число на 2 и 3 столько раз сколько будет нужно?

Question

[21ken]

Представьте что существует гостиница с комнатами на двух и трех человек. На входе дается число - сколько людей заселяется, а на выходе нужно указать какое минимальное количество комнат они смогут занять.
Например, на пять человек - 2 комнаты(2 мест и 3 мест), на 6 человек - 2 комнаты по 3 места, на 7 тоже 3(2 комнаты по 2 места и 1 по 3-х местка) и так далее. Количество людей может быть любым, хоть 20, хоть 30.
Как написать такой алгоритм?

Comments

[sswwssww]

Почему на 6 человек 3 комнаты?

[Алан Гибизов]

Как написать алгоритм? Очень просто.
Разделить задачу на части, например:

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

Это самый тупой вариант, но принципиально должен работать.

[o5a]

В описании задачи не указано, чтобы распределение по комнатам было оптимальным, только про минимальное количество. Если оптимальное распределение действительно не требуется, все решается проще: сортируем наши размеры комнат по убыванию и в цикле делим людей (с учетом остатка) на размер комнат.

[shurshur]

Я присоединяюсь к вопросу о том, почему на 6 человек нужно 3 комнаты? А так задача тривиальна в такой постановке вопроса:

rooms = math.ceil(humans/3)

Нужно просто по максимуму использовать комнаты на 3 человека.

Answer 1

[Валерий Мамонтов]

21ken, добрый день!
Есть хорошая книга "Грокаем алгоритмы", в неё рассматривается похожая задача про Рюкзак.

Answer 2

[AbramovKS]

Если комнат бесконечное количество)
Делим кол-во людей на вместительность самой большой комнаты.
Например 8 людей / 3 мест. = 2, остаток 2 чел
Остаток делим на 2 местные и повторяем пока не вселим всех.

На вскидку в псевдокоде

humans = 8
capacity = 3 #вместительность самой большой комнаты

while(humans>0){
ok = Math.trunc(humans/capacity) #вселили количество
humans -= ok * capacity #осталось вселить
capacity -= 1 #уменьшаем вместительность комнат и повторяем

if(ok==0){
humans = 0 #если все вошли в одну комнату без остатка например 2 в 3 мест.
}

}