比较次数求7个数字的中位数

Question

我可以通过12次比较找到中位数。但我想知道最小的比较次数以及如何进行比较。

Answer 1

Donald Knuth在“计算机编程艺术”第三卷中有一个关于“最小比较选择”的章节。

Knuth说，“在最小数量的比较中还没有明显的通用选择方法”，但他给出了一些接近最小数量的通用方法。

查看表5.3.3-1，我们可以看到V₄(7) = 10 (也就是说，你可以通过最多10次比较找到7个项目中的第四大项)，并且在练习5.3.3-10的解决方案中给出了算法(“通过反复试验手动找到”)。

Answer 2

如果您允许并行比较(现代CPU可能会为您完成此操作)，则可以使用sorting network在6个步骤中解决此问题。

Answer 3

对于(7)，当你发现飞行机器人时，你就知道你在正确的轨道上(哈斯图)。有两个主要情况需要验证10个比较；其他情况没有接近限制。(7s)接近于完美的拼图，就像E的斑马拼图。不是太难，但足够难，所以只有训练有素的人才会在第一次尝试时破解它。

现在(4s，3)，也有7个数字，等于(7s)。这里我们假设其中一个数字重复三次(重数为3)。我不会告诉你答案是什么(最优三进制十进制的高度。树)是。伙计们，去找吧！