文档介绍：赛马问题据说,这是Google的面试题。面试题目如下:一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问,最少得比多少场才能知道跑得最快的5匹马?(不能使用撞大运的算法)很明显这是一个算法题,网上有很多贴子在讨论这个问题,不过都没有给出一个明确的答案。我想了想,想到下面的一个算法:1)分成5组A,B,C,D,E,比五场。然后根据每场结果分别给这五组内的五匹马排序(从快到慢)。2)每组的头名再赛一场,取走第一名,然后该组第二名顶上。3)重复第二步,直到选出前5名。这个算法是比较笨的算法,总计需要赛10次,这个算法应该是万无一失的。现在的问题的就,如何优化这个算法,想了想,的确是有优化的空间的。也就是说,是可以少于10次的。想了一想,上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”,总是挑一个最优秀的出来,其实,在第6次以后除了挑出最优秀的,我们还可以在每次比赛后淘汰一些速度不行的,淘汰的马匹数自然会比选出的更多,所以,一方面在找,另一方面在淘汰,找出前5名的速度应该会更快。比如:我们假设比赛完第六场后,我们得到下面的排序:(每组排序是——快马从左到右,各组头名的排序是——快马从上到下)A组A1A2A3A4A5B组B1B2B3B4B5C组C1C2C3C4C5D组D1D2D3D4D5E组E1E2E3E4E5这样,我们不但知道,A1是25匹马里最快的马,而且我们可以淘汰近一半的马,比如E2,E3,E4,E5就可以全部淘汰了,为什么呢,因为比E2快的马有A1,B1,C1,D1,E1这五匹马,所以,E2后面的马是无法进入前五名了;同理,D3和其后面的也进入不了前5;同理,C4,C5,B5都可以淘汰。于是,在第六轮后我们可以得知,除了A1外的Top4必然在下面这些马中:A组:A2A3A4A5B组:B1B2B3B4C组:C1C2C3D组:D1D2E组:E1接下来的过程应该不必我多说了。重复前面的方法,尽可能淘汰无法进前N名的马,于是后面的马就越来越少,你所需要的比赛也会越来越少。那么,对于这个题,聪明的你知道最少要比赛几场了吗?举一反三,如果有64匹马,8个赛道呢?不失一般性,如果有N匹马,M个赛道呢?N=M*M,那么公式是什么呢?期待你的答案!