赛马问题

25匹赛马，5个跑道，也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马

   
前5次大家都一样，排序后如下
A1,A2,A3,A4,A5
B1,B2,B3,B4,B5
C1,C2,C3,C4,C5
D1,D2,D3,D4,D5
E1,E2,E3,E4,E5
第六次，最大值比较，找出最快的马

第7次参加比赛的马匹为
A2 A3 B2 C2 D1

下面就3种第7次可能的比赛结果进行分析：
1、若第7次的比赛可能的一种结果为：
A2 A3 B2 C2 D1
此时必进入前5的是A1、A2、A3
可能进前5的是A4、A5、B1、B2、C1
则第8次为
A4、A5、B1、B2、C1
取前2名，与A1、A2、A3一直即为前5
2、若第7比赛结果为B2、A2、C2、A3、D1
此时必进入前5的是A1、B1、B2
可能进入前5的是A2、B3、B4、C1
第8次只要让这4匹马参赛就可以啦
3、若第7次比赛结果为D1、C2、A2、A3、B1
此时必进入前5的是A1、B1、C1、D1
而剩下的第5匹马只可能出现在C2、D2、E1这3匹马中，自然，让这3匹马参加第8次比赛就可以啦
总之，不管第7次的比赛结果如何，都在第8次比赛中做出适当的安排，即而可以在8次比赛后确定跑得最快的前5匹马。

 

问题大致是这样的：有36匹马，通过赛马寻找出最快的3匹。跑道可容纳6匹马同时赛跑，请问最快需要几次赛马可以找到最快的3匹马？

    首先假设每匹马的速度不一样，这样分析可以抓住要害。如果有速度相同的马，则问题会稍微复杂一点，但基本思路是一致的。

    先给出一个最简单的方案。36匹马随机分为6组，分别进行赛跑，那么每组的后3名将被淘汰(这些马不可能是最快的)，余下18匹马。将剩余的18匹马再次 分为3组进行赛跑，余下9匹。在最后9匹中随机选择6匹进行赛跑，将最快的3匹马与剩下3匹马进行赛跑，最后胜出的3匹马即为所求。总共赛马次数为 6+3+1+1=11

    让我们回顾一下上述的赛马过程。我们发现，最初的6次赛马之后，剩余的18匹马实际上是局部有序 的，每一组赛马的3匹优胜马都是有序的，很显然上面的做法过于简单，存在冗余操作。我们接下来要做的工作实际上类似于归并排序。那么怎么做可以用最少的赛马次数从18匹马中挑选出最快的3匹呢？

    答案是这样的：将第一组中3匹优胜马按排名令为A1,A2,A3，其中A1最快；同理第二组令为B1,B2,B3；第三组C1,C2,C3；以此类推，直 至F1,F2,F3。取A1,B1,C1,D1,E1,F1进行赛跑，为了方便说名，假设结果为 A1>B1>C1>D1>E1>F1。很显然，D1,E1,F1，将被淘汰，于是D、E、F组的其余马也将被淘汰，因为他 们比这3匹马还慢。再看C组，在剩余有竞争力的9匹马中(分别是A1,A2,A3,B1,B2,B3，C1,C2,C3)，C1最多只能排第三，那么 C2,C3不可能成为最快的3匹马之一，将其淘汰。同理观察B组，可知B3也不具备成为前三甲的可能，淘汰之！现在只剩下 A1,A2,A3,B1,B2,C1共6匹马，再次进行赛马即得到答案。总共赛马次数为6+1+1=8

    结论：最快通过8次赛马可得答案。