algorithm - 通过最多问 8 个问题找到最重的球

Question

给定 6 个具有不同 重量的球。目的是找到这些球中最重的一个。

问题以问答方式进行，即我们必须提出问题，问题设置者为我们提供答案。每个问题包括给出 6 个指标中的 5 个指标。返回的答案是第 3^rd 最重和第 2^nd 最重球的索引(按此顺序)。我们最多可以问 8 个这样的问题来找到最重的球。

示例:

假设球的索引是 - 1,2,3,4,5,6。

Q : 1 2 3 4 5     A : 3 4   (here 3 is the third most and 4 is the second most heaviest of the 5 balls)

Q : 1 2 3 4 6     A : 3 4

Q : 1 2 3 5 6     A : 3 5

Q : 1 2 4 5 6     A : 4 5

Q : 1 3 4 5 6     A : 4 5

Q : 2 3 4 5 6     A : 4 5

这 6 个问题足以确定指数为 6 的球是最重的。 (仍然可以再问 2 个问题 - 我们不需要尽量减少问题的数量。此外，这些查询可能会或可能不会对所有 6 个数字进行排序，我们的目标是只找到最重的)。

---

我正在寻找解决此问题的通用方法(最好不涉及基于案例的分析)。

Answer 1

这好像不是编程。而且我怀疑你编造了这个谜题，因为如果它来自一个谜题网站，他们应该知道它永远不需要超过 5 个问题。

首先，在你的前 3 个问题之后，已知答案是 6。怎么会这样？问题 2 的答案没有改变的事实表明，要么 5 和 6 都 > 4 > 3，要么都 < 3 < 4。在问题 3 中，显示 5 > 3 因此 6 > 3。事实5 出现在 #2 中表示某物大于 5，唯一可能的答案是 6。所以我们完成了!

您只需要知道您正在收集哪些信息并充分应用它。

现在让我们以更通用的方式解决问题，这样我们可以更快地解决问题。

第一轮我们什么都不知道，所以我们加权1 2 3 4 5 .这将产生一个答案 x y .交流x与 6然后再试一次。以下是可能性:

1. 如果我们得到 y z与 z不是 6 ，那么我们的答案是6出于与之前找到答案相同的推理，在 2 个问题中。
2. 如果我们得到 y 6或 6 y那么它不是x , y或 6 .我们交流x对于其他三个中的每一个，直到第二名答案发生变化。发生这种情况的问题最重，最多 5 个问题。
3. 如果我们得到 z y与 z不是6然后 6比y轻(否则它会把它推下来)。我们现在知道答案不是 x , y , z或 6 .所以我们只需要交换x与其他两个依次应用与以前相同的推理，在最多 4 个问题中找到最重的问题。