面试题：赛马问题
一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问，最少得比多少场才能知道跑得最快的5匹马？（不能使用撞大运的算法）
很明显这是一个算法题，网上有很多贴子在讨论这个问题，不过都没有给出一个明确的答案。我想了想，想到下面的一个算法：
1）分成5组A，B，C，D，E，比五场。然后根据每场结果分别给这五组内的五匹马排序（从快到慢）。
2）每组的头名再赛一场，取走第一名，然后该组第二名顶上。
3）重复第二步，直到选出前5名。
这个算法是比较笨的算法，总计需要赛10次，这个算法应该是万无一失的。现在的问题的就，如何优化这个算法，想了想，的确是有优化的空间的。也就是说，是可以少于10次的。
想了一想，上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”，总是挑一个最优秀的出来，其实，在第6次以后除了挑出最优秀的，我们还可以在每次比赛后淘汰一些速度不行的，淘汰的马匹数自然会比选出的更多，所以，一方面在找，另一方面在淘汰，找出前5名的速度应该会更快。
比如：我们假设比赛完第六场后，我们得到下面的排序：（每组排序是——快马从左到右，各组头名的排序是——快马从上到下）
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5
这样，我们不但知道，A1是25匹马里最快的马，而且我们可以淘汰近一半的马，比如E2，E3，E4，E5就可以全部淘汰了，为什么呢，因为比E2快的马有A1,B1,C1,D1,E1这五匹马，所以，E2后面的马是无法进入前五名了；同理，D3和其后面的也进入不了前5；同理，C4，C5，B5都可以淘汰。
于是，在第六轮后我们可以得知，除了A1外的Top 4必然在下面这些马中：
A组 A2 A3 A4 A5
B组 B1 B2 B3 B4
C组 C1 C2 C3
D组 D1 D2
E组 E1
接下来的过程应该不必我多说了。重复前面的方法，尽可能淘汰无法进前N名的马，于是后面的马就越来越少，你所需要的比赛也会越来越少。
那么，对于这个题，聪明的你知道最少要比赛几场了吗？
举一反三，如果有64匹马，8个赛道呢？不失一般性，如果有N匹马，M个赛道呢？N = M*M，那么公式是什么呢？
期待你的答案！
(14 人打了分，平均分： 4.57 )
Loading ...
43楼比较每组第二名，很有想法，受教了。。
最一般的答案就是M+2
首先M组，每组M个赛马，每组分出前三名
然后每组第一名进行比较，假设前三名分别是A，B，C
A是名副其实的第一
之后要把可能为二三名的马选出，进行一场比赛
1.选出A组的第二名，第三名，因为他们有可能会比B组C组的第一快
2.选出B组的第一名，第三名，因为B组第一名还不能确定在总共的M*M匹马中是第二还是第三，第三名仅次于B组第一名，也就是说它还可能成为第三
3.选出C组的第一名，它需要与以上的马匹确定第三的位置
此时选出的5匹进行最后的比赛就可以确定最终的第二三名
3.选出C组的
第六场取每组第二比，如设第六场顺序为A2 > B2 > C2 > D2 > E2，
其结果，B3也可以淘汰，是吧，因为已有5匹比它快（A1/A2/A3/B1/B2）…………
不好意思，错了，A3不一定…………
分5组、
a1-a5\b1-b5\c1-c5\d1-d5\e1-e5,（5轮）用各组第一决出最快的1名（6轮），用最快一组的第二与各组第一名比选出最快的一名（7轮），以此类推，用10轮就可以找到最快的
分五组是没问题，但从前或者从后或者第1/2/3/4/5的“撞大运“选法总是感觉不对……瞬间的念头是：二分法……
我认为,第六轮后我们可以得知
A组 A2 A3 A4 A5
B组 B1 B2 B3 B4
C组 C1 C2 C3
D组 D1 D2
E组 E1
此时选第二名只会从A2与B1之间单选,如果A2是第二名,则第三名只会从A3与B1之间单选,反之,第三名会从A2,B2,C1选,所以第七轮A2 A3 B1 B2 C1比赛可以选出第二名和第三名.
………