[已解决][趣题]赛马算法题

爱疯 · 发表于 2010-12-21 14:33

转自：http://coolshell.cn/articles/1202.html

据说，这是Google的面试题。面试题目如下：

一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问，最少得比多少场才能知道跑得最快的5匹马？（不能使用撞大运的算法）

很明显这是一个算法题，网上有很多贴子在讨论这个问题，不过都没有给出一个明确的答案。我想了想，想到下面的一个算法：

1）分成5组A，B，C，D，E，比五场。然后根据每场结果分别给这五组内的五匹马排序（从快到慢）。
2）每组的头名再赛一场，取走第一名，然后该组第二名顶上。
3）重复第二步，直到选出前5名。

这个算法是比较笨的算法，总计需要赛10次，这个算法应该是万无一失的。现在的问题的就，如何优化这个算法，想了想，的确是有优化的空间的。也就是说，是可以少于10次的。

想了一想，上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”，总是挑一个最优秀的出来，其实，在第6次以后除了挑出最优秀的，我们还可以在每次比赛后淘汰一些速度不行的，淘汰的马匹数自然会比选出的更多，所以，一方面在找，另一方面在淘汰，找出前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是25匹马里最快的马，而且我们可以淘汰近一半的马，比如E2，E3，E4，E5就可以全部淘汰了，为什么呢，因为比E2快的马有A1,B1,C1,D1,E1这五匹马，所以，E2后面的马是无法进入前五名了；同理，D3和其后面的也进入不了前5；同理，C4，C5，B5都可以淘汰。

于是，在第六轮后我们可以得知，除了A1外的Top 4必然在下面这些马中：

A组 A2 A3 A4 A5
B组 B1 B2 B3 B4
C组 C1 C2 C3
D组 D1 D2
E组 E1

接下来的过程应该不必我多说了。重复前面的方法，尽可能淘汰无法进前N名的马，于是后面的马就越来越少，你所需要的比赛也会越来越少。

那么，对于这个题，聪明的你知道最少要比赛几场了吗？

举一反三，如果有64匹马，8个赛道呢？不失一般性，如果有N匹马，M个赛道呢？N = M*M，那么公式是什么呢？

期待你的答案！

[此贴子已经被作者于2010-12-21 14:49:51编辑过]

最佳答案

月排行榜 / 总排行榜

amulee

2010-12-21 15:59

爱疯理解错误

先随便假设一下名次可能可以帮助理解
假设名次是A1,A2,B1,C1,C2

第六场。A1,B1,C1,D1,E1出来比赛
        很显然A1会赢，A1是所有马中最快的。所以A1就不用再比了，把A1先放在一边。

        接下来，我们要找剩余马中最快的。
        现在已知快的马还剩下B1,C1,D1,E1。这些马是剩下B,C,D,E中最快的，但都比A1慢点。
        那么还有哪匹马可以和它们比比呢？
        选B2？B2比B1跑得都慢，怎么和其他组比？同理C、D、E组都不行啊
        那么A2呢？A2比A1慢一点，但是没和B、C、D、E比过，A2说不定能比B1他们快哦。

第七场。A2,B1,C1,D1,E1。
        A2果然不负众望，A2晋级
        再来找剩下马中最快的
        很显然，不能选B2、C2他们，比他们跑得快的B1、C1都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才A组晋级的后面一位。这里再找A组中的A3来比

第八场。A3,B1,C1,D1,E1。
        A3没能得第一，B1跑了第一了，那么B1晋级了。

        再来找剩下马中最快的
        很显然，不能选A4、C2他们，比他们跑得快的A3、C1都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才B组晋级的后面一位。这里再找B组中的B2来比

第九场。A3,B2,C1,D1,E1。
        B2没能得第一，C1跑了第一了，那么C1晋级了。

        再来找剩下马中最快的
        很显然，不能选A4、B3他们，比他们跑得快的A3、B2都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才C组晋级的后面一位。再找C组中的C2来比

第十场。A3,B2,C1,D1,E1。
        C2跑了第一了，那么C2晋级了。

这样就找到了最快的5匹马

从第六场开始，不断找最快的，然后将最快的晋级放一边，再到剩下的马中找最快的。

跳转到最佳答案楼层

爱疯 · 发表于 2010-12-21 14:34

我没明白他是怎么算的，一种都没明白[em06]

请看明白了的人说说吧[em04]

wayy · 发表于 2010-12-21 14:46

这个算法是比较笨的算法，总计需要赛10次

amulee · 发表于 2010-12-21 15:14

他的算法是这样的。
1-5、选出5组第一名。
后面每次都找出剩余马中最快的那匹，那匹就晋级。
在刚晋级的马的组中找出比它的慢一点的顶替其出战来和其他四组中比。这样就能找出第二快的，再次晋级。依次类推

爱疯 · 发表于 2010-12-21 15:18

谢谢阿木！

还是 .... 没明白[em04]

需不需要把题再简化些（数量少些，然后分别编号）？

amulee · 发表于 2010-12-21 15:25

假设A,B,C,D,E代表5个小组。12345代表小组中的名次。
那么前面五场比赛能够在每个小组中确定名次，得到A1,A2,A3,A4,A5;B1,B2,B3,B4,B5.....
第六场。A1,B1,C1,D1,E1出来比赛
        假设A1赢了，很显然，A1是所有马中最快的。所以A1就不用再比了，把A1先放在一边
        那么快的马还剩下B1,C1,D1,E1。这些马是剩下4组中最快的，但都比A1慢点。那么还有哪匹马可以和它们比比呢？
        显然就是A2，A2在开始的小组内是仅次于A1的，也只有A2可能超过B1,C1,D1,E1。
第七场。A2,B1,C1,D1,E1。再找出这里面最快的，那么这匹马就晋级了，不用再比了，放在一边。
        接下来的思考过程如同第六场
。。。。
。。。。
一直到第十场比完，可以找到前5名的马。

这个算法没有充分利用后5场的比赛结果，所以感觉不是最优化的。

爱疯 · 发表于 2010-12-21 15:46

F6ovwUaD.rar (3.7 KB, 下载次数: 3)

amulee · 发表于 2010-12-21 15:59

这个最佳答案由 amulee 给出，感谢 amulee 的回答。

单击隐藏图章

爱疯理解错误

先随便假设一下名次可能可以帮助理解
假设名次是A1,A2,B1,C1,C2

第六场。A1,B1,C1,D1,E1出来比赛
        很显然A1会赢，A1是所有马中最快的。所以A1就不用再比了，把A1先放在一边。

        接下来，我们要找剩余马中最快的。
        现在已知快的马还剩下B1,C1,D1,E1。这些马是剩下B,C,D,E中最快的，但都比A1慢点。
        那么还有哪匹马可以和它们比比呢？
        选B2？B2比B1跑得都慢，怎么和其他组比？同理C、D、E组都不行啊
        那么A2呢？A2比A1慢一点，但是没和B、C、D、E比过，A2说不定能比B1他们快哦。

第七场。A2,B1,C1,D1,E1。
        A2果然不负众望，A2晋级
        再来找剩下马中最快的
        很显然，不能选B2、C2他们，比他们跑得快的B1、C1都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才A组晋级的后面一位。这里再找A组中的A3来比

第八场。A3,B1,C1,D1,E1。
        A3没能得第一，B1跑了第一了，那么B1晋级了。

        再来找剩下马中最快的
        很显然，不能选A4、C2他们，比他们跑得快的A3、C1都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才B组晋级的后面一位。这里再找B组中的B2来比

第九场。A3,B2,C1,D1,E1。
        B2没能得第一，C1跑了第一了，那么C1晋级了。

        再来找剩下马中最快的
        很显然，不能选A4、B3他们，比他们跑得快的A3、B2都还没晋级呢。上去比不可能获得第一。

        当然，这里应该找刚才C组晋级的后面一位。再找C组中的C2来比

第十场。A3,B2,C1,D1,E1。
        C2跑了第一了，那么C2晋级了。

这样就找到了最快的5匹马

从第六场开始，不断找最快的，然后将最快的晋级放一边，再到剩下的马中找最快的。

爱疯 · 发表于 2010-12-21 16:27

名次	A组	B组	C组	D组	E组
第1名	10	20	300	400	500
第2名	25	21	301	401	501
第3名	26	22	302	402	502
第4名	27	23	303	403	503
第5名	28	24	304	404	504

FvvELN9g.rar (3.98 KB, 下载次数: 0)

爱疯 · 发表于 2010-12-21 16:45

mj0XE9fU.rar (4.04 KB, 下载次数: 1)

		自动登录	找回密码
密码			注册