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

评论

42 楼 lipengyu2006 2008-10-31  

哈哈，没看请题目。
我改下以前的答案。
好像应该是10场。
第六场比赛后 都让没次比赛都是最快的5五匹马比赛。
最坏的情况是五匹马全在一个组里
应该最少是10场吧

41 楼 superloafer 2008-10-31  

用插入排序法给一个数组排序，至少要n次比较，就是当数据都是顺序的时候，因为只有比过n次之后你才知道数组已经是排好序的。这时候问你用这个算法至少要比较数据几次，就要回答n；用顺序查找或二分查找法查找一个数据，最差和一般情况的时间复杂度分别为O(n)和O(lgn)，但是如果问至少几次可以找到呢？两者都为一次，因为就是理想情况下一戳就中。
这个题目就算马匹的排序完全理想，也不可能在第六场找出前五名来。当第六场跑第五的马和其他队的第二的马（不包括它自己队的队员）进行第七场比赛跑一次，“理想”情况下他要是跑了第一名把各队的第二都赢了，第七场就能出结果了。这个题目的理想情况就是:在第六场跑出来的五匹马其实就是前五名了，但是除了第一名之外的其他2，3，4，5名都还没有跟其他队剩下的队员比赛，他们无法证明自己就是真正的前五。好，这个时候，最快速的证明方法就是把他们当中实力最弱的第五的马拉出去战斗，和各队（除了它自己的队员外）中最厉害的第二名比一场，立马就可见分晓。他要是赢了的话，就可以给自己和第六场的第二，三，四名正身了。这道题目问的就是“至少”，而要达到这种“至少”本来就是要算法和数据都要对路的情况下才行！

40 楼 kissau 2008-10-30  

superloafer 写道

jemmywang 写道

ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了；


注意题目，是问至少：
答案是7场，下面是我的表述：

前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    u
c    g    l    q    v
d    h    m    r    w
e    i    n    s    x

在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    X
c    g    l    X    X
d    h    X    X    X
e    X    X    X    X

第7场，取第6场的第5名与  第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。

如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。

我觉得你的是对的，我前面也说过这样排除那些不需要比赛的，但是得出的结果是八场。但是这道题目说的是至少，所以如果能找到一种比赛组合可能七场就能确定的话，那应该就是七场了。我没有抓住题目的要旨，即“至少”。就好比一个排序算法一样，拿插入排序为例，如果问插入排序至少要比较多少次才能确定它是有序的，答案是n，当所有的数据本来都是顺序排列的时候；当问至多要比多少才能确定呢，答案是(n-1)n/2次，即所有的数据都是逆序的。

你的第一步是对的，但第二步却有点问题，太过理想化，如果按你的思想，拿某一轮的第五和其他4轮的第一比，如果第五跑第一，那么结果是6场，所以这种算法肯定是错误的。
应该拿每组的第二名比赛
a    e    j    o    t   1（根据第六轮分析）
b    f    k    X    X   2（因为e,b比f快，所以a比f快，所以f后面至多一个，为k）
c    ◎   X    X    X   3（abcef比◎快，所以◎和后面的都淘汰）
d    X    X    X    X   4（同上）
e    X    X    X    X   5（同上）
这样根据比赛排名（每组的第二排名），
可以淘汰如上X
然后拿j，f，c，d，e比赛
无论排名如何都能得出结果(自己分析)
至少7场

39 楼 superloafer 2008-10-30  

jemmywang 写道

ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了；


注意题目，是问至少：
答案是7场，下面是我的表述：

前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    u
c    g    l    q    v
d    h    m    r    w
e    i    n    s    x

在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    X
c    g    l    X    X
d    h    X    X    X
e    X    X    X    X

第7场，取第6场的第5名与  第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。

如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。

我觉得你的是对的，我前面也说过这样排除那些不需要比赛的，但是得出的结果是八场。但是这道题目说的是至少，所以如果能找到一种比赛组合可能七场就能确定的话，那应该就是七场了。我没有抓住题目的要旨，即“至少”。就好比一个排序算法一样，拿插入排序为例，如果问插入排序至少要比较多少次才能确定它是有序的，答案是n，当所有的数据本来都是顺序排列的时候；当问至多要比多少才能确定呢，答案是(n-1)n/2次，即所有的数据都是逆序的。

38 楼 jemmywang 2008-10-30  

ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了；


注意题目，是问至少：
答案是7场，下面是我的表述：

前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    u
c    g    l    q    v
d    h    m    r    w
e    i    n    s    x

在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    X
c    g    l    X    X
d    h    X    X    X
e    X    X    X    X

第7场，取第6场的第5名与  第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。

如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。

37 楼 ak_2005 2008-10-30  

恩 根据我的想法（就是某组第一剔除了，后面补上） 就是10场能决出最快的5匹马（绝对保证正确）
但是就是不知道是不是最小值了

36 楼 armorking 2008-10-30  

先把马分成5组，每组5匹

第1场到第5场分别决出每组第一
第6场对每组的第一名进行比赛
根据结果，假定第六场的5匹马是
a1 > b1 > c1 > d1 > e1
a1所在的组的5匹马是a1 > a2 > a3 > a4 > a5
b1所在的组的5匹马是b1 > b2 > b3 > b4 > b5
c1所在的组的5匹马是c1 > c2 > c3 > c4 > c5
d1所在的组的5匹马是d1 > d2 > d3 > d4 > d5
e1所在的组的5匹马是e1 > e2 > e3 > e4 > e5

显然a1是第1名

第7场，将a1剔除出去，把a2换进来，与b1,c1,d1,e1进行比赛
因为比赛仍然是在每组最快的马之间进行的（a1已经排除在外了）
这场比赛的胜者就是除了a1之外最快的马，即第2名

第8场，先将第7场胜者（第2名）剔除出去
将第7场胜者所在组的下一匹马与参与第7场比赛的剩下4匹马进行比赛
显然比赛仍然是在每组最快的马之间进行的
所以，这场比赛的胜者就是第3名

依次下去，到了第10场比赛就可以决出第5名了

以上说明的是，最少要10场就一定能决出前5名
至于这个10是不是最小值，我无法证明

35 楼 ak_2005 2008-10-30  

这里需要搞清楚一个事 25匹马分成A B C D E 5个组
前面5场决出 每组 第一

第6场让每组第一名决出高下

假设A组的的第一最快 D组第一最慢
但是能保证A组第二（该组第一和第二差距很大）就一定比D组（该组第一和第二差距很小）第二快吗？？？（而第6场差距也很微弱）

更极端的是某个组的5匹马就是跑的最快的那5匹。。。

34 楼 lipengyu2006 2008-10-30  

第二个是不是（N/M+1）*Y-1

33 楼 lipengyu2006 2008-10-30  

我觉得应该是29场

每六场能决定一匹马

最后一次是五场

6+6+6+6+5=29

32 楼 20024804 2008-10-30  

最多9场
前面5场就不说了
第2，3明只需比一场就可以决出，其他的每选出一名都需要比一场

特殊情况下，运气好的话，7场，8场都有可能

31 楼 ganqing1234 2008-10-30  

楼上的当然有问题，我觉得还是10场

30 楼 baseline 2008-10-30  

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名马了.

我怎么觉得是8场，，前面的你说的是对的。
前面5场，所有的马跑一次。得到每场最快的马（第一梯队）和第二快的马（第二梯队）。
第6场，最快的5匹马（第一梯队）跑一次。标记为a,b,c,d,e
第7场，第二快的马(第二梯队）跑一次。得到的其中最快的马，标记为f。f就第二梯队里最快的了。
第8场，不用a在参加了，因为a就是最快的马了。让b,c,d,e,f跑一次，淘汰最后的一名。然后把a在加到里面，得到的就是最快的了。

有没问题？

29 楼 ThinkInJava 2008-10-30  

没什么说的了，就是10场了，上面已经有人说过了，是正确的了！

28 楼 heroicq 2008-10-30  

既然都很稳定，拿个秒表计算，看时间，只要比五场就知道结果了！！
哈哈。。。大家不要扔砖头。。。

27 楼 superloafer 2008-10-29  

思考了一下这个问题，发现一个规律就是：从第六场决出每队最快的马之后的每一场比赛中，跑得越前的马都给它原来所在队的队员留下了更广阔的空间，而同时也让其他的某些队员无缘下一轮比赛。比如说第六场，甲1跑了第一，那么给甲2，甲3，甲4，甲5留下了广阔的发展空间，它们都有可能有能力得的2，3，4，5名，他们四个当中至少要有一个上过场，否则就算接下来比了N场，他们没上场都不能定音。所以最快决出前五名的马的规则就是要让每场跑第一名的马所属的那队其他马先上。它在比赛中所获的名次，决定其后面兄弟的命运。比如甲2，甲3在第七场分别跑了第四第五，甲队是不用再比赛了，甲2，甲3跑的成绩好一点，那么给甲4，甲5留下了余地，也淘汰了一些其他队的一些队员。

26 楼 superloafer 2008-10-29  

这个答案我早已经承认错误了啊，呵呵！看来目前离google的距离还挺远，平时要多看看这类题目，多多锻炼算法和思维。

25 楼 ailu5949 2008-10-29  

superloafer 写道

M6正好跑了第一名，第七场就能出结果了，前五名就是在第六场比赛的五匹马；

我觉得这样不对～。
如果是以下情况怎么办？（数字代表马的速度）
第一场：25 9 8 6 5
第二场：17 12 13 7 4
第三场：24 14 15 16 22
第四场：23 18 19 20 21
第五场：11 10 3 2 1

这样最快的是 21 22 23 24 25  可是按LZ所说的  那就是 23 24 25 11 17

24 楼 xingqiliudehuanghun 2008-10-29  

感觉最少需要6+1+4场比赛，前5场找出每组中的最快的，第六场找出选拔出来的最慢的，剩下的四场和余下的四对比证明自己最快

23 楼 superloafer 2008-10-29  

第六场： 甲1 乙1 丙1 丁1 戊1  每队队员分别称为甲1，甲2，。。。乙1，乙2.。。。丙1，丙2。。。。。 甲1为No1选出
甲2-甲5 4名队员：可能争夺的名次：2 3，4，5，
乙2-乙4 3名队员：可能争夺的名次：  3，4，5，
丙2-丙3 2名队员：可能争夺的名次：     4，5，
丁2：   1名队员：可能争夺的名次：        5，
戊：          其他四名被淘汰；

除甲1（已选出），加上乙1，丙1，丁1，戊1，共剩下14匹马仍需比赛

第七场： 乙1 甲2（争第二名，因为只有甲2有实力和乙1抗衡） 丙1 甲3 乙2（争第三名）
若比赛结果为：
甲2 第二，甲3第三（也就是第七场比赛的第一第二名，是整体第二第三名）
那么乙3，乙4，丁1，丁2，戊1被淘汰（被甲2，甲3挤掉）
        甲队仍需比赛队员：：甲4，甲5，
乙队仍需比赛队员：  乙1，乙2，
        丙队人需比赛队员：  丙1        
        共5名队员仍需参加比赛
因为只剩下5名需要再参加比赛的马了，所以最多只要再赛第八场就可出结果了。取第八场的前两名，再加上前面已赛出来的甲1，甲2，甲3，便可选出整体的前五名。

还有其他情况，不过场次应该都要更多或相等的吧。