初步思考
- 64匹马,8赛道,很容易想到一直 除以8,显然会有很多重复的比较。
- 还有一个大前提,所有的马都至少要跑一次,这样才能纳入统计。
分析
- 每一匹都得先跑一次,64匹,8个赛道,那就先分8组跑8次。
- 每一组都会得到8匹的相对速度,也就是在同一组内的名次。
- 为了方便描述,我们用编号来表示。其下标表示名次。
- 只需要找前四,所以每组的后四名都被淘汰,不需要再比。「此时已经比了8场」
- 现在每一组内都有相对名次,但不同的组间是不知道的。如果把A组和B组放一起,下面的情况都可能存在。
📌注:接下来是缩小比较次数的关键:选择每组的第一名再出来跑一次。落后的第一名所在的整组都可以排除。
- 为了描述方便,把最快到最慢的第一名所在的组依次重新命名为A,B...H组。「这里比了1场」
-
一样取前四,后面四整组都被淘汰。「因为他们组的第一名都被淘汰了,组员肯定都被淘汰」
-
这时候已经确定了最快的马,「A1」。然后就可以在剩下 15 只马中排除一些不可能是总体前4的马。分别是「B4」「C3 C4」「D2 D3 D4」,如下图所示。
- 可以这样理解,A1是第一名,所在的组都是「精英组」,理论上是可能A组4匹马都是前4,所以都保留名额,其他组同样思考。假设A组只有A1进入前4,B组全员进名次,这样就不可能排到B4,所以排除「B4」。同理,剩下的C组D组都可以这样思考,注:C组判断时,A1和B1肯定都在C组全员之前的。
- 剩下的9匹马选3只即可。赛道只能放8匹马,这里先把「A4」这匹马放一边,然后剩下的进行比较。
- 如果「A3」在第三名或更后,说明那3名已经选出来了「A4」不需要再跑了。「这样就是10场」
- 否则,再拉「A4」跟前三再比一场,这样即可选出三个名额。「这样就是11场」
总结
- 最少需要10场。
- 最多需要11场。
- 就可以把前4名选出来。
图源:小K算法
网友评论