面试智力题之赛马问题

面试智力题之赛马问题

Administrator 605 2021-02-06

起因：今天在牛客看面经的时候偶然看到了一道智力题，简单记录一下

问题

现在共有 64 匹马，有 8 条赛道，最少需要多少次赛马能选出最快的 4 匹马？（假设马匹的速度恒定且不会疲劳，且没有计时器，但是可以得到相对名次）

解法

设 cnt 为赛马的次数

  1. 先将所有马匹分为 8 组，每组进行一次赛马，每组都可以得到相对名次，则可以删除每组的都 5 - 8 名，它们必然不可能时最快的 4 匹马，此时剩余 32 匹马

    +----+----+----+----+----+----+----+----+
| A1 | B1 | C1 | D1 | E1 | F1 | G1 | H1 |
+----+----+----+----+----+----+----+----+
| A2 | B2 | C2 | D2 | E2 | F2 | G2 | H2 |
+----+----+----+----+----+----+----+----+     (cnt = 8)
| A3 | B3 | C3 | D3 | E3 | F3 | G3 | H3 |
+----+----+----+----+----+----+----+----+
| A4 | B4 | C4 | D4 | E4 | F4 | G4 | H4 |
+----+----+----+----+----+----+----+----+

  2. 将每组的第一名都拉出来进行比赛，就可以去除第一名中后四名所在的组的所有马，此时剩余 16 匹马

    +----+----+----+----+
| A1 | B1 | C1 | D1 |
+----+----+----+----+
| A2 | B2 | C2 | D2 |
+----+----+----+----+                         (cnt = 9)
| A3 | B3 | C3 | D3 |
+----+----+----+----+
| A4 | B4 | C4 | D4 |
+----+----+----+----+

    此外，A1 无论在当先所在的组中，还是在各个第一名中都是第一，则必然是第一名。

    其次，如果 D1 在前四名中，则必然为第 4 名，其所在组中的其余马匹都不可能在前 4 名中。

    C1 ，C2 同理，如果 C2 在前 4 名中，则必然为第 4 名，其余马匹被排除。

    A ，B 赛道同理，可以排除 B4。

    此时剩余 9 匹马，只需要在其中筛选出第 2，3，4 名即可。

         +----+----+----+
     | B1 | C1 | D1 |
+----+----+----+----+
| A2 | B2 | C2 |
+----+----+----+                              (cnt = 9)
| A3 | B3 |
+----+----+
| A4 |
+----+

  3. 现在假设 B1 为第二名，将其余的马 8 匹马进行赛马

    • 如果 B2 或者 C1 进入了前三名，则可将 B1 插入到 B2 或者 C1 之前，必然可以选出前 2, 3, 4 名，选择结束 (cnt = 10)
    • 否则，可以选出前两名，并将 B1 加入再赛跑一次，选出第一名即可 (cnt = 11)

参考

Algorithm