讨论一个算法，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轮了，我也没想清楚最佳方法，我就不在第一个帖子说了。

感觉推而广之这个没解。

《算法导论》第二版，第九章 Medians and Order Statistics，最后一节。那里介绍了一个算法如何通过分组比较来找出一个数组中第 k 大的元素。稍微变一下就是这个问题。

（另：这个是 Google 面试题？不太像啊）

电面的，电面因人而异吧

算法导论？没看过这个书

确实比较有意思的，感觉这实际上是为了实现并行/分布式排序，如果数据量很大，也可以考虑用MapReduce方法来做实际的实现。

应该是要7场。首先至少每一匹马都要比赛，所以一开始就先比五场；每一场比完后分别将当时那场的马按快慢顺序排好队。然后第六场每对最快的马比。这一场过后，将跑得最慢的那匹马的所在的队伍整队都淘汰掉（无需比了，最快的都跑得比别人慢），同时将第六场跑得最快的那个队的第二名拉出来比(因为只有这个队的马才有可能挤进第二到第五名之间）。第七场会出现几种情况：
1。在第六场才加进来的马在第七场正好跑了第五名，那么结果出来了
2.第二三四名的话，都还要继续比，不一一列举。但可以给个场次最多的，就是跑得最快的马都是同一个队的，要10场比赛才能见分晓。

上面的第二行说话有点纰漏，应该是将第六场跑了第一的马所在的留下继续比，其他的队伍的马都要被淘汰掉！

此匹马万一恰好是总第五名呢？

万一第六场比赛的5匹马，恰好是总第1到第5名呢？所以任何队伍都不能淘汰。

哦，不好意思，是我的思维不够缜密。有可能第六场跑最慢的那匹马就是第五的料，所以第七场应该这样比：将第六场跑得最慢的马（不妨称这匹马为M6）和第六场跑得最快的那匹马所在的队伍的其他四批马比。情况有几种：
M6正好跑了第一名，第七场就能出结果了，前五名就是在第六场比赛的五匹马；
M6跑了第二名，那么它就被淘汰掉了，第七场第一名的马挤进前五，还要进行第八场才能决出胜负；
。。。。。
场数最多的情况应该是：前五名的马都是同一个队的，也即一直都是第一名的马所在的那个队伍。
谢谢billgui的提醒，以后要多练练！