100匹马，4个赛道，找出跑最快的4匹马。

4 years ago

source link: https://zhuanlan.zhihu.com/p/189771676
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

100匹马，4个赛道，找出跑最快的4匹马。

腾讯高级前端工程师

创作声明：内容包含虚构创作

内容中的情节存在虚构加工，仅供参考

其实在网上也有不少该题目的文章，但是可能题目不一样，能找到的题目名为《64匹马，8个赛道，找出跑得最快的4匹马》。该题目出现在腾讯的面试题里面。

最近我也在进行腾讯的面试，也遇到了这一题，虽然网上有答案，但是还是想写一些我的思路，或许不是最好，希望有人可以点评一下。

100匹马，每一只马的跑步速度是恒定的，不会因为多跑几轮就会速度下降，没有提供秒表进行记录。问需要比赛多少轮才能得出最快的4匹马?

第一轮：从100匹马分成25组，每组4只马进行第一轮的比赛，得出每一组第一名的马进行第二轮。第一轮需要比赛25场。

第二轮：我们将第一轮分为ABCDEG...共25组，在第二轮中，取前4组的第一名进行第二轮的第一场比赛。每一场的比赛中的第一名晋级第三轮，第二名会进行第二场，从第一轮晋级的马匹中选取3匹进行下一场比赛，剩下3，4民直接淘汰。

晋级留淘汰

25 - 4 = 21 1 1 2
21 - 3 = 18 1 1 2
18 - 3 = 15 1 1 2
15 - 3 = 12 1 1 2
12 - 3 = 9 1 1 2
9 - 3 = 6 1 1 2
6 - 3 = 3 1 1 2
3 - 3 = 0 1 0 3

第三轮：假设通过第二轮得出来的是ABCDEFGH组的第一名，那么我们将要在第三轮决出4强。

ABCD 第一组
EFGH 第二组

假设第一场AB是第一二名，第二场EF是第一二名，那么将交叉再比赛一次。

从而得出最终四强就是第一第二场的前两名。假设是ABEF这个4个。

第四轮：得出的4强当中，进行一次比赛，在第四轮就能提前锁定第一名，假设我们为第三轮的得出的4强重新编号，ABCD，那么进行比赛

假设胜出的是A，那么ABCD所在的第一轮比赛的组别进入第五轮。还记得第一轮比赛是4匹马为一组，为什么需要这么做呢，因为没有秒数的条件，所以你并不能确定A组第二名是不是一定比B组第一名慢，所以必须进行第五轮，但是为什么只拿这4组呢，因为如果A组第一名已经比H组的第一名快，所以H组后面的所有马都不可能比ABCD组的第一名快，如果B组的第二名比C组的第一名快，那么H组的第一名更加不可能比B组第二名快，所以才将最后得出最快的4个分组的第一名中，将所在的组别放到第五轮进行再一次比赛。

第五轮，因为第四轮得出第一名，假设为A组的第一名。那么剩下的马匹分布如下：