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

评论

2 楼 Elminster 2008-10-22  

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

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

1 楼 stormspire 2008-10-21  

感觉推而广之这个没解。