面试智力题之赛马问题

面试智力题之赛马问题

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

问题

现在共有 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 名中。

    C1C2 同理,如果 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)

参考