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

评论

22 楼 blurm 2008-10-29  

1，先赛五场
2，第六场，每场的第一名赛一次，此次的第一名拿出去
3，第七场，第六场第一名在（1）里队伍的第二名顶上来再加上第六场的剩下四名比赛，此次的第一名再拿出去。
4，第七场的第一名在（1）里的下一个名次的马继续顶上来，和剩下的四匹马比赛

这样算下来得赛10场，不知道对不对

我表述的太烂了。。。sigh，自己寒一个

21 楼 superloafer 2008-10-29  

yuyoo4j 写道

是7场;
前面5场,让所有的马跑一次;
标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队
标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队
第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5;
第7场, 让 第6场中跑第1,3,5名的马对应在  first梯队 和 第2,4名在second梯队跑一次
就可以最终确定 前5名马了.

这样好像也不能确定哦。假如有一种情况就是在分组的时候正好把前五名分到一个队里，其实这种情况就好比说，几个班的人比赛，每个班谁最利害是知道了，但是有可能其中一个班的人比其他班里的第一名都要厉害（比如那些特尖班奥赛班之类的，呵呵)！不妨说这队为甲队吧，其他依次为乙丙丁戊。按你这种思路，第六场跑第一的是甲队的第二（实则也是整体第二），而其实真正的第三第四名第五都还在甲队呢，能确定在第七场的时候把前五都选出来么？

20 楼 blurm 2008-10-29  

yuyoo4j 写道

是7场;
前面5场,让所有的马跑一次;
标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队
标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队
第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5;
第7场, 让 第6场中跑第1,3,5名的马对应在  first梯队 和 第2,4名在second梯队跑一次
就可以最终确定 前5名马了.

貌似你是把前五名限制在了每场的第一二名里共10匹马中间
如果第一场比赛的五匹马碰巧就是最快的五匹马呢？

19 楼 yuyoo4j 2008-10-29  

zhangkaitao 写道

我觉得至少是6场,5场完了,万一第一场的第5名跑的比后4场的还快,那不是6场就出来了 呵呵,大家觉得呢

题目中问的是"至少"不是"最少"; 你描述的只是特例;

18 楼 yuyoo4j 2008-10-29  

是7场;
前面5场,让所有的马跑一次;
标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队
标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队
第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5;
第7场, 让 第6场中跑第1,3,5名的马对应在  first梯队 和 第2,4名在second梯队跑一次
就可以最终确定 前5名马了.

17 楼 fabulous 2008-10-29  

记得有人发了一个意思差不多的题，可以参考一下，那个好像是面试ruby开发的吧

16 楼 zhangkaitao 2008-10-29  

我觉得至少是6场,5场完了,万一第一场的第5名跑的比后4场的还快,那不是6场就出来了 呵呵,大家觉得呢

15 楼 lbh087 2008-10-28  

jackyqiang 写道

n/m+y
哈哈

有可能是n/m+y+1,

14 楼 ThinkInJava 2008-10-28  

superloafer,你在上面说，M6正好跑了第七场的第一名结果就出来了，不会吧，其它组也有可能有比M6还要快的呀？应该比下去吧？

13 楼 jackyqiang 2008-10-28  

n/m+y
哈哈

12 楼 apptech 2008-10-28  

必须进行的五场比赛就不说了。从第六场比赛开始吧：在每组的第一名进行第六场的比赛，然后第一名直接晋级，再由第一名所在对的下一名和剩下的四匹马进行比赛，以此类推，五轮比赛后即可得出跑的最快的无匹马。

11 楼 stormspire 2008-10-28  

Elminster 写道

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

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

请教下用这个理论是怎么解的？


我只能通过推理来算，大概是至少比9场吧。

10 楼 stormspire 2008-10-28  

楼上的没有明确回答出至少多少场要比。看不明白至少要多少

9 楼 superloafer 2008-10-28  

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

8 楼 billgui 2008-10-28  

superloafer 写道

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

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

7 楼 billgui 2008-10-28  

superloafer 写道

这一场过后，将跑得最慢的那匹马的所在的队伍整队都淘汰掉（无需比了，最快的都跑得比别人慢）

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

6 楼 superloafer 2008-10-27  

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

5 楼 superloafer 2008-10-27  

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

4 楼 billgui 2008-10-26  

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

3 楼 stormspire 2008-10-22  

Elminster 写道

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

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

电面的，电面因人而异吧

算法导论？没看过这个书