一道面试题

据说是腾讯的面试题,我也来试一下。

有36辆摩托车6个赛道,在没有计时器的情况下,如果要选出跑得最快的三辆车,至少需要几次比赛?

首先将36辆摩托车分为6组,每组分别进行一次比赛。这时候获得的信息有:每组的第一名,第二名,第三名…

因为只需要选出跑得最快的三辆车,这时候将每组的第一名划为A组,第二名划为B组,第三名划为C组。因为A组有可能有车是本组最快,但不是所有组的前三快。而剩下的后三组的后三辆一定不存在最快的前三辆车。

下面分组如下:

每组第一名:A1 A2 A3 A4 A5 A6

每组第二名:B1 B2 B3 B4 B5 B6

每组第三名:C1 C2 C3 B4 B5 B6

然后让A组进行一次比赛,假如获胜的是A1 A2 A3(并且他们的顺序也确定了,假如就是A1>A2>A3),那么A4 A5 A6以及他们的组内一定不存在前三快的车。所以舍弃。下面需要讨论的如下:

A1 A2 A3

B1 B2 B3

C1 C2 C3

又因为A1>A2>A3,所以有A1>A2>A3>B3>C3,因此B3、C3被淘汰掉,剩下分组如下:

A1 A2 A3

B1 B2

C1 C2

再比一下A2 A3 B1 B2 C1 C2就可以了。

总共是6+1+1=8

原文地址:https://www.cnblogs.com/kirai/p/4775785.html