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

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

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

Информация

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

Проблема

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

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

Пример

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

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

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

4 человека с 3 перерывами по вертикальным осям
3 человека с 2 перерывами по горизонтальным осям
2 человека с 1 перерывом прямо посередине
< br> Другие эмпирические решения: (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 разных подгруппах шкалы.

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


algorithm geometry 2d
person roy100    schedule 13.05.2009    source источник
comment
ваши правила слишком строгие, чтобы разбить что-либо на n частей, вам понадобится как минимум n-1 перерыв, но, поскольку перерывы должны быть вдоль одного края, и вы не можете разделить небольшой кусок на два, также вы не можете сделать составное сломать (в разделе разъяснений) то, о чем вы просите, невозможно.   -  person z -    schedule 13.05.2009
comment
@yx Проблема заключается в том, чтобы сломать планку максимум за n перерывов. Я не думаю, что вам нужно делать сложные перерывы для достижения ограничения - у меня есть решение для n = 8 (конечно, вручную).   -  person roy100    schedule 13.05.2009
comment
Значит, решение должно выводить только p и q, а не где их сломать?   -  person Unknown    schedule 14.05.2009
comment
да. Но p и q должны быть такими, чтобы выполнялись 4 условия (хотя я не уверен, как мы будем их проверять)   -  person roy100    schedule 14.05.2009
comment
Если вы пришлете нам плитку шоколада, мы можем попробовать ее поработать. Было бы намного лучше дюжина, потому что тогда я, возможно, захочу провести несколько тестов с моими друзьями. Ни изюма, ни пузырей. Темное или молочное, пожалуйста.   -  person jbasko    schedule 14.05.2009
comment
Это можно сделать для торта: bbc.co.uk/dna/h2g2/A27360038.   -  person TRiG    schedule 07.08.2011

Ответы (3)


arrow_upward
8
arrow_downward

Мне кажется, что вы ищете числа, которые без остатка делятся на все числа от 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, НОК (4,3,2,1) = 12. Прямоугольник равен

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

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

1: ############     // 0 cuts
2: ###### ######    // 1 cut
3: #### #### ####   // 2 cuts
4: ### ### ### ###  // 3 cuts (3 being n-1)
person Welbog    schedule 13.05.2009
comment
черт возьми, я собирался опубликовать этот ответ что-то вроде прямоугольного шоколада размером 1x (LCM (факторы (n-1)) - person z -; 13.05.2009
comment
@Welbog Максимальное количество перерывов: n; не n -1. Как указано yx, n - 1 - это минимальное количество разрывов, необходимое для разбивки стержня на n частей. НОК n, n - 1, n - 2 ... 2, 1 определяет размер полосы, но не конфигурацию. - person roy100; 13.05.2009
comment
@ roy100: Смотрите мое последнее обновление. Это не имеет значения, поскольку вы всегда можете сделать это за n-1 или меньшее количество разрывов с прямоугольником размером 1 на LCM. - person Welbog; 13.05.2009
comment
Извините - забыл добавить это ограничение. р! = д! = 1. - person roy100; 13.05.2009
comment
О-ХО-ХО-ХО! Изменение характера проблемы после того, как я ее решил, а? Это просто грубо. - person Welbog; 14.05.2009
comment
Извините - забыл добавить это ограничение. p! = q! = 1 Другие эмпирические решения: (n, p, q) = (1, 1, 1); - person Unknown; 14.05.2009
comment
@Welbog - извините за это; это было имплицитно в моей голове, но просто не подавляло. См. Пояснение: 4. p или q не могут быть равны 1. yx указал в одном из ответов, что проблема легко разрешима, если на одной стороне есть 1 столбик. Это, однако, не лучшее решение для реальных ситуаций - что и было целью решения этой проблемы :) @ Неизвестно - да, я это понимаю. Я думаю, вы могли бы назвать n = 1 особым случаем - person roy100; 14.05.2009
comment
Тогда возьмите прямоугольники 2 на LCM / 2. Поскольку 2 гарантированно будет множителем, а все остальные числа гарантированно будут множителями остатка, вы всегда можете разделить такой прямоугольник на n-1 или меньше разбиений. - person Welbog; 14.05.2009
comment
Да, ты прав. Очень простое и элегантное решение :) Каким-то образом я придумал, что решение будет намного сложнее, чем это - person roy100; 14.05.2009

arrow_upward
3
arrow_downward

Поскольку вы не можете разрезать несколько частей одновременно, для любого количества частей 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)

person Community    schedule 14.05.2009
comment
Да это правильно. Хотел бы я отметить его как принятый ответ, но это было бы несправедливо по отношению к Велбогу =) Но каково математическое значение sqrt? - person roy100; 14.05.2009

arrow_upward
1
arrow_downward

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

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

person AlbertoPL    schedule 13.05.2009