面试题:赛马问题

面试题:赛马问题

据说,这是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微信公众账号可以在手机端搜索文章

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

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.53 )
Loading...

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

  1. 剩下來的問題就是能不能再找三匹馬,來和第七場的第三名、第四名比賽,
    這第八場比賽的前兩名可以決定全部馬匹的第四名第五名

    如果不能只找三匹馬,那就必須再有個第九場
    只是這推導太複雜,很難完全說明
    這邊直接說一下我的結論,

    第七場的第五名有三種可能:A3, B2, C1
    1) 如果七場五名是 C1 的話,CDE 三組都可以排除在前五之外
    可以第八場場就決定出前五名
    (第八場剩下三匹馬的取法,需視第七場第四名所在組而決定)
    2) A3, B2 的話沒辦法,需要第九場

  2. 最一般的答案就是M+2
    首先M组,每组M个赛马,每组分出前三名
    然后每组第一名进行比较,假设前三名分别是A,B,C
    A是名副其实的第一
    之后要把可能为二三名的马选出,进行一场比赛
    1.选出A组的第二名,第三名,因为他们有可能会比B组C组的第一快
    2.选出B组的第一名,第三名,因为B组第一名还不能确定在总共的M*M匹马中是第二还是第三,第三名仅次于B组第一名,也就是说它还可能成为第三
    3.选出C组的第一名,它需要与以上的马匹确定第三的位置
    此时选出的5匹进行最后的比赛就可以确定最终的第二三名
    3.选出C组的

  3. weihao :
    好早听说过这个题目,自习思考过方法,尽可能的让每次赛马后淘汰最多的马
    和楼主最初一样,先分成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场

    第六场取每组第二比,如设第六场顺序为A2 > B2 > C2 > D2 > E2,
    其结果,B3也可以淘汰,是吧,因为已有5匹比它快(A1/A2/A3/B1/B2)…………

  4. 分5组、
    a1-a5\b1-b5\c1-c5\d1-d5\e1-e5,(5轮)用各组第一决出最快的1名(6轮),用最快一组的第二与各组第一名比选出最快的一名(7轮),以此类推,用10轮就可以找到最快的

  5. 分五组是没问题,但从前或者从后或者第1/2/3/4/5的“撞大运“选法总是感觉不对……瞬间的念头是:二分法……

  6. 我认为,第六轮后我们可以得知
    A组 A2 A3 A4 A5
    B组 B1 B2 B3 B4
    C组 C1 C2 C3
    D组 D1 D2
    E组 E1
    此时选第二名只会从A2与B1之间单选,如果A2是第二名,则第三名只会从A3与B1之间单选,反之,第三名会从A2,B2,C1选,所以第七轮A2 A3 B1 B2 C1比赛可以选出第二名和第三名.
    ………

  7. 解题报告:
    定义:
    1.两匹马的速度快慢,称为一个关系,例如A比B快,则称A和B构成一个关系,用表示;
    2.在一个关系中,每个比较对象有贡献,其中慢的向快的马贡献,马匹x具有的贡献称为度,用D(x)表示。如A比B快,则B向A贡献1,此时A的度为1,B的度为0,即D(A)=1, D(B)=2,度数说明了比较慢的马匹有多少匹;
    题目分析:
    求最少比赛场数应考虑每次比赛比会产生最多关系的马匹,由于不能采用撞大运的情况,考虑每次比赛后产生的关系数应为最少
    解题过程:
    前五场采分组比赛,得出以下关系
    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,B1,C1,D1,E1)含有最多度数4,故第六场应比较每组第一名,假设得出关系如下:
    A1 > B1 > C1 > D1 > E1
    得出全局第一名A1
    往后关系和度数如下(冒号后面的是度数)(排除掉不可能进入前五名的):
    A2:3 > A3:2 > A4:1 > A5:0
    B1:9 > B2:2 > B3:1 > B4:0
    C1:5 > C2:1 > C3:0
    D1:2 > D2:0
    E1:0
    由上表,第七场应比较(B1,C1,A2,A3,X)(其中X为度数为2的马匹,这里为D1或者B2)。
    如果X=D1,考虑极端情况,增加最少的度数为以下情况(其他情况等价考虑):
    B1 > C1 > A2 > A3 > D1
    此时增加的总度数为11(其中A2分别向B1、C1贡献4度,D1分别向A2、A3贡献3度,共4×2+3×2=14度),并选出第二、三名:B1和C1;
    如果X=B2,考虑极端情况,增加最少的度数为以下情况(其他情况等价考虑):
    B1 > C1 > A2 > A3 > B2
    此时增加的总度数为15(其中A2分别向B1、C1贡献4度,B2分别向A2、A3、C1贡献3度,共4×2+3×3=17度),并选出第二、三名:B1和C1;
    由上述可知应比较(B1,B2,C1,A2,A3)。
    往后关系如下(极端情况考虑并排除掉不可能进入前五名的):
    A2:3 > A3:2 > B2:1 > B3:0
    C2:1 > C3:0
    D1:2 > D2:0
    E1:0
    由上表,第八场应比较(A2,A3,D1,B2,C2)。
    注意A2 > A3 > B2,考虑极端情况,增加最少的度数为以下情况:
    D1 > C2 > A2 > A3 > B2
    此时增加的总度数为10 (其中A2分别向D1、C2贡献4度,C2向D1贡献2度,共4×2+2=10度),并选出第四名:D1;
    最后第九场比赛(C2,D2,E1)可决出第五名。
    综上所述,至少要赛九场方能保证决出前五名。

  8. 赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。
    5个赛道 就真的只能同时有5匹马一起比赛么?

  9. M匹马中选出前N名来,K条赛道
    无意间看到这题了,想个半个小时,想明白了。
    应该是按照森林合并的思想,分层来。每次只比最上第一个不是一个元素的层,如果最上层不足赛道数K就取下一层的马代替。
    每闪比完需要改变一下树结构,直到出现前N层元素都是一个元素,前N名就出来了。
    我觉得这是最好的答案

    ###################################
    代码简单思想:

    element {
    element parent = ROOT;
    element broutherL = null;
    element broutherR = null;
    element child = null;
    }
    A 先把parent==ROOT && child==null的比,不够赛道时,如果有parent==ROOT但是child!=null的加入比赛,直至只有一个元素的parent(第一名)为null
    这样就形成了初步的树了,也就是说至少第一名出现了
    B 查看最上面的每层只有一个元素的连续的层(1~CNT),如果达到N,恭喜你选出前N来了
    C CNT+1层的马进行比赛,分组时不够K的组取CNT+2层的马加入比赛,比赛后记得调整树,然后转到B,直到找到结果

    在A之前要查看MNK的关系,如负数,M<K岂不是不用比了,直接打印出1就行了……
    树的调整我没考虑,应该能做到吧
    (也或许我写的数据结构不对)

    不知道有没有人写代码实现,发我一份 china_qd@163.com,谢谢

  10. 顺便说一下
    parent 是速度比自己快的,child是速度比自己慢的,brotherL与brotherR是不知道是否快慢的
    构造初始数据可以parent都为null,用brotherLR设置好,构造出初始数据来

  11. 最快是7场, 第七场比较 A2,B2,C2,D2,E1。 如果D2或E1第一,则直接得出前5。

    逻辑理解很简单,但头痛在于如何抽象成算法,再想想~

  12. 我认为1次比赛就可以得出结果。可以把5个赛道分别分成5段距离,假设每段距离100米,这样就可以让25匹马站在5个赛道的25个起始点上同时起跑,看最先跑完各自100米的5匹马就是你要的答案了。

  13. 受#10启发,发现可以这样:
    在5场后得到五组
    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
    如果以上面这样的阵型去跑呢?没有错,就是让它们陆续出发,第一名在前面跑,速度各不相同,肯定不会撞车,但是并列出发的就能发现不同速度了。而经过一定时间后,最快的马用看的也知道了。

  14. sorry,赛马场的硬件设备被我忽略了……如果不够大而且是圆形的话,可能在找出之前,同一列的撞了

  15. 题目假设每匹马都跑的很稳定,那我觉得完全可以值跑5场,统计5场的结果,选出最快的前5名就行了啊!

  16. 好题啊,挺锻炼思维的。
    不要怕麻烦,穷举+淘汰,画图把大小顺序排列成森林的形状,更容易做出来。
    评论中的某些想法也比较精彩。

  17. 感觉25匹马,只要让每一匹马与其他24匹马,都跑一次就好了。那就是6次。不过这是针对一匹马而言,不知道可否找到这样的状态对于所有马都成立。

  18. M+1场过后,只剩下
    A1 A2 A3 A4 A5
    B1 B2 B3 B4
    C1 C2 C3
    D1 D2
    E1,
    第M+2场,取A2,A3,B1,B2,C1赛一场(赛道有多?没关系的),无论什么结果都能决出2,3名,
    第M+3场,不妨设上一场A3最慢,则取B2,B3,C1,C2,D1赛一场,即可决出4,5名。

  19. cook_li :受#10启发,发现可以这样:在5场后得到五组A1 B1 C1 D1 E1A2 B2 C2 D2 E2A3 B3 C3 D3 E3A4 B4 C4 D4 E4A5 B5 C5 D5 E5如果以上面这样的阵型去跑呢?没有错,就是让它们陆续出发,第一名在前面跑,速度各不相同,肯定不会撞车,但是并列出发的就能发现不同速度了。而经过一定时间后,最快的马用看的也知道了。

    这个想法神了!果然NB啊……

  20. @cook_li
    没事,跑个百米直线就行了,每匹马出发距离差1米,到终点的距离也差一米,设置5条出发线和到达线。。。。

  21. 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

    假如前五场,如上所示。

    第六场, A2 B2 C2 D2 E2
    假如结果是:A2 > B2 > C2 > D2 > E2

    此时A1 A2 B1 B2 C1一定比C2快。

    即,C2没必要再去竞争前五了。

    现在

    然后,第七场让A3 B3 C1 D1 E1跑
    如果 C1 D1 E1中有一个获得第一名,不妨设为D1,则第八场安排剩下的A1 B1 D1 A2 B2比赛即可。
    但是,我们要求最大比赛数,此时不妨设B3在第七场获得第一名,

    现在简单了,第八场安排,A1 A2 B3~5,比赛。取前三名。
    第九场决定最后名次。

  22. 具体分析很多人都做出来了,我也不知道对不对,小的想了一个算法,不知对不对也请各位大神指正:

    这个问题里的比赛结果像是什么呢,个人觉得是一个偏序集,偏序集的问题一般都是用有向图来解决的。
    有向图顶点和边我是这样设计的:
    struct Node
    {
    Num 最好顺位 //预期最好的顺位(排名当然是越高越好),简称顺位
    List 直接后继列表 //就想里面写的那样就是直接后继列表,注意是指针类列表,用来代指边,可以知道边是排名高指向排名低的
    T 对象 //对象本身,马之类的,用来比较
    };

    下面说初始化:
    T当然是填上比较的对象
    Num全部置为1,说明比较还没开始谁都可以是第一
    List全置为空,表示所有对象的大小没有指定,换句话说就是这个图的边还没有

    第一个问题是比较元素的选择,这个问题里大概不可能出现Num值大的结点个数少于Num值小的情况(这作为一个我这个有向图的属性,下面的维护这个也是重点)。选择元素问题很简单使用一个定长的数组(长度就同时可以比较几个对象)就可以完成,选取Num值最小的那几个就可以了,(你说怎么选那几个最小的几个,我是用队列,NodeA出列那么NodeA.List内的依次入列,第一次的话就随便瞎搞都搞的出来啦)(还有为了避免一直把前面排好的一直入列的情况,就使用一个值来记录现在要找第几名,这样就可以设置一个Num值为0的Node来处理出初始的无无序情况,其List为所有Node)

    第二个问题是指定这几个Node的关系:
    我拿到这几个Node之后第一件事不是去比较,而是把他们之间的关系消除
    例如我拿到的是Node1~3
    我消去他们之间关系的是做法就是把所有Node.List中的所有Node1, Node2, Node3删除
    消除关系之后我再比较再指定关系,
    例如我比较完了之后结果是
    Node1.Num<Node3.Num<Node2.Num
    那么我就在Node1.List中插入Node3
    Node3.List中插入Node1
    然后我发现这个图的Num是乱的,我对这个图里面的Num要进行维护
    这个图里面一定会有Node的Num值是1
    就从这个元素入手,上面填1,List中的Node的Num填2,在拿出那些我填2的Node的List中的全填上3,如此往复到了那个Num等于要求的直接把List置为空不再进行下去,相当于说把太慢的马淘汰掉
    你如果看懂了上面的方法的话,你可能会有疑问:
    维护的时候一个Node会不会访问两次导致出错,我的回答是不会的,如果有需要的话我应该可以给出严谨的数学证明。

    我的文字非常的羞涩难懂,各位看官就凑合着看,这也是好几年前的老物,也不知会有谁还来看,说实在的我自己看自己写的东西我也会晕的Zzzzz

  23. @weihao
    43楼分析很多,结果是对的,但是分析的细节不对。
    其中讨论:

    若A3为前两名,B2不为前两名,那么就有三匹马(前五)找出了A2 A3 (C1或D1或E1)

    这个时候如果是A3排第二,的确是可以取出来(C1或D1或E1),但是如果是A3排名第二,这个时候很可能A组的都是飞毛腿,(C1或D1或E1 )完全跑不过A4A5,也就是只能选出来两个。那还剩下A4,A5,B1,C1,D1,E1,要选出前2名。已经确定C1,D1,E1中的顺序,那就丢掉最末的那个马,剩下的5只再跑一次。答案还是8。

发表评论

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