BAT 面试题：25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？

╰半夏微凉° 2022-02-24 14:51 246阅读 0赞

写在前面：最近在刷面试题的过程中遇到这么一道题，感觉解读题目的角度很多，这里介绍自己的做法。注意：本文并不是参考答案，只是为大家在面试的时候多提供一条思路，或许可以获得面试官的青睐。

> 25匹马，5个跑道，每个跑道最多能有 1 匹马进行比赛，最少比多少次能比出前 3 名？前 5名？

## 1 - 一些假设 ##

同一马匹在任意场次的速度都能保持一致。

## 2 - 前 3 名分析 ##

1.  将 25 匹马分为 5 个小组，每个小组跑一场，共 5 场比赛。假设决出的顺序如下图：
    
    <table> 
     <thead> 
      <tr> 
       <th>组A</th> 
       <th>组B</th> 
       <th>组C</th> 
       <th>组D</th> 
       <th>组E</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>A1</td> 
       <td>B1</td> 
       <td>C1</td> 
       <td>D1</td> 
       <td>E1</td> 
      </tr> 
      <tr> 
       <td>A2</td> 
       <td>B2</td> 
       <td>C2</td> 
       <td>D2</td> 
       <td>E2</td> 
      </tr> 
      <tr> 
       <td>A3</td> 
       <td>B3</td> 
       <td>C3</td> 
       <td>D3</td> 
       <td>E3</td> 
      </tr> 
      <tr> 
       <td>A4</td> 
       <td>B4</td> 
       <td>C4</td> 
       <td>D4</td> 
       <td>E4</td> 
      </tr> 
      <tr> 
       <td>A5</td> 
       <td>B5</td> 
       <td>C5</td> 
       <td>D5</td> 
       <td>E5</td> 
      </tr> 
     </tbody> 
    </table>
2.  取每个小组的第一名跑一场，假设决出的顺序为 `A1 > B1 > C1 > D1 > E1`，则 A1 是第一名，**剔除掉没有希望进入前 3 的马匹后**，排序表变为：
    
    <table> 
     <thead> 
      <tr> 
       <th>组A</th> 
       <th>组B</th> 
       <th>组C</th> 
       <th>组D</th> 
       <th>组E</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>-</td> 
       <td>B1</td> 
       <td>C1</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A2</td> 
       <td>B2</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A3</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
     </tbody> 
    </table>
    
    容易发现，刚好只剩下 5 匹马，可以在一场比赛跑完。
3.  结果就是 5 + 1 + 1 = 7 场。

## 3 - 前 5 名分析 ##

1.  和前 3 名的分析类似，分成 5 个小组，5 个小组的第一名再跑一场，决出第一名后剔除没有机会进入前 5 的马匹，排序表如下：
    
    <table> 
     <thead> 
      <tr> 
       <th>组A</th> 
       <th>组B</th> 
       <th>组C</th> 
       <th>组D</th> 
       <th>组E</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>-</td> 
       <td><code>B1</code></td> 
       <td>C1</td> 
       <td>D1</td> 
       <td>E1</td> 
      </tr> 
      <tr> 
       <td>A2</td> 
       <td>B2</td> 
       <td>C2</td> 
       <td>D2</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A3</td> 
       <td>B3</td> 
       <td>C3</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A4</td> 
       <td>B4</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A5</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
     </tbody> 
    </table>
    
    注意到 B1 是 BCDE 四组中最快的马，但是 B1 和 A 组剩下的马的快慢暂不得知。B1 与 A 组马的顺序将会直接影响接下来需要跑的场次。
2.  让 A 组剩下的 4 匹马和 B1 跑一场，则可能出现如下结果：
    
    <table> 
     <thead> 
      <tr> 
       <th>结果 1</th> 
       <th>结果 2</th> 
       <th>结果 3</th> 
       <th>结果 4</th> 
       <th>结果 5</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>A2</td> 
       <td>A2</td> 
       <td>A2</td> 
       <td>A2</td> 
       <td><code>B1</code></td> 
      </tr> 
      <tr> 
       <td>A3</td> 
       <td>A3</td> 
       <td>A3</td> 
       <td><code>B1</code></td> 
       <td>A2</td> 
      </tr> 
      <tr> 
       <td>A4</td> 
       <td>A4</td> 
       <td><code>B1</code></td> 
       <td>A3</td> 
       <td>A3</td> 
      </tr> 
      <tr> 
       <td>A5</td> 
       <td><code>B1</code></td> 
       <td>A4</td> 
       <td>A4</td> 
       <td>A4</td> 
      </tr> 
      <tr> 
       <td><code>B1</code></td> 
       <td>A5</td> 
       <td>A5</td> 
       <td>A5</td> 
       <td>A5</td> 
      </tr> 
     </tbody> 
    </table>
    
    容易发现，由于 B1 的特殊性，结果 1 和结果 2 其实已经决出了前 5 的马匹（包括 A1），结果 3 决出了前 4 的马匹，结果 4 决出了前 3 的马匹，结果 5 决出了前 2 的马匹。
3.  所以最少需要 5 + 1 + 1 = 7 场。（题目到这里就可以结束了）
4.  结果 1 和结果 2 具有偶然性，出现其他结果时的情况比较复杂，但是考虑到每场都会至少确定 1 个名次，那么实际上最多 5 + 5 =10 场就能确定前 5 。

## 4 - 拓展 ##

64匹马，8条跑道，决出前4名？

1.  分 8 组，决出第一名之后剔除不能进入前 4 的马匹，如下：
    
    <table> 
     <thead> 
      <tr> 
       <th>组A</th> 
       <th>组B</th> 
       <th>组C</th> 
       <th>组D</th> 
       <th>组E</th> 
       <th>…</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>-</td> 
       <td>B1</td> 
       <td>C1</td> 
       <td>D1</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A2</td> 
       <td>B2</td> 
       <td>C2</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A3</td> 
       <td>B3</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
      <tr> 
       <td>A4</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
       <td>-</td> 
      </tr> 
     </tbody> 
    </table>
    
    还剩 9 匹马，一次跑不完。
2.  笔者的考虑是第 10 场先不安排A4、B3、C2、D1中的某一匹，因为这 4 匹马相对较慢，很大几率不会入选前 4，根据结果来确认是否需要第 11 场。比如，第 10 场 D1 没有上场，如果（速度比 D1 快的）B1 或者 C1 不在前 3，那么 D1 就没有再上场的必要了。反之，若 B1、C1分别是第 2 、第 3 名，那么 D1 还是有机会争一争第 4 的。
3.  所以按这个思路，最多 11 场，最少 10 场就能确认前 4。

## 再次强调：本文不是标准答案，请勿擅自曲解笔者意思。最后，祝大家面试顺利～ ##

--------------------

正文结束，欢迎留言讨论。