【面试智力题】100匹马中找出最快的4匹

本文最后更新于：2023年12月17日下午

前言

之前腾讯面试的时候，出了一道智力题，跟赛马相关的，大意就是总共100匹马，共有4条赛道，请问最少比赛几次就能选出最快的4匹马，假设比赛不能计时，只能比较快慢。

这不巧了吗，正好最近我在看赛马娘2，对赛马也是略知一二，这题，拿下！

咳咳，不好意思，好像植入了一段广告（doge）。不过残酷的现实是，当时完全没有好的思路，就想着依次选出最快的马，然后被最快的马淘汰的再比较，选出第二快的马，实际写起来的时候思路就乱糟糟的，可能也是因为面试紧张的原因吧。但现在回过神来，冷静思考分析后，感觉还是可以跟大家分享一下我的思路。

解题思路

网上类似的参考文章有：

都提供了不错的思路，然后我也是自己再尝试计算了一下，最后算出来最少需要36轮，可能也不是最准确的，下面就介绍一下我的思路。

首先100匹马，分成25组，比赛25次，比较出每组的1234名。（组号表示为1、2、3 … 25 ， 1-1 表示第1组的第1名）
选出每组的第一名，那么总共有25匹马，分成7组，前6组都是4匹马，最后一组只有一匹马（组号表示为 A、B、C、D、E、F、G，用字母表示，A-1 表示第A组的第1名，G组只有一匹马就是25-1）；前6组比赛6次，又选出每组1234名
A-1、B-1、C-1、D-1 比赛一次，然后拿这一次的第1名和 E-1、F-1、G-1进行比赛，此时就能选出最快的一匹马，至此共比赛了 25+6+2 = 33次
为了方便理解，不妨设上一步比赛中，最快的是A-1（其实选A-1、B-1、C-1、D-1、E-1、F-1都是一样的，可以替换。而如果最快的是G-1 ，会具有特殊性，需要再比较的马的数量更少（因为G-1之前只跟3匹马比赛过），所以要计算最少的比赛次数不能选G-1。
- 进一步假设，不妨认为上一步中两次比赛的排名为 A-1、B-1、C-1、D-1 和 A-1、E-1、F-1、G-1，因为调换顺序也不影响下面的计算
因为A-1是最快的马，而现在要选出第2快的马，那么第2快的马就有可能出现在被A-1淘汰的马中。不妨进一步将设，A组比赛的结果为 1-1 、2-1、3-1、4-1 ，即 A-1 为 1-1，以此类推 B-1为5-1 。那么第2快的马可能的集合为 { 1-2 、2-1/A-2、B-1、E-1 } ，此时只要再比赛1次，就能选出第2快的马。
在上一步的比赛结果中，如果1-2是第一名，那么只要拿第二名和1-3比赛就能选出第3快的马，而如果2-1、B-1、E-1 是第一名，都是再拿出2匹马和第二名比较（例如，选2-1，则要比较 3-1/A-3和2-2；选B-1即 5-1，则要比较 6-1/B-2 和 5-2），所以只要再比赛1次，就能选出第3快的马。
同理，在上一次比赛结果的基础上，最多再选出2匹马和上次比赛的第二名
比赛1次，就能选出第4快的马。
- 例如上次比赛结果为 { 6-1/B-2、5-2、17-1/E-1 } ，那么只要从 { 6-2、7-1/B-3、5-2 } 里再比一次即可。
最终，最少需要的比赛次数为 25+6+2+1+1+1 = 36 次