64匹马、8赛道,至少多少轮比赛找出速度最快的4匹马?

一共需要比赛的场次:10场或者11场

8 + 1 + 1 + 1 = 11 场或8+1+1=10场

10场合11场前面的两次比较都是一样的主要区别在于最后两场的比较

解题思路如下:

第一步

全部马分为8组,每组8匹,每组各跑一次,然后淘汰掉每组的后四名,如下图(需要比赛8场)

这里写图片描述

第二步

取每组第一名进行一次比赛,然后淘汰最后四名所在组的所有马,如下图(需要比赛1场)

原因是:该组最快的马也不能跑进前4名那么该组所有的马都不是前4名的马匹。同时也能知道在这次比赛中跑最快的一定是所有马匹的冠军。

这里写图片描述


这个时候总冠军已经诞生,它就是A1,蓝色区域(它不需要比赛了),而其他可能跑得最快的三匹马只可能是下图中的黄色区域了(A2,A3,A4,B1,B2,B3,C1,C2,D1,共9匹马)

备注:下面的图中的A1 B1不是前面的A1和B1了,这是重新排序后的,通过上面的比赛可以知道A1>B1>C1>D1(马匹速度)

这里写图片描述

第三步

只要从上面的9匹马中找出跑得最快的三匹马就可以了,但是现在只要8个跑道,怎么办?

此时我们可以把接下来的比较分为两种情况:因为我们前面已经知道了A1>B1>C1>D1,此刻我们假设D1是第四名,那么需要比较的是A2、B2、C2、A3、B3、A4、D1,如果D1在此组跑最快,则可以知道D1就是第四名(因为前面我们已经知道了A1>B2>C1>D1)则就可以知道前四名的马匹了,总共比较次数是10场。

如果此时D1不是跑最快的,则我们前面的假设是不能确定的只能知道A1还是第一名其他的2-4名还不能确定,需要继续判断,但是我们可以肯定的是D1肯定不是第四名了,这是我们就把A2,A3,A4,B1,B2,B3,C1,C2 总8匹马进行比赛一次就可以知道前4名了。总共需要11

原文地址:https://www.cnblogs.com/wuyepeng/p/9740963.html