Алгоритм делить плитку шоколада на равные части

Question

В мою голову пришла случайная мысль (конечно, когда я делила шоколадку!). Мне было интересно, если есть общий алгоритм для решения этой проблемы.

Проблема выглядит так:

Информация

1. У вас есть шоколадная плитка с маленькими квадратами, расположенными в прямоугольной матрице
2. В комнате n человек

Проблема

Напишите алгоритм, который выводит оптимальную конфигурацию (p x q), в которой планка может быть распределена поровну между n, n-1, n-2...., 2, 1 людьми с учетом следующих ограничений:

1. Маленькие квадраты (единичный квадрат) нельзя разрезать на более мелкие кусочки
2. Все разрывы должны быть сделаны полностью вдоль одной оси
3. Общее количество разрывов не может быть больше n (это препятствует неэффективным решениям, таким как попытка разбить весь стержень на мелкие кусочки и разделить маленькие кусочки)
4. p или q не могут быть равны 1. yx указал в одном из ответов, что проблема легко разрешима, если у одной стороны есть 1 столбец. Это, однако, не является хорошим решением для ситуаций реального мира - целью которых было решение этой проблемы :)

Пример

Для n = 4 оптимальная конфигурация 4 х 3.

 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~
|    |    |    |    |
 ~~~~ ~~~~ ~~~~ ~~~~

Эту конфигурацию можно разделить на:

4 человека за 3 перерыва по вертикальной оси
3 человека с 2 перерывами по горизонтальной оси
2 человека с 1 перерывом по центру

Другими эмпирическими решениями являются (n, p, q) = (1, 1, 1); (2, 2, 1); (3, 3, 2); (4, 4, 3); (5, 5, 12); (6, 6, 10) OR (6, 5, 12)

Пояснения
Разрыв определяется как разрез по одной оси для подмножества стержня, если применимо. Чтобы лучше проиллюстрировать это, скажем, у вас есть 2 x 2 плитки шоколада, как это:

 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~
|    |    |
 ~~~~ ~~~~

Обычная мудрость гласит, что вам нужно сделать 2 перерыва (перпендикулярные оси посередине - вниз и поперек), чтобы разделить эту планку на 4 части. Однако в реальном мире (если бы это была плитка шоколада) вы сначала разбили бы ее пополам, а затем снова разбили каждую половину по отдельности. Это дает в общей сложности 3 перерыва - 1 перерыв на весь бар и 2 перерыва на 2 различных подмножества бара.

Я не мог найти решение где-либо в Интернете - если кто-то считает, что это не Вопрос, связанный с программированием, или решение уже существует, не стесняйтесь закрыть вопрос =)

Answer 1

Мне кажется, что вы ищете числа, которые делятся поровну на все числа от 1 до n включительно. Это называется наименьшим общим кратным 1, ..., n. Квадрат, содержащий наименьшее общее кратное 1, ..., n квадратов, по определению будет равномерно делиться на части размером 1, ..., n. Вы ищете максимум n разбиений, что добавляет дополнительной сложности к проблеме, которая может быть или не быть возможной.

Ваш пример для n = 4 - LCM (4,3,2,1), равный 12. LCM (5,4,3,2,1) - 60. LCM (6,5,4,3, 2,1) также 60.

Они всегда могут быть представлены в виде 1xLCM (n, ..., 1) прямоугольников и всегда делятся на 1, ..., n четных куч в n-1 или меньше делений.

Например, когда n = 4, LCM (4,3,2,1) = 12. Прямоугольник равен

############

И можно разделить следующим образом:

1: ############     // 0 cuts
2: ###### ######    // 1 cut
3: #### #### ####   // 2 cuts
4: ### ### ### ###  // 3 cuts (3 being n-1)

Answer 2

Поскольку вы не можете разрезать несколько кусков одновременно, для любого количества кусков m, которое вы хотите, где m находится в наборе (1..n), вам всегда будут нужны отрезки m-1. Каждый разрез создает еще один кусок, вы начинаете с одного куска.

Основываясь на предыдущем решении, я думаю, вы интуитивно искали следующий алгоритм:

A = LCM(n)
p = greatest divisor of A <= sqrt(A)
q = A/p

Алгоритмы для этого должны быть тривиальными (например, начинать с p = floor (sqrt (A)) и вести обратный отсчет до mod (A, p) == 0).

Причина, по которой вы хотите использовать sqrt, заключается в ограничении количества проверяемых вами номеров. В конце концов, у вас всегда будет один делитель <= sqrt (A) и один> = sqrt (A)

Answer 3

Хороший способ ответить на этот вопрос - использовать алгоритм поиска в ширину. Алгоритм будет пробовать каждый возможный разрыв всей плитки шоколада. Затем для каждого из этих возможных состояний проблемы, попробуйте все возможные разрывы, и это будет продолжаться, сохраняя при этом равномерность кусков.

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