8

这是为了在算法课程中获得额外的学分。问题说明

国王有N瓶酒窖，单瓶中毒。
毒药大约需要一个月才能起作用。国王希望在一个月内使用尽可能少的测试人员识别出准确的瓶子。

我的解决方案是

  • 将N瓶子分成M多个批次并使用“M 测试仪”

    • 第一个测试者品尝第一批和最后一批

    • 第二个测试者品尝第一批和第二批。

    • 第三个测试者品尝了第二批和第三批。

    • 继续进行 M 批次，测试人员重叠批次。

  • 当品尝到受污染葡萄酒的两名测试人员生病时，该批次已被确定。M-2测试人员从受污染的批次中给每个人留下一瓶味道，第三个生病的测试人员识别出受污染的瓶子。

然而，这个算法需要双倍的工作时间：一个月来识别受污染的批次，第二个月来识别受污染的瓶子。有没有更高效的算法？

4

4 回答 4

7

我们可以log2(N)使用非常简洁的算法与测试人员一起完成。

让我用一个简单的例子来演示一下。假设N = 1000。

如果我们0通过标记瓶子999，那么每个瓶子都可以用一个唯一的二进制数表示，范围从0000000000（0十进制）到111100111（999十进制）。

声称：我们只需要 10 名测试人员就可以找到毒瓶。注意：log2(N) = log2(1000) = 10。

算法：对于第Mth 瓶，我们首先得到 的 10 位二进制表示M。如果i二进制数的第 th 位是1，我们让第ith 测试者喝瓶子里的酒。注意：0 < M <1000, 0 < i <10。

考虑一个示例，其中1st, 4th,9th测试人员已死亡，而其他测试人员在一个月后还活着。我们得出结论，289th瓶子是有毒的，因为0100100001它是十进制数的二进制表示289。

为什么10测试人员足以识别1000瓶子中的中毒者？

因为10最终测试人员每个人都死了还是活着，我们可以有一个总共的1024组合，每个组合都可以用来唯一地识别一个瓶子是否有毒1024。

于 2013-01-19T05:11:16.380 回答
5

这是一个经典的谜题，所以我不想立即给出答案，但这里有一个提示：假设你将酒瓶分成两组，每组包含一半的瓶子，然后让一个人测试每一半. 这会给你一种方法来缩小哪个瓶子中毒到一半的瓶子。

所以问题是——有没有办法想出许多不同的方法来将酒瓶分成两半并并行运行上述方法？作为提示，请考虑 N 的二进制表示。

希望这可以帮助！

于 2013-01-18T19:57:37.243 回答
0

这是我的建议。这基本上来自并行算法。

  1. 将瓶子分成 n/log2(n)。将每个部门称为要解决的子问题。
  2. 将每个 log2(n) 测试人员分配给步骤 1 中的每个子问题。
  3. 最后说一个测试员死了，假设我们还剩下 log2(n) 个瓶子和 log2(n) - 1 个测试员。
  4. 每个测试员测试一瓶。还剩下一瓶。
  5. 如果没有测试人员死亡（或者至少在最初几天出现症状……这是我的假设），那么我们就知道罪魁祸首是留下的瓶子。
  6. 如果任何一名测试人员死亡（或至少表现出生病），那么我们就知道该测试人员测试过的瓶子是罪魁祸首。

这需要 log2(n) + 1 个月。由于 1 是一个常数，我们可以忽略它并且可以说它是 O(log2(n))。

于 2013-10-13T18:50:45.610 回答
0

举个例子：

从 1 到 n 标记每个瓶子，并将每个瓶子视为二进制数。例如 11 瓶

00000001 
00000010 
00000011 
00000100 
00000101 
00000110 
00000111
00001000 
00001001 
00001010 
00001011

现在，从右到左，首先从最右边位设置为“1”的每个瓶子中取一滴，然后放入第一个杯子中。其次，从第二位设置为“1”的每个瓶子中取一滴，然后放入第二个杯子中。
以类似的方式继续通过最高位。所以我们总共需要 4 个杯子和 4 个品尝者。

taster4 taster3 taster2 tester1
cup4     cup3    cup2     cup1

我们现在将品尝者映射到杯子并将杯子映射到比特，因此将品尝者映射到比特命令品尝者喝。一个月后，你的一些品酒师会死掉。例如，品尝者 3 和品尝者 1 变为死状态，然后将相应的位设置为 1，将所有其他位设置为 0。生成的二进制数 00000101将识别毒瓶。品尝者的数量 f(n) = (int)(logn)+1 ，所以 f(n) 是 O(logn)

于 2016-01-31T05:46:59.553 回答