有25匹马，共5个跑道，不用任何工具，请问：

1. 用几场比赛可分出前3名？
2. 几场比赛可以分出前5名？
3. 几场比赛可以给所有赛马排名？

我尝试分析了一下这道题，写了篇博客：25 马问题，感兴趣的朋友可以过去看一下对不对。

我得出来的结论是，25 取前三，最坏情况下最少比赛次数是 7； 25 取前五，最坏情况下最少比赛次数是 9.

1)首先赛5次，每次不同的马，假设结果为

a11,a12,a13,a14,a15,

a21,a22,a23,a24,a25,

...

a51,a52,a53,a54,a55

2)然后上5次的第一名赛一次，不失一般性假设结果为 a11,a21,a31,a41,a51

现在赛了6次了

3)可以确定所有马中第一名是a11；第二三名只能从a12,a13,a21,a22,a31中得到，他们赛一次，得到第二第三

现在赛了7次了

4)假如第二是a12,则第三是a13或a21

4.1)假如a13第三，第四五只能从a14,a15,a21,a22,a31中选,赛第8次得到前五

4.2)假如a21第三，现在可以确定第四。 有这些情况：

4.2.1)a12<a21<a13<a22 or a12<a21<a13<a31     a13是第四
       第五从a22,a31,a14中选

4.2.2)a12<a21<a22<a13<a31                    a22第四
       第五从a23,a13中选

4.2.3)a12<a21<a32<a31<a13                    a32第四
       第五从a23,a31中选

以上情况，赛8次得到前五

5)假如第二是a21,则第三是a12,a22,或a31,

5.1)a31第三，则第四五只能从a41,a51,a12,a13,a22中得到，赛8次得到前五

5.2)a12第三，现在可以确定第四，类似4.2)，再赛一次得到第五

5.3)a31第三，现在可以确定第四，类似4.2)，再赛一次得到第五

综上所述，8次赛马可以得到前五。请指教

分五组，五路归并排序，头五个。这样得到比赛次数是：5+5=10

BTW，如果选头三名只要七次。

我觉得这其实是个可以编程求解的问题，这个跟猜数字游戏很像

几点零星的想法，等到有时间再来细化：

1. 几次赛马以后，实际上生成了一个逻辑排序的图，每一次赛马，都要尽可能的把这个图变成一条线
2. 贪心的标准可以是：消除尽量多的分支
3. 每一步采用贪心算法，不一定能做到全盘最优 - 我求解猜数字游戏的时候就遇到过，贪心总是会有3、4个需要8步的，而全局最优却可以做到都在7步以内
4. 如果只是前三名，或许贪心算法得到的结果跟全局最优是一致的
5. 全局最优的算法，粗略一想，需要25!的计算量。要尽量减少计算的话，就要考虑做一些cache，滤掉重复性的计算，或许需要用到动态规划
6. 如果只是要求前三名，全盘最优应该很容易做到

先写这么多，等有时间再来写程序验证。。。

矩阵没排出来。。。这里重贴：
10 1 1 1 1
9 9 9 9 9
8 1 1 1 1
1 1 1 1 1
1 1 1 1 1
＝＝＝＝＝＝＝＝＝＝＝

补充，仔细一看，我搞错了lol

10 1 1 1 1
9 1 1 1 1
8 7 6 1 1
7 6 5 1 1
6 1 1 1 1
（这几个中文是凑数。。。）

我也参与一下，我想是五场吧，按比赛时每匹马到达的时间排序就可以了。

9场，这个题目我画了3张纸，最坏情况是9场。

补充说明哦，前3名是7次，前4名是8次