乐趣区

关于前端:百度小红书三面均遇赛马问题

关注公众号“执鸢者”,回复“材料”获取 500G 材料(各“兵种”均有),还有业余交换群等你一起来洒脱。(哈哈)

适逢金三银四的跳槽的黄金时段,看到很多小伙伴都在拼命的找工作、找实习,本人已经的面试经验也浮现在眼前,特地是一道在百度和小红书三面时遇到的“赛马”问题,既然很多公司都爱问这个问题,那么是时候将该问题储备到本人的面筋小题库中了。

一、题目

一个赛场中有 5 条赛道,当初有 25 匹马,在没有定时器的前提下起码跑多少圈能够角逐出前三名?

二、头脑风暴

刚遇到这个问题的时候,不晓得小伙伴们是什么想法,反正霎时属于懵逼状态,懵逼过后就进入了剖析问题的环节。

2.1 全副马均需跑一次

不管怎样,25 匹马必定都须要上跑道跑一下(是骡子是马,拉进去溜溜),所以先将马匹分成 5 组(25 / 5 = 5;其中 25 指马匹数、5 指赛道数,获取到的就是组数),各组标号别离是 A、B、C、D、E,最终全副 5 组较量之后的后果如下表所示:

通过本轮较量之后,曾经跑了五圈,通过这五圈之后可能获取到的信息就是每组都角逐出了第一名(A1、B1、C1、D1、E1),然而到底谁是前三名还不能确定,接下来咱们所能做的是持续进行较量,然而让谁进行比呢?这个时候必定不是轻易选,轻易选的话咱们后面五圈做的铺垫就没有意义了,所以此时将每组第一名赛一圈再说,至多可能角逐出 25 匹马中谁是最快的那个仔。

2.2 每组第一名赛一次

上面将每组第一名的马匹(A1、B1、C1、D1、E1)牵出来进行较量,比赛结果如下所示:

通过本轮较量之后,曾经跑了六圈,在第六圈完结之后,咱们获取的信息就变的丰盛很多,很多老铁必定会说了,通过第六圈之后咱们不就晓得了第一名是谁了,除了这个还有啥有用信息,这个时候才是最最重点的地位(敲黑板),上面我间接列举进去可能获取到的信息:

  1. 第一名是 A1
  2. 每组第一名的程序也确定了,速度程序是:B1 > C1 > D1 > E1
  3. A2-A5 的速度有可能比其它组的都快;B2-B5 的速度有可能比 C、D、E 组的都快;C2-C5 的速度有可能比 D、E 组的都快;D2-D5 的速度有可能比 E 组的都快。

通过获取到的信息进一步用咱们聪慧的脑袋加工一下,到底谁有可能获取到 2、3 名呢?

上述图中间接标出了可能获取 2、3 名的马匹,然而为什么会是这些马匹呢?上面一起剖析一下。

  1. 若 A2、A3 的速度比其它组的都快,则必定是 A2、A3 别离包揽 2、3 名;
  2. 若 A2、A3 的速度比肯定比其它组的速度快,则 B2 就有可能竞争 2、3 名;B2、C1 就有可能竞争第 3 名。

2.3 A2、A3、B1、B2、C1 赛一次

通过这五匹马再赛一圈之后,就曾经跑了七圈,第七圈角逐进去的 2、3 名就是最终后果的 2、3 名。

2.4 论断

通过上述剖析,5 条赛道,当初有 25 匹马,在没有定时器的前提下起码须要 7 圈能够角逐出前三名。

三、扩大

若当初想角逐出前 4 名起码须要多少圈?

3.1 信息剖析

在赛到第七圈的时候,曾经角逐进去了前三名, 此时可能获取到的信息有:

  1. 前三名是谁
  2. 第七圈的第三名是谁

目前要角逐出第四名,只须要通过比第七圈外面的第三名,和总体第三名前面可能产生第三名的地位即可。

3.2 问题解答

若前三名别离是 A1、B1、C1,第七圈后果是 B1、C1、A2、A3、B2,则可能产生总体第四名的地位是 A2、C2、D1,则只须要比拟三者即可跑出第四名。

3.3 论断

角逐出前 4 名至多须要跑 8 圈。

四、思考

5 条赛道,25 匹马,没有定时器的状况下角逐出前三名起码须要 7 圈,角逐出前四名起码须要 8 圈,那么角逐出前五名呢?欢送老铁留言解答。

退出移动版