【每日一道智力题】之 赛马找最快

简介: 【每日一道智力题】之 赛马找最快

问题:

       25匹马5条跑道找最快的3匹马,需要跑几次?

将25匹马分成ABCDE5组,假设每组的排名就是A1>A2>A3>A4>A5,用边相连,这里比赛5次第6次,每组的第一名进行比赛,可以找出最快的马,这里假设A1>B1>C1>D1>E1。而D1,E1肯定进不了前3,直接排除掉。第7次,B1 C1 A2 B2 A3比赛,可以找出第二,第三名,所以最少比赛需要7次。

这里会有同学问为什么第七次会有B1,C1参与比赛,原因是:当我们得知第一是A1以后,无法得知第二名和第三名是否和第一名在第一场比赛里同组,为了防止这种事情的发生,我们就要检测B1,C1是否是真的二三名。B2也是同样的道理。

       64匹马8条跑道找最快的4匹马,需要跑几次?

第一步

全部马分为8组,每组8匹,每组各跑一次,然后淘汰掉每组的后四名,如下图(需要比赛8场)

这个时候,

取每组第一名进行一次比赛,然后淘汰最后四名所在组的所有马,如下图(需要比赛1场)

这个时候总冠军已经诞生,它就是A1,蓝色区域(它不需要比赛了),而其他可能跑得最快的三匹马只可能是下图中的黄色区域了(A2,A3,A4,B1,B2,B3,C1,C2,D1,共9匹马)

第三步

只要从上面的9匹马中找出跑得最快的三匹马就可以了,但是现在只要8个跑道,怎么办?那就随机选出8匹马进行一次比赛吧(需要比赛一场)

第四步

上面比赛完,选出了前三名,但是9匹马中还有一匹马没跑呢,它可能是一个潜力股啊,那就和前三名比一比吧,这四匹马比一场,选出前三名。最后加上总冠军,跑得最快的四匹马诞生了!!!(需要一场比赛)

最后,一共需要比赛的场次:8 + 1 + 1 + 1 = 11 场

       25匹马5条跑道找最快的5匹马,需要跑几次?

有些同学的思路是这样的:

(1) 首先将25匹马分成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]

     其中,每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场,选出第1名的马,不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场,此时选择出来的必定是第2名的马,不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场,选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推,第9,10场可以分别决出第4,5名的吗。

因此,依照这种竞标赛排序思想,需要10场比赛是一定可以取出前5名的。

但是,仔细想一下,如果需要减少比赛场次,就一定需要在某一次比赛中同时决出2个名次,而且每一场比赛之后,有一些不可能进入前5名的马可以提前出局。 当然要做到这一点,就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题,希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论:有一些马在前6场比赛之后就决定出局的命运了(下面粉色字体标志出局)。

      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 ]

(3) 第7场比赛是关键,能否同时决出第2,3名的马呢?我们首先做下分析:

    在上面的方法中,第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1),试问?有B1在的比赛,C1、D1、E1还有可能争夺第2名吗? 当然不可能,也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名,剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗?

    能够优化的关键出来了,我们是否能够通过剩下的3个跑道来决出第3名呢?当然可以,我们来进一步分析第3名的情况?

    ● 如果A2>B1(即第2名为A2),那么根据第6场比赛中的(B1>C1>D1>E1)。 可以断定第3名只能在A3和B1中产生。

    ● 如果B1>A2(即第2名为B1),那么可以断定的第3名只能在A2, B2,C1 中产生。

    好了,结论也出来了,只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马,那么这场比赛的第2,3名一定是整个25匹马中的第2,3名。

    我们在这里列举出第7场的2,3名次的所有可能情况:

    ①  第2名=A2,第3名=A3

    ②  第2名=A2,第3名=B1

    ③  第2名=B1,第3名=A2

    ④  第2名=B1,第3名=B2

    ⑤  第2名=B1,第3名=C1

(4)  第8场比赛很复杂,我们要根据第7场的所有可能的比赛情况进行分析。

     ①  第2名=A2,第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

          ● 如果第4名=A4,那么第5名只能在A5、B1中产生。

          ● 如果第4名=B1,那么第5名只能在A4、B2、C1中产生。

          不管结果如何,此种情况下,第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]

     ②  第2名=A2,第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

          ● 如果第4名=A3,那么第5名只能在A4、B2、C1中产生。

          ● 如果第4名=B2,那么第5名只能在A3、B3、C1中产生。

          ● 如果第4名=C1,那么第5名只能在A3、B2、C2、D1中产生。

          那么,第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

     ③  第2名=B1,第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

          情况和②一样,必须角逐第9场

     ④  第2名=B1,第3名=B2。 那么此种情况下第4名只能在A2、B3、C1中产生。

          ● 如果第4名=A2,那么第5名只能在A3、B3、C1中产生。

          ● 如果第4名=B3,那么第5名只能在A2、B4、C1中产生。

          ● 如果第4名=C1,那么第5名只能在A2、B3、C2、D1中产生。

           那么,第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产 生,则必须比赛两场才行,也就是到第9场角逐出全部的前5名。

       ⑤  第2名=B1,第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

           ● 如果第4名=A2,那么第5名只能在A3、B2、C2、D1中产生。

           ● 如果第4名=B2,那么第5名只能在A2、B3、C2、D1中产生。

           ● 如果第4名=C2,那么第5名只能在A2、B2、C3、D1中产生。

           ● 如果第4名=D1,那么第5名只能在A2、B2、C2、D2、E2中产生。

            那么,第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中 产 生,因此也必须比赛两场,也就是到第9长决出胜负。

       好了,今天的每日一题就到这里,我们会清楚的发现这些智力题需要我们见多识广和足够的耐心才能真正的做出了,就像我们的最后一个题目,分类讨论还是很麻烦的,但是只要我们足够的耐心,还是可以解决的!每日一题贵在坚持,希望各位大佬点赞收藏和关注!

目录
相关文章
惊险!备战3个月,五面蚂蚁金服差点倒在最后一面
作为程序员,免不了要经历面试这关,虽然平时工作勤勤恳恳,但是面试上面未必能展示的出来,比如平时都是做增删改查的业务系统,面试官非要问你如何处理高并发大数据,本来是写java代码,非要问你大型网站架构,这些问题防不胜防,本文就自己一次在蚂蚁金服的面试经验来总结一下,抛砖引玉。
【每日一道智力题】之 药瓶毒鼠鼠
【每日一道智力题】之 药瓶毒鼠鼠
204 0
【每日一道智力题】三个火枪手(快来看人生哲理)
【每日一道智力题】三个火枪手(快来看人生哲理)
275 0
|
算法 关系型数据库 定位技术
为什么订餐不会凉凉和牛顿发现万有引力有关
希望通过本次课题,与大家探讨订餐系统的技术难点及提出解决方案。
为什么订餐不会凉凉和牛顿发现万有引力有关
|
机器学习/深度学习 算法 测试技术
面试官在“逗”你系列:到底应该怎么爬楼梯?! | 牛气冲天新年征文
算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式,因为有一句古话说的好:“说一千道一万,不如写段代码看一看”。今天我们就来个单刀直入,直奔主题,从一个真实面试题到底怎么爬楼梯来聊一聊算法中的动态规划 。
205 0
【智力题】新数字游戏
两人轮流说出1到10之间的自然数,并且依次相加,先加到100的胜。请问你该怎么说?解析:反推法。假设最后一步我加到100。      我——>100      他——>90-99      我——>89      他——>79-88      我——>78      他——...
1090 0
【智力题】数字游戏2
有16枚硬币。双方轮流从中取走1枚、2枚或者4枚硬币,谁取最后一枚硬币就算输。请分析游戏的策略。可以将游戏转化为:轮流说出数字1或2或4并累加,先加到16的人输。从后往前推:我——>15他——>14\13\11我——>12他——>11\10\8我——>9他——>8\7\5我——>6他——>5\4\2我——>3可以找出一些规律。
1135 0
【智力题】找出药
共有3类药片,每片分别重1g,2g,3g,放到n个瓶子里。每个瓶里只放一类药,且瓶里药片足够多。现在有一个测重仪,如何只称一次而知各瓶中装的是哪类药?法一:第一瓶拿一片,第二瓶拿10片,第三瓶拿100片,以此类推,最后一起测重得到一个n位数,第几位的数字对应第几瓶。
1401 0
下一篇
无影云桌面