将巧克力棒分成等份的算法 [英] Algorithm to divide a chocolate bar in equal parts

问题描述

一个随机的想法突然出现在我的脑海中(当然是在我分享巧克力棒的时候！).我想知道是否有通用算法来解决这个问题.

A random thought popped into my head (when I was sharing a chocolate bar of course!). I was wondering if there is a generic algorithm to solve this problem.

问题是这样的:

信息

1. 你有一个巧克力棒，上面有排列成矩形矩阵的小方块
2.房间里有n个人

Info

1. You have a chocolate bar with small squares arranged in a rectangular matrix
2. There are n people in the room

问题

编写一个算法，输出最优配置 (pxq)，其中 bar 可以在 n, n-1, n-2...., 2, 1 人之间平均分配，但有以下限制:

1.一个小方块(单位方块)不能切成小块
2.所有中断都必须完全沿着一个轴
3.中断的总数不能超过 n(这是为了阻止低效的解决方案，例如试图将整个条分成小块并将小块分开)
4.p 或 q 不能等于 1. yx 在其中一个答案中指出，如果一侧有 1 bar，则问题很容易解决.然而，这对于现实世界的情况并不是一个好的解决方案 - 这是解决这个问题的意图:)

示例

对于 n = 4，最佳配置为 4 x 3.

The problem

Write an algorithm that outputs the optimal configuration (p x q) where the bar can be shared equally between n, n-1, n-2...., 2, 1 people given the following restrictions:

1. A small squares (the unit square) cannot be cut into smaller pieces
2. All breaks have to be made completely along one axis
3. The total number of breaks cannot be more than n (this is to discourage inefficient solutions such as trying to break the whole bar apart into small pieces and dividing the small pieces)
4. p or q cannot be equal to 1. yx pointed out in one of the answers that the problem is easily solvable if one side has 1 bar. This, however is not a good solution for real world situations - which was the intent of solving this problem :)

Example

For n = 4, the optimal configuration is 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 巧克力棒:

This configuration can be divided among:

4 people in 3 breaks along the vertical axes
3 people with 2 breaks along the horizontal axes
2 people with 1 break right down the middle

Other empirical solutions are (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)

Clarifications
A break is defined as a cut along one axis for the subset of the bar, if applicable. To better illustrate this, say you have a 2 x 2 chocolate bar like this:

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

传统观点认为，您需要进行 2 次折断(中间的垂直轴 - 向下和交叉)才能将此条分成 4 部分.但是，在现实世界中(如果它是巧克力棒)，您会先将其分成两半，然后再将每一半分开.这总共有 3 次休息 - 在整个酒吧上休息 1 次，在酒吧的 2 个不同子集上休息 2 次.

我在互联网上的任何地方都找不到解决方案 - 如果有人觉得这不是一个编程相关问题或解决方案已存在，请随时关闭问题 =)

Conventional wisdom says you need to make 2 breaks (the perpendicular axes in the middle - down and across) to divide this bar into 4 pieces. However, in the real world (if it were a chocolate bar), you would first break it in half and then break each half again, separately. This makes a total of 3 breaks - 1 break on the entire bar and 2 breaks on 2 different sub sets of the bar.

I couldn't find solution anywhere on the internet - if anyone feels this is not a programming related question or a solution already exists, feel free to close the question =)

推荐答案

在我看来，您正在寻找可以被 1 和 n 之间的所有数字整除的数字.这称为 1, ..., n 的最小公倍数.根据定义，包含 1, ..., n 个正方形的最小公倍数的正方形将被均匀划分为大小为 1, ..., n 的部分.您正在寻找最多 n 个拆分，这会增加问题的复杂性，这可能或不可能.

It seems to me that you're looking for numbers that are evenly dividable by all numbers between 1 and n inclusive. That's called the least common multiple of 1, ..., n. A square containing the least common multiple of 1, ..., n squares would by definition be evenly dividable into pieces of size 1, ..., n. You're looking for a maximum of n splits, which adds additional complexity to the problem which may or may not be possible.

您的 n = 4 示例是 LCM(4,3,2,1)，即 12.LCM(5,4,3,2,1) 是 60.LCM(6,5,4,3,2,1) 也是 60.

Your example for n = 4 is the LCM(4,3,2,1) which is 12. LCM(5,4,3,2,1) is 60. LCM(6,5,4,3,2,1) is also 60.

它们总是可以布置为 1xLCM(n,...,1) 个矩形，并且总是可以分成 1,...,n 个甚至 n-1 个或更少的分区的堆.

They can always be laid out as 1xLCM(n,...,1) rectangles, and always be dividable into 1,...,n even piles in n-1 or fewer divisions.

例如当n = 4时，LCM(4,3,2,1) = 12.矩形为

For example, when n = 4, LCM(4,3,2,1) = 12. The rectangle is

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

又可以分为:

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

这篇关于将巧克力棒分成等份的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！