将巧克力 block 等分的算法

Question

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

问题是这样的:

信息

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

问题

编写一个算法，输出最佳配置 (p x q)，其中酒吧可以在 n, n-1, n-2...., 2, 1 给定以下限制的人之间平均共享:< br/>
1. 一个小正方形(单位正方形)不能切割成更小的 block
2.所有的中断都必须完全沿着一个轴
3。打断的总数不能超过n(这是为了阻止低效的解决方案，例如试图将整个条打断成小块并将小块分开)
4。 p 或 q 不能等于 1。 yx 在其中一个答案中指出，如果一侧有 1 条，则该问题很容易解决。然而，这对于现实世界的情况来说并不是一个好的解决方案——这正是解决这个问题的目的:)

示例

For 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 block 。然而，在现实世界中(如果它是一 block 巧克力)，你会先把它掰成两半，然后再把每一半分别掰开。这总共有 3 次休息 - 1 次在整个杆上休息，2 次在杆的 2 个不同子集上休息。

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

Answer 1

在我看来，您正在寻找可被 1 和 n 之间的所有数字(包括 1 和 n)整除的数字。这叫做 1, ..., n 的最小公倍数。一个包含 1, ..., n 正方形的最小公倍数的正方形根据定义可以平均分为大小为 1, ..., n 的 block 。您正在寻找最多 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)