面试题：赛马问题

据说，这是Google的面试题。面试题目如下：

一共有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，那么公式是什么呢？

期待你的答案！

（转载本站文章请注明作者和出处酷壳 – CoolShell ，请勿用于任何商业用途）