面试题:赛马问题

面试题:赛马问题

据说,这是Google的面试题。面试题目如下:

Question一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问,最少得比多少场才能知道跑得最快的5匹马?(不能使用撞大运的算法

很明显这是一个算法题,网上有很多贴子在讨论这个问题,不过都没有给出一个明确的答案。我想了想,想到下面的一个算法:

1)分成5组A,B,C,D,E,比五场。然后根据每场结果分别给这五组内的五匹马排序(从快到慢)。
2)每组的头名再赛一场,取走第一名,然后该组第二名顶上。
3)重复第二步,直到选出前5名。

这个算法是比较笨的算法,总计需要赛10次,这个算法应该是万无一失的。现在的问题的就,如何优化这个算法,想了想,的确是有优化的空间的。也就是说,是可以少于10次的。

想了一想,上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”,总是挑一个最优秀的出来,其实,在第6次以后除了挑出最优秀的,我们还可以在每次比赛后淘汰一些速度不行的,淘汰的马匹数自然会比选出的更多,所以,一方面在找,另一方面在淘汰,找出前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

这样,我们不但知道,A1是25匹马里最快的马,而且我们可以淘汰近一半的马,比如E2,E3,E4,E5就可以全部淘汰了,为什么呢,因为比E2快的马有A1,B1,C1,D1,E1这五匹马,所以,E2后面的马是无法进入前五名了;同理,D3和其后面的也进入不了前5;同理,C4,C5,B5都可以淘汰。

于是,在第六轮后我们可以得知,除了A1外的Top 4必然在下面这些马中:

A组  A2 A3 A4 A5
B组 B1 B2 B3 B4 
C组 C1 C2 C3 
D组 D1 D2 
E组 E1

接下来的过程应该不必我多说了。重复前面的方法,尽可能淘汰无法进前N名的马,于是后面的马就越来越少,你所需要的比赛也会越来越少。

那么,对于这个题,聪明的你知道最少要比赛几场了吗?

举一反三,如果有64匹马,8个赛道呢?不失一般性,如果有N匹马,M个赛道呢?N = M*M,那么公式是什么呢?

期待你的答案!

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 3.91 )
Loading...

面试题:赛马问题》的相关评论

  1. 据题意可知,钟表这玩意儿也是不能使用的
    所以,你只能知道分在同一组的马之间谁快,谁慢
    但是却不可能比较各组之间的谁快谁慢吧

  2. 理想的情况下,应该是M+1+1场就够了。
    假设为一个M*M的矩阵,一组一列:
    1、各列赛一场,得到各列从上至下高到低的排序;
    2、第一行赛一场,得到从左至右高到低的排序;
    A1 B1 C1 D1 …N1
    A2 B2 C2 D2 …N2
    A3 B3 C3 D3 …N3
    . . . . ….
    . . . . ….
    . . . . ….
    An Bn Cn Dn …Nn
    最理想的情况是,淘汰尽量多,观察发现,A1是整个矩阵最快的,B1是从B1~N1矩阵中最快的,所以假如An大于B2即可结束比赛,即An与B2单独赛一场验证An大于B2。
    所以,M+1+1场。

  3. @benx203
    最最理想情况是随机选的M匹马是所有马中最快的,他们之间只需比赛一次,其它的马不用比了,所以不能按理想情况…

  4. 我觉得不失一般性的话,应该是10次比赛吧。最基本的比较就是前面6次,然后排除掉下半部分后,E1,D2,C3,B4,A5就是一个级别的了,一场比赛可以选出一个最快的;再和D1,C2,B3,A4合起来比赛,选出前两名,继续和对角线上的比较,依次比赛完毕总共10次。也就是2M次

  5. 楼主验证过你的想法吗?经过验证还是需要10次,选出5个最快的和选出20个最慢的是等效果的。

  6. 大家都太拘泥于题目里说的算法了,如果在赛场上加个秒表的话总共只需要跑五场就可以选出最快的五匹马儿,Google要的不只是算法一流的程序员吧?呵呵

  7. 显然只能是个区间,因为至少可以假设最快的马都在同一组里面,回头慢慢研究一下

  8. 1)分成5组A,B,C,D,E,比五场。然后根据每场结果分别给这五组内的五匹马排序(从快到慢)。
    2)每组的第二名再赛一场,并根据结果对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
    显然:B4 B5 C2 C3 C4 C5 D2 D3 D4 D5 E2 E3 E4 E5 可以淘汰 A1肯定是前五
    6场比赛以后,结果如下:
    A组 A2 A3 A4 A5
    B组 B1 B2 B3
    C组 C1
    D组 D1
    E组 E1
    3)A3 B2 C1 D1 E1进行第七场比赛
    4)根据结果再举行一场比赛(第8场)就得出前5名

  9. 痛苦思考了一早上都没有结果,对于文章中所说的方法,我想第6次比较之前没有建立垂直链,在第6次比较之后即出现了垂直关系,而且看起来并不能简单地用一句不必多说了就完事,可否有大侠继续说下去,给出一个可推导的公式?
    To phidoit:
    这个命题好像是还需要知道前5名之间的排序,所以你说的这个算法好像还差一步

  10. 还有,文章中所说的方法,第7次比较完了以后排除掉2个,就只剩下4组9匹马了,如何抉择啊?貌似不能不必多说了啊?如果是M×M的话路径选择更加多样,如何抉择啊?痛苦ing…

  11. 还有,文章中所说的方法在第7次比较之后,排除掉2个,剩下的是4组9匹马,而不是5组,如何抉择啊?能不能多说一些?是否可以推导?如果是M*M匹马呢?痛苦ing…

  12. 我的想法是:当A1选出来时,让A2,A3,B1,B2,C1进行一场比赛,可以选出前两名直接进入总结果的前五。这五匹马选出两匹可能结果是:
    “A2,A3” + “A2,B1” + “B1,B2” + “B1,C1”
    此时只需要选两匹马了:
    如果是“A2,A3”,则剩下的可以继续的有A4,A5,B1,B2,C1。一次比赛可以搞定。
    如果是“A2,B1”,则剩下的可以继续的有A3,A4,B2,B3,C1,C2,D1。鉴于C1,B2,A3已经比赛过,看排列:
    {*,*,A3,则A3,A4舍弃}剩余马匹<=5
    {B2,A3,C1,则C1,A4舍弃}剩余马匹<=5
    {A3,B2,C1,则C1,B3舍弃}剩余马匹<=5
    仍然可以一次赛完。
    如果是“B1,B2”,则剩下的可以继续的有A2,A3,B3,B4,C1,C2,D1。鉴于C1,A2,A3已经比赛过,看排列:
    {*,*,C1,则C1,D1,C2舍弃}剩余马匹<=5
    {A2,C1,A3,则D1,C2舍弃}剩余马匹<=5
    {C1,A2,A3,则A3,舍弃}剩余马匹 = 6
    两次比赛可以搞定。
    如果是“B1,C1”,则剩下的可以继续的有A2,A3,B2,B3,C2,C3,D1,D2,E1。鉴于B2,A2,A3已经比赛过,看排列:
    {*,*,B2,则B2,B3舍弃}剩余马匹 = 7
    {A2,B2,A3,则A3,B3舍弃}剩余马匹=7
    {B2,A2,A3,则A3,舍弃}剩余马匹 = 8
    两次比赛可以搞定。

    所以我的结论是6+1+2九次保证选出前五匹马

  13. 我使用排除方法,在最差情况还是需要9次…排除方法到了最后要考虑的情况蛮多,因为要保证每个组马名次上的有序,所以每个组马的数目会参差不齐,数据量越大,最差情况的判断上越发困难,感觉上是不是有个通用的方法可以应对M*M的情况,期待…

  14. 如果M=5的话,可以确定需要9次,但随着M的变大,需要考虑的情况就多起来了,因为每次比赛后如果淘汰不符条件的马后,出现空赛道的情况也多起来,那么,利用空赛道肯定能更快得出结果,但如何利用是个问题。。或者还有更好的实现方法?
    我写了个实现计算的例子,但还是没能找出通用的方法。。。看来算法方面还是不行。。
    http://blog.csdn.net/leon_7mx/archive/2010/01/14/5188769.aspx

  15. A组 A2 A3 A4 A5
    B组 B1 B2 B3 B4
    C组 C1 C2 C3
    D组 D1 D2
    E组 E1

    现在是第六次
    ——————-
    然后 A3 B2 C2 D2 E1 比赛 最快的一个 第七次

    A组 A2 XX A4 A5
    B组 B1 XX B3 B4
    C组 C1 XX C3
    D组 D1 XX
    E组 XX

    所以只要7次就可以知道最快的5马

  16. 先比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
    第六步:
    A3/B3/C3/D3/E3比试。(利用折半查找)
    来个假设吧:
    \\实际结果也是A-E,那么我们就有了3组排列:
    A1 A2 A3 A4 A5;
    A1 A2 A3 A4 B1;
    A1 A2 A3 B1 B2。
    第七步:
    A3 A4 A5 B1 B2比试。结束。

  17. 第六步结果修改:
    A3/B3/C3/D3/E3比试。(利用折半查找)
    可判定最强一队5匹(以A编队;其余顺编)和其余4队头2名为最强5匹所在;排除12匹。

    第七步:
    A1 B1 C1 D1 E1
    *1 *1 *1 *1 A1 排除A2-5 ;A1与各组第2比试,得出前5;总8次。
    *1 *1 *1 A1 X1 排除A3-5 X2;各组第2比试,如A2第一则总赛9次,否则为8次。
    *1 *1 A1 X1 Y1 排除A4-5 Y2;A2 A3与各组第2比试,取前4与X1 Y1 比试,9次。
    *1 A1 X1 Y1 Z1 排除A5 Z2;所剩马匹同A3比试,9次。
    A1 *1 *1 *1 *1 排除弱队第2;所剩马匹同A3比试,9次。

    头痛。

  18. 最少五次也就只需要五次, 要秒錶.
    不要秒錶, 以下情況用以上的算法要幾次:
    A==>600 1200 1201 1202 1203
    B==>601 602 603 604 605
    C==>700 801 901 1001 1101
    D==>800 851 951 990 991
    E==>900 901 902 903 904

  19. 这题目… 完全被误导了哎… 我记得某次笔试做过的原题是求前三名的, 25马前三名7次是可以的
    但是前5名, 7次是不一定能够完全求出的。。 所以是7次或者8次。。

  20. 另外,这个举一反三我认为不具有一般性, 因为8匹马的赛道仍然一次最多决出2名
    一次性决出三名需要2+3+4=9条赛道

    也就是说, 81匹马9条赛道的情况下,9+9/3 = 12次
    而,64匹马8条赛道的情况下,仍然还是 8+8/2 = 12次

    N = M*M 的情况下,需要看 M ≈ [2+3+4….+K](向下取整) 其中K就是一次最多能赛出几匹马
    那么, 公式则就可以描述为 M+ [M/K] 向上取整

    不知道说明白了没有

  21. a1 a2 a3 a4 a5 —– A1
    b1 b2 b3 b4 b5 —–B1
    c1 c2 c3 c4 c5—— C1
    d1 d2 d3 d4 d5 —–D1
    e1 e2 e3 e4 e5—-E1
    A1 B1 C1 D1 E1—–First 一个6局

  22. 确实是一道好题,但是按楼主的算法,如果是最坏情况,即假如跑的快的马全部在一队,不是也要10次吗?大家看看我说的对不对

  23. @yfz
    不对,因为第七次可以拿没有跑过的马进行比较,比如A2,A3,B1,B2,C1,这样跑一次可以确定两个名次,如果A组都是最快的马,那么A2,A3,就是第二和第三名。

  24. E1 D2 C3 B4 A5比一场就能知道了
    A5胜出就是A1~A5,B4胜出就是A1 B1~B4,C3胜出就是A1 B1 C1~C3…以此类推

  25. 5场
    我的思路:
    1. 首先在25匹马中随机挑出5匹比一次,再在剩下的20匹中随机挑5匹比一次,然后将两次比赛的结果合并,选出10匹中的前5名,其余淘汰。
    2. 在余下的15匹中随机挑5匹比一次,再和第1步中的前5名合并,生成新的前5名。
    3. 在余下的10匹中挑5匹比一次,再和步骤2中的前5名合并,生成新的前5名。
    3. 最后余下的5匹比一次,再和步骤3中的前5名合并,生成前5名。

    最后合并出来的前5名即为25匹中的跑得最快的5匹马。

  26. 仔细想了下 我上面的解法是错误的,上面20楼应该是正解,M*M的还没想出通用解法,按照QuXuan的思路 2*2 是3场(A2 B1比较即可) 3*3 4*4就不具备这种解法的条件了…以此类推M=2,5,9,14…第七场分别可以确定1,2,3,4匹前M位的马,但是不同情况就太复杂了…

  27. 个人觉得最少的次数是8,基本5,决出第一名1次,决出2、3名1次,剩下四匹马决4、5名

  28. 好早听说过这个题目,自习思考过方法,尽可能的让每次赛马后淘汰最多的马
    和楼主最初一样,先分成5组,每组5匹,编号ABCDE,组内赛完后,共计五场
    A1 B1 C1 D1 E1
    A2 B2 C2 D2 E2
    A3 B3 C3 D3 E3
    A4 B4 C4 D4 E4
    A5 B5 C5 D5 E5
    第六场若取每组的第一比的话,最终可以淘汰4 + 3 + 2 + 1 = 10 (+ 1选出)
    若取每组的第二比的话,最终可以淘汰4 + 4 + 4 + 2 = 14 (+ 1选出)
    若取每组的第三比的话,最终可以淘汰3 + 3 + 3 + 3 = 12
    … 后面肯定更少
    所以第六场取每组第二比最佳,不妨设第六场顺序为A2 > B2 > C2 > D2 > E2。
    这样第六场后剩余的马有10匹,只需选出前四即可
    B1 C1 D1 E1
    A2 B2
    A3 B3
    A4
    A5
    第七场还是按照上面的原则,尽可能的淘汰最多的马
    选择A3 B2 C1 D1 E1比赛,
    若A3 B2为前两名,那么这四匹马(前五)就找出了,为A2 A3 B1 B2,只用了7场
    若A3为前两名,B2不为前两名,那么就有三匹马(前五)找出了A2 A3 (C1或D1或E1)淘汰B2 B3,最后就只剩五匹马,所以只需要加赛一次,共计8场
    若A3 B2都不为前两名,A3 A4 A5 B2 B3都可以淘汰,最后A2 B1 C1 D1 E1赛一场就可以了。所以只需要8场。

    综合三种情况,最少需要8场

  29. 假设每匹马都跑的很稳定,这个前提下就没有两匹或者三匹马跑的速度一样的吗??

  30. 我的想法第七場與 20 樓同,第七場結束後就可以決定前三名。
    但是 20 樓在第七場的後續展開還不夠完善。
    第七場五匹馬選出兩匹的結果不只下面四種,
    “A2,A3” + “A2,B1” + “B1,B2” + “B1,C1
    還有可能是 “B1, A2” 這種情況

  31. 第七場(A2, A3, B1, B2, C1)的前兩名會是第2,3名,
    因為除了上述五匹之外的馬,都至少輸給三匹馬,因此不會是前三
    這五匹馬在第七場之前都只輸給一或兩匹馬,
    所以比完第七場後可以決定第二名(只輸A1一匹馬)與第三名(只輸A1與第七場第一名)。

    而第七場的第五名肯定不是前五名
    (因為已經輸給了第七場的四匹馬跟 A1, 共五匹馬, 輸給五匹馬就是第六名以後了)
    所以第七場比完後,(A2,A3,B1,B2,C1)中還有兩匹馬有可能在前五

回复 yuxio 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注