Алгоритм разделения шоколадной плиты в равных частях

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

Проблема следующая:

Info

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 x 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 разных подмножества бара.

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

Ответ 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)

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ответ 4

Возможно, вы могли бы использовать язык, подобный прологу, для решения такого рода вещей.