探讨GOOGLE面试题赛马问题（纯粹个人思路，有什么不对的请大家指正）

这个是google的一个面试题，觉得挺有意思的，问题是这样的：

一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。

假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。[也许至少会产生误解，换成最少，就是考虑你的算法的最坏情况下]


以上就是这个问题。其实拿起笔来，仔细看看倒是不是很难。  (后来仔细想了想，其实并不简单)

如果推而广之，有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马。

在CSDN上看到另外一个题，http://topic.csdn.net/u/20081017/14/826303de-1871-4e50-89e8-47ed56f49acc.html
实际上就是把N换成256， M换成2， Y换成3

-----
另外有个朋友提出的描述方法浅显易懂，反正25匹马要分5组的，大家在下列统一的马匹归类下讨论比较容易

前5轮应该没有什么争议，就是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

第6轮目前比较统一的做法是让 每个组的第一，即A1,B1,C1,D1, E1比一场，假设 A1>B1>C1>D1>E1 那么这个时候可以淘汰一些马了，淘汰的用--表示，如下:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --

分歧就在第7轮了，我也没想清楚最佳方法，我就不在第一个帖子说了。

  原文作者stormspire说，第6轮目前比较统一的做法是让 每个组的第一，即A1,B1,C1,D1, E1比一场，我的算法是，比出了每组的第一之后，假设是A1,B1,C1,D1, E1，并非直接让它们接着比，而是让每组的第二名进行第六轮的角逐，假设是A2,B2,C2,D2,E2之间比一场，为什么我要这么安排呢？且听在下细细道来：
  这个赛马比赛，最好的情况是在前五轮比出的A1,B1,C1,D1,E1就是最快的五匹马，那么，为了确认它们是最快的，

我们还要保证这五个第一名不仅快于本组成员，而且比其他组的马匹成员（不包括每组第一名），于是，我们让每组的

第二名马进行比较，比出最快的一匹马，假设它是A2，现在，让A2,B1,C1,D1,E1之间比一场。由于

A2>B2>C2>D2>E2，那么毫无疑问，A2是那些余下的马中最快的，如果A2在与B1,C1,D1,E1的比赛中

输了，那么，在加上A1>A2，那么我们就可以肯定A1,B1,C1,D1,E1是最快的五匹马。此时，共比赛了5+1+1=7场



   而整场比赛最糟的情况莫过于五匹最快的马被分配到了一组，假设它们是A1,A2,A3,A4,A5 。

那么我们在前五次得出了每组最快的A1,B1,C1,D1,E1之后，为了确认它们的确是最快的时候，依然采用前述的方法，

即，让每组第二名角逐出最快的和B1,C1,D1,E1比赛，这时我们发现A2比B1,C1,D1,E1都快，于是，淘汰掉这次比赛

的最后一名，假设是E1被淘汰,此时，我们得出了新的临时结果，即最快的是A1,A2,B1,C1,D1，并且A2比倒数第二名

快（如果A2是倒数第二名，那么这是即可确定最快的五匹马是A1,A2,B1,C1,D1，而我们的假设前提是

最快的五匹马均在A组），那么此时，我们有理由怀疑A组中余下的马中可能还有不比B1,C1,D1慢，于是，

我们让余下的A3,A4与B1,C1,D1比一场，结果，A3是第一名、A4第二名，更新了两名最快成

员，假设C1,D1被淘汰，最后，让B1与A5在比一场即可得出最快的五匹马是A1,A2,A3,A4,A5，此时总共

比赛9场。当然，针对这种特殊情况，我们还可以最后大胆让A4,A5与B1,C1,D1比赛而跳过

A3,那么，如此比赛最好的情况就是A4,A5为前两名，即可判断出最优组是A1,A2,A3,A4,A5，共比赛8场，否则，也可

通过A4,A5的名次大致判断出A3的实力，当然实际操作时不可能这么做，这个特殊情况我只是提出来玩玩~~

  总结一下我的算法思路，即为：
1.每组中比出第一名，权且称之为临时最优组。
  2.每组中的第二名角逐，所得出的那匹马就是余下马中最快的，让它与除了它所在组的之外的各组第一名比赛，
    即max_speed{除去各组第一名余下的马匹}与{临时最优组中与max_speed{除去各组第一名余下的马匹}不在同一组的马}比赛  
  3.if( max_speed{除去各组第一名余下的马匹})被淘汰 )
        临时最优组成员即为最优结果;
    else{
         更新临时最优组成员;
         重复类似与步骤2的结果;(随着临时最优组的成员被淘汰，每次能与临时最优组的马数会增加）
         }   
   本来我还想把题目推广，有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马，看看是不是能整

理归纳出一个通解式子，可惜。。。我现在没时间了（靠，机房被病毒入侵，需要临时关闭！），期望我的算法能给你

一些启迪，当你完成出了通解式子式子时，请记得发一份给我，谢谢！当然，我自己在空余时间也会继续研