将巧克力 block 等分的算法

标签 algorithm geometry 2d

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

问题是这样的:

信息

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 个不同子集上休息。

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

最佳答案

在我看来,您正在寻找可被 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)

关于将巧克力 block 等分的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/859922/

相关文章:

c# - 翻转顶点数组

java - 如何使用 circle.java 计算圆柱体的 getVolume。 [2个类(class)]

algorithm - 任何人都知道我是否可以找到一个算法或有一个他们可以共享的算法来将球体(网格)分成随机部分?

c# - SlimDX 中的二维三角形

.net - 如何衡量字符串的复杂度?

java - 使用散列法查找总长度最小的字符串子数组,该子数组包含原始数组中的所有不同字符串

c - openGL 2D鼠标点击位置

linux - 适用于 Linux 的 2D 渲染库(和视频)

opengl - OpenGL 中的 2D 绘图 : linear filtering with pixel accuracy at native size

顶点权重和边操作的多边形算法