经典面试题:64匹马,8个赛道,找出前4名最少比赛多少场?
第一步:全部马分8组,各跑一次,然后淘汰掉每组的后四名(8次);
此时,只有列上有大小关系,行上是没有大小关系的。
最少10次选出前四,最多11次选出前四
在以上的两次比赛过后可以得出,A1 直接晋级,B1比B2和C1跑的快
A2、A3、A4、B2、B3、C1、C2、D1八匹马跑一次,即:在剩下需要排名的马中,除了B1外,其它8匹马跑一次(1次)
在这次比赛中,如果B2或者C1排名第一,那从该次比赛中取出前两个,和A1,B1,一起作为前4名
如果B2或者C1排名第二,那从该次比赛中取出前两个,和A1,B1,一起作为前4名
如果B2或者C1排名在第三或者第四,那么将A2,A3,A4,B1再比赛一次(1次),取前三名和A1一起作为前4名
所以64匹马,8个赛道,找出前4名最少比赛的场次是10或者11次。