二十五匹马五个赛道求五匹最快马最少需要多少次问题的原理是什么？{技术}{算法}
phpxer
一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比
赛，试问在最坏情况下最少得比多少场才能知道跑得最快的5匹马。
这是一个在CSDN和Javaeye上都讨论过的问题，回答过这个问题的人们大多数努力使用类似于贪心的策略，总是选择最靠前的马去比赛，有许多人答八
场或者九场(参考我后面的论证)。但是这种方法也可能不是最好的，显然没有利用到在比赛过程中，有的马之间形成了一定的顺序关系。或许可以利用好这些顺
序。尝试从算法和数据结构书中也没有找到类似可以切入的理论。哪位牛人帮忙找下靠谱的依据？
前5轮应该没有什么争议，就是5个队都比一场，暂且这样排名，名字在前面的快些。
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5
我的方法： 主要根据是每次都取最靠前的马参与下一轮的角逐：
第六场： 选取各组的第一批马，不失一般性，假设为 A1>B1>C1>D1>E1。可决出第一名A1.
此时有一些马可以被排除了，如：
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --
第七场： 选择A2,A3,B1,B2,C1 参加比赛，此次显然可得出第二名(B1 | A2)和第三名。
接下来的第四名和第五名应该可以在第八场就决出。我是用穷举的方式得出的，不知道有没有什么很好的证明方式？
CSDN: http://topic.csdn.net/u/20091024/12/989417AA-60E9-45D1-A96F-A623695FC6D7.html
JavaEye: http://www.javaeye.com/topic/255969
（第一次发贴，搜过了，在TopLanguage上没有发过此题，如有不合规矩请见谅）
realfun
--
题酷@ http://fayaa.com/tiku/ 精彩、经典、最新IT面试题库、智力题库
代码@ http://fayaa.com/code/ 无需插件支持blog代码高亮，100+种语言，30+种高亮主题
游戏@ http://fayaa.com/youxi/ 华容道、数独等在线游戏及求解、图解
图标@ http://fayaa.com/tool/favicon/ 在线制作网站图标(favicon)，工具简单易用，很好很强大 :)
Blog@ 半瓶墨水 http://www.2maomao.com/blog
Follow me @ http://twitter.com/realfun
zhaoren liu
陈路
phpxer
些可能的马，而超出该路径的就可以直接剪掉不需要参与该轮的比赛。可惜把大学里学的东西都还给老师了，哪位仁兄出来证明一下这个问题？另外，我觉得这是
最快的，但是没找到理论依据.....
On Nov 4, 4:26 pm, 陈路 <chenl...@gmail.com> wrote:
> 图
>
> 2009/11/4 realfun <real...@gmail.com>
>
> > 参见：http://fayaa.com/tiku/view/91/
>
> > 这里面有个回答分析的很彻底http://blog.solrex.cn/articles/25-horses-problem.html
>
> > 2009/11/4 phpxer <php...@gmail.com>
>
> > 题目：
> >> 一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比
> >> 赛，试问在最坏情况下最少得比多少场才能知道跑得最快的5匹马。
>
> >> 这是一个在CSDN和Javaeye上都讨论过的问题，回答过这个问题的人们大多数努力使用类似于贪心的策略，总是选择最靠前的马去比赛，有许多人答八
> >> 场或者九场(参考我后面的论证)。但是这种方法也可能不是最好的，显然没有利用到在比赛过程中，有的马之间形成了一定的顺序关系。或许可以利用好这些顺
> >> 序。尝试从算法和数据结构书中也没有找到类似可以切入的理论。哪位牛人帮忙找下靠谱的依据？
>
> >> 前5轮应该没有什么争议，就是5个队都比一场，暂且这样排名，名字在前面的快些。
> >> A组 A1 A2 A3 A4 A5
> >> B组 B1 B2 B3 B4 B5
> >> C组 C1 C2 C3 C4 C5
> >> D组 D1 D2 D3 D4 D5
> >> E组 E1 E2 E3 E4 E5
>
> >> 我的方法： 主要根据是每次都取最靠前的马参与下一轮的角逐：
> >> 第六场： 选取各组的第一批马，不失一般性，假设为 A1>B1>C1>D1>E1。可决出第一名A1.
> >> 此时有一些马可以被排除了，如：
> >> A组 A1 A2 A3 A4 A5
> >> B组 B1 B2 B3 B4 --
> >> C组 C1 C2 C3 -- --
> >> D组 D1 D2 -- -- --
> >> E组 E1 -- -- -- --
>
> >> 第七场： 选择A2,A3,B1,B2,C1 参加比赛，此次显然可得出第二名(B1 | A2)和第三名。
> >> 接下来的第四名和第五名应该可以在第八场就决出。我是用穷举的方式得出的，不知道有没有什么很好的证明方式？
>
> >> CSDN:
> >>http://topic.csdn.net/u/20091024/12/989417AA-60E9-45D1-A96F-A623695FC...
石奇偲
这实际是一个很经典的问题，数据结构书中有提到。
抽象一下，这就是内存有5个单位，外存有25个单位的外部排序，用败者树分析。
Gaofeng Zeng
在 2009年11月4日星期三UTC+8下午3时45分49秒，phpxer写道：
