笔试面试题:25匹赛马,5个跑道,每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马

时间:2022-06-07 21:39:02

该题最早在10月12日360的笔试中见到。作为一道选择题出现 

A、7 B、8 C、9 D、10


先给出一种启发式方法

方法一:

1)将25匹马分成5组,进行5场比赛。

2)将每组的第一名放到一起,进行第6场比赛,选出排名第1的马。

3)选择一匹有可能进入前5,但尚未参加比赛的马(有且仅有1匹,为什么?),与上一场剩余的四匹马进行第7场比赛,选出排名第2的马。此时,若新加入的小组第2名的马位列本次比赛第5。则说明其余4匹马,为整体排名2-5的马,选择结束。大多数情况并非如此幸运。

5)根据如上规则进行第8、9、10场比赛,选出第3、4、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

(数子代表组号,字母代表小组内排名)

1)进行5场比赛,得到如上分布。

2)选A1 A2 A3 A4 A5进行第六场比赛,选取排名第1的马,(假设为A1)

3)选取B1 A2 A3 A4 A5进行第七场比赛,选取排名第2的马。假如这场比赛中B1 排名最末,则说明A2  A3 A4 A5位列2-5名,选择结束。

4,5)略


由上述可见,该方法最差需要7-10次。取最差情况为10次。

该方法选出了5匹最快的马,且给出了他们之间的排名;而题目中只要求前者,因此方法一“超额”完成了任务,代价就是比赛的场数过多。并且显然该方法不稳定。那么可不可以进行优化,使其稳定在7-10的一个数字呢。下面给出一种只需8的方法。

方法二:

1)同方法一(1),

2)选取每组的第2名进行第6场比赛。假设比赛排名从前往后依次为 B1 B2 B3 B4 B5,则A1肯定位列1-5名,同时B3-E3 B4-E4 B5-E5定不是前5名。

3)选取C1 B2 A3 A4 A5进行第7场比赛。这时就需要分类讨论了。

   a)B2获得小组第1名,此时情况比较简单,B2全部排名第4(B1,A2为第2、3名),只需在C1,A2,A3,A4 ,A5之间进行第8场比赛,找出第5名即可。(八场)

   b)C1获得小组第1名,此时,排名一定在C1前的有A1 B1,可能在C1前的有 A2,此时B1,C1入选前5名。此时还需针对B2,进行分类讨论:

          b.1)若B2为小组第2名,则第4、5名只可能出现在D1 E1 A2 B2的位置上,该四匹马进行第8场比赛,找出4、5名。

          b.2)若B2为小组第3名,不妨设排名为C1 A3 B2 A4 A5(考虑A3 A4 A5的轮换对称性,始终假设A3先于A4先于A5,下同),则此时A4 A5定无法进入前5,可能进入前5的为 D1 E1 A2 B2 A3,该五匹马进行第8场比赛,找出4、5名。

          b.3)B2为小组第4名,设排名为C1 A3A4 B2 A5,则B2 A5无法进入前5,可能进入前5的为D1 E1 A2 A3 A4。

   c)A3获得小组第1名,则可能在A3前的只有A1 B1 A2,所以A3进入前5名。针对第小组第2名进行分类讨论

          c.1)C1获得小组第2名,则B2之前有A1 B1 A2 A3 C1,B2不可能进入前5名;B1之前只可能有A1 A2 A3,B1进入前5名。可能进入前5名的还有C1 D1 A2 A4。该4匹进行第8场,选出第4、5名。

          c.2)B2获得小组第2名,则C1之前有A1 B1 A2 B2 A3,C1不可能进入前5名;B1之前只可能有A1 A2 A3,B1进入前5名。B2之前只可能有A1 A2 A3 B1,B2进入前5名,A2进入前5名。

          c.3)A4获得小组第2名,

              c.3.1)C1获得小组第3名,则排名在B1之前的有A1,可能排在B1之前的有A2 A3 A4,B1进入前5名,B2之前的有A1 A2 B2 C1 A3 A4,B2不可能进入前5名,则可能进入前5名的为C1 A2 A3 A4,第8场比赛从中选择第4、5名。

              c.3.2)B2获得小组第3名,则前5名为A1 A2 A3 A4 B1。

              c.3.3)A5获得小组第3名,则第4、5名可能为A4 A5 A2 B1。进行第8场。

该方法进行7-8场比赛。

本方法穷举了所有情况。缺少系统的概括。