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

评论

62 楼 bcccs 2008-11-04  

巫师已经给出通解的ref了。真要研究算法，研究一下m匹马，n个跑道，前k名的时间复杂度最低的算法，还有点意思。

61 楼 superloafer 2008-11-04  

几天没来这题还在讨论啊！我想问一下，假如在面试的时候，我们是该答7轮，还是10轮呢，还是两者都要答呢？题目中的“至少”到底是什么意思啊？

60 楼 moses3017 2008-11-03  

最好情况下7轮，最坏情况下10轮

59 楼 xuyoumi 2008-11-03  

一个a[5][5]的矩阵
a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5

前六场都没有争议的。
但可以得出：
   a1,b1,c1,d1,e1每一匹马都比它们右下方的马快。
   每横行都是左边的比又边快。
   a1 是第一名，入围了。a1出列。

现在还有：
   a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5

由于b1大于它左下方的。a2大于它右边的，所在第二名就在了b1和a2中。
（其实我觉得离空位最近的最有可能。）
所在第七场我们把 b1 , c1 , b2 ,a2 ,a3 拿来比。
（其实第一名肯定是在b1,a2中的）
如果a2比b1快。a2移到a1的位置，a2入围。
    这种情况下，
                a3 a4 a5
        b1 b2 b3 b4 b5
        c1 c2 c3 c4 c5
        d1 d2 d3 d4 d5
        e1 e2 e3 e4 e5
      我们可以知道 其它四道b1,c1,b2,a3中，b1大于c1,b2.所以第三名应在b1与a3中。
这一轮我们决出了两名。

第八场，在第七场的基础上。同理可得两名。五名就出来啦。
（每一匹马快于右下方的马）
（每次拿最近左上角的马比。）

58 楼 xuyoumi 2008-11-03  

至少 8 场

57 楼 nciky1984 2008-11-03  

以下是我的思路- -

首先前6次比赛按照楼主的思路..

然后画出结果表格。如附件1的图1，表格里的数字代表这批马可能跑到的最好排名

根据前6场的比赛结果我们可以很容易得到以下3条结果：

从横向方向来看：右边那匹马的可能的最好成绩是左边一匹最好成绩+1，比如A2可能的最好成绩是第2，则A3的可能最好成绩是第3

从纵向方向上来看：在第1列上，下面那匹马的最好成绩是是上面那匹马的最好成绩+1，比如B1可能的最好成绩是第2，则C1可能的最好成绩是第3

表格中数字唯一：即代表这批马的排名...比如A1是第一。为了方便起见，标明为绿色

下面是第7轮的比赛算法..
选择没有确定排名的，数字最小的5匹马进行比赛，如附件1中图1的红色部分标明的5匹马..把排名填写在表中。因为第一名已经确认，所以从第2名开始排列

假设排名结果如附件1图2这样的结果（紫色部分）。

根据前面得到的3个条件，更新表格中马匹的最好成绩...见附件1图3。

很显然，最好成绩在第6名以后的可以直接淘汰..

然后重复以上循环即可得出跑得最快的5匹马...

最少需要8轮，即附件1所示那种情况。

以上算法可以扩展到有N匹马，M个赛道中...

但是题目问的是 至少 需要多少场比赛...也就是说运气最好的情况下可以确认前5的比赛场数...

所以答案得靠...凑

首先每匹马都得至少进行一场比赛，所以前5场比赛没有悬念...

关键在于第6场...将A5和B1，C1，D1，E1拉一起比...
如果运气够好，A5第一胜出...
排名就是A1，A2，A3，A4，A5。
最少需要 6场 比赛就能够确定名次..

56 楼 zghen 2008-11-03  

最多10轮，最少7轮。没有必要再讨论了，答案很明确。

55 楼 tomqyp 2008-11-02  

最多要十轮可以比出前5名
前六轮同楼主
第七轮时，第一名已经找到了，也就是说要找到第二名,这只只用B1和A2\A3\A4\A5比就可以得出第2名
以此类推只要找出其后的几名既可

54 楼 blurm 2008-11-02  

stormspire 写道

我也并不知道标准答案，下面是我的思路:
第6轮完毕是
A组 A1,A2,A3,A4,A5
B组 B1,B2,B3,B4,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--
假设 A1>B1>C1>D1>E1

第二名没有什么悬念，肯定是A2,B1中的一个
第三名也没有悬念，是A2,A3,B1,B2,C1中的一个

所以拿A2,B1,A3,B2,C1 比一轮 （第7轮），那么可以得出第2、3名，并且可以淘汰第5名，以及第5名所在的其余成员
下面的就麻烦了。

1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以
2. 如果A2,B1是前两名，再比第8轮也可以得出结果。我就不仔细分析了。
3. 最复杂的情况就是B1和C1是前两名，
   3.1 如果A3是最后一名，剩下
A组 A1,A2,--,--,--
B组 B1,B2,B3,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  这里就有A2,B2,B3,C2,C3,D1,D2,E1 8匹马来竞争最后的2个名额. A2,B2比过，所以
第4名可以在 A2,B2中的快者，然后加上C2,D1中比出来，假设我第8轮只用3匹马比，可以得出第4，而且可以淘汰第3名以及比第3名慢的马。所以第8轮可以至少淘汰2匹，加上选出来的第4，那么第9轮只剩下5匹马了，可以得出结果。

  3.2 如果B2是最后一名，剩下
A组 A1,A2,A3,--,--
B组 B1,--,--,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  可以发现这个图比上面的还简单，所以不会比3.1多

综上，觉得至少应该比9轮

关于第七轮的分析:
1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以

如何能够确定B3,B4就在前五名开外呢?

53 楼 Julien 2008-11-01  

五场过后，每一组的第一名进行赛跑，如果赢了则将其从这一组抽走，再以剩下的第一名继续跑，比如说A1第一名抽走了，A2,B1,C1,D1,E1继续跑。不要说B1,C1,D1,E1在之前的A1,B1,C1,D1,E1那一轮已经跑过了，这一组再跑是浪费，因为你不知道A2在B1,C1,D1,E1之间的哪个位置，所以必须让A2和他们全部跑一次才能决定。所以每一次都是有必要的，最好的情况下会出现A2直接比E1慢的情况，直接跑两次就决定了前五名，但是最糟糕的情况肯定要跑满10次

52 楼 chubing07 2008-11-01  

前5场确定每匹马在本队中的顺序，
然后每场比赛确定一匹马，然后淘汰几匹
到第9场的时候，只剩下5匹马比赛，结果就出来了。right？

51 楼 luzl 2008-11-01  

第一场 A1,A2,A3,A4,A5 第一场第一名 AX(假设是A1)
第二场 B1,B2,B3,B4,B5 第二场第一名 BX(假设是B1)
第三场 C1,C2,C3,C4,C5 第三场第一名 CX(假设是C1)
第四场 D1,D2,D3,D4,D5 第四场第一名 DX(假设是D1)
第五场 E1,E2,E3,E4,E5 第五场第一名 EX(假设是E1)

AX,BX,CX,DX,EX  得出第一名 XX1 并且排序(因为是在一起比所以肯定能得到这个顺序)，假设 AX>BX>CX>DX>EX ，XX1即是AX,因为XX1间接的跟每组的比过了，比如XX1大于BX说明比B1，B2，B3，B4，B5都快

BX,A2,A3,A4,A5  得出第二名 XX2 

CX,B2,B3,B4,B5  得出第三名 XX3

DX,C2,C3,C4,C5  得出第四名 XX4

EX,D2,D3,D4,D5  得出第五名 XX5

这是10次的比法，什么情况是比的最小的呢？

50 楼 blurm 2008-10-31  

不错，正确答案出来了

49 楼 stormspire 2008-10-31  

LS的赞一个，很清晰

48 楼 armorking 2008-10-31  

下图是对ls的做法的补充说明

该图表示的是第7场比赛(在A2,B1,A3,B2,C1之间进行的比赛)之后的结果

其中
“○”表示已经确定是前5名之内的马
“-”表示在第6场比赛后淘汰（不可能进前5）的马
“×”表示第7场比赛之后根据结果淘汰的马
淘汰的依据是反证法：假定该马能够进入前5名，那么会有多于5匹马进入前五名

黄色底色的是参加第7场比赛的马

黄色底色的“○”，“×”以外的马与蓝色底色的马进行第8场比赛
第八场比赛的第一是第4名

第7场比赛前两名是A2,A3的情况下
第八场比赛的第二就是第5名

之外的情况下，第八场比赛的第二与绿色底色的马进行第9场就可以得到第5名

47 楼 stormspire 2008-10-31  

我也并不知道标准答案，下面是我的思路:
第6轮完毕是
A组 A1,A2,A3,A4,A5
B组 B1,B2,B3,B4,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--
假设 A1>B1>C1>D1>E1

第二名没有什么悬念，肯定是A2,B1中的一个
第三名也没有悬念，是A2,A3,B1,B2,C1中的一个

所以拿A2,B1,A3,B2,C1 比一轮 （第7轮），那么可以得出第2、3名，并且可以淘汰第5名，以及第5名所在的其余成员
下面的就麻烦了。

1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以
2. 如果A2,B1是前两名，再比第8轮也可以得出结果。我就不仔细分析了。
3. 最复杂的情况就是B1和C1是前两名，
   3.1 如果A3是最后一名，剩下
A组 A1,A2,--,--,--
B组 B1,B2,B3,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  这里就有A2,B2,B3,C2,C3,D1,D2,E1 8匹马来竞争最后的2个名额. A2,B2比过，所以
第4名可以在 A2,B2中的快者，然后加上C2,D1中比出来，假设我第8轮只用3匹马比，可以得出第4，而且可以淘汰第3名以及比第3名慢的马。所以第8轮可以至少淘汰2匹，加上选出来的第4，那么第9轮只剩下5匹马了，可以得出结果。

  3.2 如果B2是最后一名，剩下
A组 A1,A2,A3,--,--
B组 B1,--,--,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  可以发现这个图比上面的还简单，所以不会比3.1多

综上，觉得至少应该比9轮

46 楼 stormspire 2008-10-31  

kissau 写道

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场

第7轮不一定能得出结果。
首先，LS的e在两个队伍里，假设这个是LS的假设:
a    y    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（同上）
我把 A组的e改成y了。

如果c跑得最快，d跑得第二快，这个时候 @，e，y，b都有可能是第4、5名。

45 楼 stormspire 2008-10-31  

貌似很多人都误解了‘至少’
至少 意思就是在任何情况下，必须比这么多场次才可以得出最快的5匹马，所以要考虑最差情况

44 楼 weiruan85 2008-10-31  

同意 lipengyu2006  我也认为是10次
前5次得到前5名，然后让这5名比，第一名 为最快的，然后用第一名所在的组的第二名和其余刚才4个比 ，依次类推 至少需要10次

43 楼 lipengyu2006 2008-10-31  

扩展之后的话 如果N/M能整除的话
是不是就是N/M+Y场呢
呵呵