赛马问题

最近在网上看到一道逻辑题,听说是腾讯的面试题,这里分析一下如何解这道题。

问题如下:

64匹马,8个赛道,找出跑得最快的4匹马,至少比赛几场?

解法一

首先用最简单的办法,8匹马需要一场比赛就可以找出最快的4匹马,16匹马可以分成两组8匹马,各自比赛找出最快的4匹,然后两组4匹合成一组再比一次,一共比3场可以找出最快的4匹马。

第一场: a1 a2 a3 a4 a5 a6 a7 a8 -> [a1 > a2 > a3 > a4] > a5 > a6 > a7 > a8

第二场: b1 b2 b3 b4 b5 b6 b7 b8 -> [b1 > b2 > b3 > b4] > b5 > b6 > b7 > b8

第三场: a1 a2 a3 a4 b1 b2 b3 b4 -> [a1 > a2 > b1 > b2] > a3 > a4 > b3 > b4

以此类推,32匹马可以分成2组16匹马,需要3+3+1=7场比赛,64匹马需要7+7+1=15场比赛。这是最简单的解法,比较中规中矩,但还有优化的空间。

解法二

64匹马分成8组8匹马,各自比赛选,共8场,每组选出前4匹,共32匹马。然后将每组的第一名放在一起比1场,后4名对应的组可以淘汰掉,还剩4组4匹,共16匹马,其中有以下关系。现在已经是第9场比赛。

a1 > a2 > a3 > a4
v
b1 > b2 > b3 > b4
v
c1 > c2 > c3 > c4
v
d1 > d2 > d3 > d4

可以看出a1, a2, a3, a4, b1, b2, b3, c1, c2, d1是可能进入前4的,其余的淘汰掉,还剩10匹,剩余的马如下所示:

a1 > a2 > a3 > a4
v
b1 > b2 > b3
v
c1 > c2
v
d1

a1可以确定是最快的一匹马,所以接下来不用考虑a1,只要在剩下的9匹里寻找最快的3匹马。这里需要一些逻辑判断,观察上图中除了第一行,可以看出b1是后三组中最快的一匹马,将除了b1以外的8匹马作为一组,进行一次比赛,这是第10场。如果8匹马的前2名中有c1或b2,说明b1一定在总比赛的前4名中,这种情况下10场比赛已经找出了前4名;如果8匹马的前3名为a2, a3, a4,那么不知道b1是否在前4名中,需要b1, a2, a3, a4再比一次,这种情况下需要11场比赛才能找出前4名。综上所述,经过优化后需要10或11场比赛可以64匹马中从找出最快的4匹马。

发表评论

电子邮件地址不会被公开。 必填项已用*标注