赛马比赛--25匹马5个跑道,怎样选出最快的5匹来

时间:2022-06-07 21:39:08

题目一(网易笔试题):25匹马5个跑道,怎样选出最快的5匹来?最少的次数

题目二(2016美团校招笔试题):30个马赛跑,5个跑道,找出前五名,至少找几次

题目三:64匹马,8条跑道,分几次可以选出最快的4匹?


********** ********** ********** ********** ********** **********

题目一:最多10次

题目二:最多12次

题目三:最多13次


********** ********** ********** ********** ********** **********

以题目一为例:

Step1:

先将25匹马按5条跑道分组:

1 24 22 2 16

6 19 3 9 7

11 8 10 14 15

12 17 18 13 20

21 5 23 4 25

将以上5组马分别进行比赛并排序。【比赛总次数:5】

24 22 16 2 1

19 9 7 6 3

15 14 11 10 8

20 18 17 13 12

25 23 21 5 4


Step2:

将最快马匹数(TopCount)除以赛道数(TrackCount)取整得到GroupCompIndex,即每组马匹中第几名应该进行第6场比赛。

GroupCompIndex = TopCount/TrackCount=5/5=1 (取每组的第二名进行比赛)

22 9 14 18 23

比赛结果为【23 22 18 14 9】 【比赛总次数:5+1=6】


依据第六场比赛结果Step1中的5组比赛进行排名:

第1组:25 23 21 5 4

第2组:24 22 16 2 1

第3组:20 18 17 13 12

第4组:15 14 11 10 8

第5组:19 9 7 6 3


依据上表分析:

第1组的第GroupCompIndex名肯定是前6名,因为比第1组的第【GroupCompIndex】名快的只有每组的第一名。【最重要的依据,遇到TopCount > GroupCompIndex * TrackCount第GroupCompIndex名肯定也是Topn

第1组的第0..GroupCompIndex名(不包含GroupCompIndex)肯定是前5名,因为比第1组的第【GroupCompIndex】名大的只有最多5名。【获得Top5数据:25】

查找剩余的可能是Top4的成员列表

针对第n组,存在(【GroupCompIndex】+ 1)* (n - 1) 匹马比当前组的第【GroupCompIndex】匹马快。

也就是当前组有 TopCount - (【GroupCompIndex】+ 1)* (n - 1) 匹马是Top5或者比第【GroupCompIndex】名快的未进行比赛赛马可能是Top5

例如:

第1组TopCount - (【GroupCompIndex】+ 1)* (1 - 1) = 5-2*0 = 5;所以所有成员都有可能是Top4:【23215 4】

第2组TopCount - (【GroupCompIndex】+ 1)* (2 - 1) = 5-2*1 = 3;所以成员【242216】都有可能是Top4

第3组TopCount - (【GroupCompIndex】+ 1)* (3 - 1) = 5-2*2 = 1;所以成员【20】都有可能是Top4

第4组TopCount - (【GroupCompIndex】+ 1)* (4 - 1) = 5-2*3 = -1,小于0取本组第【GroupCompIndex】之前的马;所以成员【15】都有可能是Top4

第5组TopCount - (【GroupCompIndex】+ 1)* (5 - 1) = 5-2*4 = -3,小于0取本组第【GroupCompIndex】之前的马;所以成员【15】都有可能是Top4

由此得到Top4的列表:

23 21 5 42422 16 20 15 19

再按照Step1,Step2进行递归运算,直到只存在一组时,直接取钱Topn




Top4分组:

23 21 5 4 24

22 16 20 15 19

Top4分组排序: 【比赛总次数:6+2=8】

24 23 21 5 4

22 20 19 16 15

按照GroupCompIndex:2进行比较【21,19】 排序两组 【比赛总次数:8+1=9】【获得Top5数据:25,24,23】

24 23 21 5 4

22 20 19 16 15


Top2分组:

21 5 4 22 20

Top2分组排序:

22  21  20  5 4      【比赛总次数:9+1=10】【获得Top5数据:25,24,23,22,21】