Browsed by
标签:Puzzle

面试题:赛马问题

面试题:赛马问题

据说,这是Google的面试题。面试题目如下:

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

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

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (18 人打了分,平均分: 4.33 )
Loading...