我可以通过 12 次比较找到中位数。但是我想知道最少的比较次数以及如何进行比较。
问问题
2153 次
3 回答
9
Donald Knuth 在The Art of Computer Programming 的第三卷中有一章关于“最小比较选择” 。
Knuth 说，“目前还没有[在最小比较次数中选择] 的通用方法是显而易见的”，但他给出了一些接近最小值的通用方法。
查看表 5.3.3-1，我们可以看到 V₄(7) = 10（也就是说，您最多可以使用 10 次比较找到 7 个项目中的第 4 大），以及算法（“通过反复试验手动找到") 在练习 5.3.3-10 的解法中给出。
于 2010-11-11T12:32:42.070 回答
1
如果您允许并行比较（现代 CPU 可能会为您执行此操作），您可以使用排序网络分六个步骤解决问题。
于 2010-11-11T23:38:16.480 回答
0
对于（7s），当您发现飞行机器人时，您知道自己走在正确的轨道上（哈斯图）。有两个主要案例需要验证 10 个组合；其他情况没有接近极限。(7s) 接近于完美的拼图，例如 E 的斑马拼图。不是太难，但足够难，所以只有受过训练的人才会在第一次尝试时破解它。
现在 (4s, 3) 也有 7 个数字，等于 (7s)。在这里，我们假设其中一个数字重复了 3 次（重数为 3）。我不会告诉你答案（最佳三元 dec. 树的高度）是什么。小伙伴们快去找吧！
于 2019-05-08T03:12:01.357 回答