Donald Knuth has a chapter on "Minimum-Comparison Selection" in Volume III of The Art of Computer Programming.
Knuth says, "no general method [of selection in the minimum number of comparisons] is evident as yet" but he gives some general methods that come close to the minimum.
Looking at Table 5.3.3–1, we can see that V₄(7) = 10 (that is, you can find the 4th largest of 7 items using at most 10 comparisons), and the algorithm ("found manually by trial and error") is given in the solution to exercise 5.3.3–10.
For (7s) you know you're on the right track when you spot the flying robots (Hasse Diagram). There are two main cases to verify for 10 comps; other cases are not close to the limit. (7s) is close to a perfect puzzle, like E's Zebra Puzzle. Not too hard, but hard enough so only the disciplined will crack it on their first go.
Now (4s, 3), also with 7 numbers, is the equal of (7s). Here we assume that one of the numbers repeats three times (has multiplicity 3). I won't tell you what the answer (height of the optimal ternary dec. tree) is. Go find it fellas!
发布评论
评论（3）
Donald Knuth 在《计算机编程艺术》第三卷中有一章介绍“最小比较选择”。
Knuth 说，“目前还没有明显的通用方法（在最小比较次数中进行选择）”，但他给出了一些接近最小值的通用方法。
查看表 5.3.3–1，我们可以看到 V₄(7) = 10（也就是说，您最多可以使用 10 次比较找到 7 个项目中的第四大项），以及算法（“通过反复试验手动找到” ") 在练习 5.3.3-10 的解决方案中给出。
Donald Knuth has a chapter on "Minimum-Comparison Selection" in Volume III of The Art of Computer Programming.
Knuth says, "no general method [of selection in the minimum number of comparisons] is evident as yet" but he gives some general methods that come close to the minimum.
Looking at Table 5.3.3–1, we can see that V₄(7) = 10 (that is, you can find the 4th largest of 7 items using at most 10 comparisons), and the algorithm ("found manually by trial and error") is given in the solution to exercise 5.3.3–10.
如果您允许并行比较（现代 CPU 可能会为您执行此操作），您可以使用排序网络< /a> 分六步解决问题。
If you allow comparisons in parallel (a modern CPU will probably do this for you), you can use a sorting network to solve the problem in six steps.
在（7 秒）内，当您发现飞行机器人时，您就知道自己处于正确的轨道上（哈斯图）。对于 10 个比较，有两种主要情况需要验证；其他情况均未接近极限。
(7s) 接近完美的拼图，例如 E 的斑马拼图。不是太难，但足够难，只有纪律严明的人才能在第一次尝试时破解它。
现在 (4s, 3)，也有 7 个数字，等于 (7s)。这里我们假设其中一个数字重复 3 次（重数为 3）。我不会告诉你答案（最佳三叉树的高度）是什么。小伙伴们快去寻找吧！
For (7s) you know you're on the right track when you spot the flying robots (Hasse Diagram). There are two main cases to verify for 10 comps; other cases are not close to the limit.
(7s) is close to a perfect puzzle, like E's Zebra Puzzle. Not too hard, but hard enough so only the disciplined will crack it on their first go.
Now (4s, 3), also with 7 numbers, is the equal of (7s). Here we assume that one of the numbers repeats three times (has multiplicity 3). I won't tell you what the answer (height of the optimal ternary dec. tree) is. Go find it fellas!