将巧克力棒均分的算法

Question

将巧克力棒均分的算法

12

当我和别人分享巧克力时，突然蹦出一个想法。我在想是否存在一个通用算法来解决这个问题。

问题是这样的：信息

1. 你有一块由小正方形排列成矩形状的巧克力
2. 房间里有n个人问题

编写一个算法，输出最佳配置（p x q），其中棒可以在给定以下限制的情况下平均分配给n、n-1、n-2....、2、1人：

1.小正方形（单位正方形）不能被切成更小的碎片
2.所有断裂必须完全沿着一个轴进行
3.断裂的总数不能超过n（这是为了防止低效的解决方案，例如试图将整个棒分成小块并将小块分开）
4.p或q不能等于1。yx在其中一个答案中指出，如果一侧有1根棒，则问题很容易解决。然而，这不是解决这个问题的好方法，因为这是解决实际问题的意图 :)

例子

对于n = 4，最佳配置是4 x 3。

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

此配置可分为：

纵轴上有3个断点的4人组
横轴上有2个断点的3人组
中间有1个断点的2人组

其他经验解决方案为(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的巧克力条如下：

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

传统智慧认为，你需要在中间做两个断口（垂直交叉的轴线），将这根棒子分成4块。然而，在现实世界中（如果它是一根巧克力棒），你首先会把它对半断开，然后再分别断开每一半。总共需要3个断口-整根棒子一个断口，以及在两个不同的子集上各自断口。

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

- roy100

2

你的规则太过严格了。为了将任何东西分成n个部分，你至少需要n-1次断裂，但由于断裂必须沿着一条边进行，并且不能将小块分成两个部分，同时你也不能进行复合断裂（在你的澄清部分），所以你所要求的是不可能实现的。 - z -

@yx 这个问题涉及到最多使用n次断开栏杆。我认为您不需要进行复合断裂来满足约束条件 - 我已经手动解决了n = 8的情况。 - roy100

所以解决方案只需要输出p和q，而不是在哪里断开它们？ - Unknown

是的，但是p和q必须满足这4个条件（虽然我不确定我们将如何进行验证）。 - roy100

3

如果您寄给我们一块巧克力，我们可以尝试着处理它。如果您能寄来12块的话，那会更好，因为这样我就可以和朋友们一起进行测试了。请不要放葡萄干和气泡，黑巧或牛奶巧克力都可以。 - jbasko

1

可以为蛋糕做到这一点：http://www.bbc.co.uk/dna/h2g2/A27360038。 - TRiG

3个回答

3

由于无法同时切割多个部件，对于您想要的任何数量为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)。

- user106752

是的 - 没错。但我不能将其标记为被接受的答案，因为这对Welbog不公平 =)sqrt有什么数学意义呢？ - roy100

1

回答这个问题的好方法是使用广度优先搜索算法。该算法将尝试整个巧克力棒的每一个可能的断点。然后针对问题的每个可能状态，尝试所有可能的断点，并在保持块的平均性的同时继续进行。

我想补充说，规则将强制执行哪些巧克力棒的断点是合法的，而那些不合法的可能状态将从算法中被剔除。

- AlbertoPL

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Welbog · Accepted Answer

我认为你正在寻找能够被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)的矩形，并且总是可以在n-1次或更少的划分中被均匀地分成1到n个堆。

例如，当n=4时，LCM(4,3,2,1)=12。矩形如下所示：

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

可以分为以下几个部分：

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