将巧克力棒分成相等部分的算法 [英] Algorithm to divide a chocolate bar in equal parts
问题描述
问题是这样的：
信息
1.你有一个巧克力块，上面摆放着一个矩形的矩形小方块。
2.房间里有n个人
问题
编写一个算法，输出可以共享条的最佳配置（pxq）同样介于 n，n-1，n-2 ....，2，1 之间的人有以下限制：
1。一个小方块（单位正方形）不能被切成小块 - 2。所有的休息必须完全沿着一个轴进行 - 3。总休息次数不能超过n次（这是为了阻止低效率的解决方案，比如试图将整个酒吧分成小块并分成小块）4。 p或q不能等于1. yx在其中一个答案中指出，如果一方有1巴，问题很容易解决。然而，这对于现实世界的情况并不是一个好的解决方案 - 这是解决这个问题的意图:)
示例
对于n = 4，最优配置是4 x 3.
~~~~ ~~~~ ~~~~ ~~ ~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
配置可分为：
3人中有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）或（6,5,12）
说明
中断被定义为沿着一个轴的切条形的子集（如果适用）。为了更好地说明这一点，假设你有这样一个2 x 2巧克力棒：
~~~~ ~~~~
| | |
~~~~ ~~~~
| | |
~~~~ ~~~~
传统观点认为您需要制作2个中断（中间的垂直轴线向下和横向）将该条分成4个部分。然而，在现实世界中（如果它是一个巧克力棒），你首先将它分成两半，然后分别再分成两半。这总共有3次休息 - 1次休息，2次休息，2次休息。
我找不到任何地方的解决方案 - 如果有人觉得这不是一个解决方案编程相关的问题或解决方案已经存在，随时关闭这个问题=） 解决方案
在我看来，你是寻找可以被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。矩形是 $> b
$ b b $ b
############
可分为以下几种：
1：########### ＃// 0削减
2：###### ###### // 1削减
3：#### #### #### // 2削减
4：### ### ### ### // 3个剪辑（3个是n-1）
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.
The problem goes like this:
Info
1. You have a chocolate bar with small squares arranged in a rectangular matrix
2. There are n people in the room
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.
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
| | | | |
~~~~ ~~~~ ~~~~ ~~~~
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:
~~~~ ~~~~
| | |
~~~~ ~~~~
| | |
~~~~ ~~~~
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 =)
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.
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.
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.
For example, when n = 4, LCM(4,3,2,1) = 12. The rectangle is
############
And can be divided as follows:
1: ############ // 0 cuts
2: ###### ###### // 1 cut
3: #### #### #### // 2 cuts
4: ### ### ### ### // 3 cuts (3 being n-1)
这篇关于将巧克力棒分成相等部分的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
