据说,这是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 B5C组 C1 C2 C3 C4 C5D组 D1 D2 D3 D4 D5E组 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,那么公式是什么呢?
期待你的答案!
(转载本站文章请注明作者和出处 ,请勿用于任何商业用途)
———————————————————————————————————————
#43的解答:
好早听说过这个题目,自习思考过方法,尽可能的让每次赛马后淘汰最多的马(这个思想很好)
和楼主最初一样,先分成5组,每组5匹,编号ABCDE,组内赛完后,共计五场A1 B1 C1 D1 E1A2 B2 C2 D2 E2A3 B3 C3 D3 E3A4 B4 C4 D4 E4A5 B5 C5 D5 E5第六场若取每组的第一比的话,最终可以淘汰4 + 3 + 2 + 1 = 10 (+ 1选出)若取每组的第二比的话,最终可以淘汰4 + 4 + 4 + 2 = 14 (+ 1选出)若取每组的第三比的话,最终可以淘汰3 + 3 + 3 + 3 = 12… 后面肯定更少所以第六场取每组第二比最佳,不妨设第六场顺序为A2 > B2 > C2 > D2 > E2。这样第六场后剩余的马有10匹,只需选出前四即可 B1 C1 D1 E1A2 B2A3 B3A4A5第七场还是按照上面的原则,尽可能的淘汰最多的马选择A3 B2 C1 D1 E1比赛,若A3 B2为前两名,那么这四匹马(前五)就找出了,为A2 A3 B1 B2,只用了7场若A3为前两名,B2不为前两名,那么就有三匹马(前五)找出了A2 A3 (C1或D1或E1)淘汰B2 B3,最后就只剩五匹马,所以只需要加赛一次,共计8场若A3 B2都不为前两名,A3 A4 A5 B2 B3都可以淘汰,最后A2 B1 C1 D1 E1赛一场就可以了。所以只需要8场。综合三种情况,最少需要8场
——————————————————————————————————————
第六轮使用最大值进行比较的后续具体解答:
前5次大家都一样,排序后如下A1,A2,A3,A4,A5B1,B2,B3,B4,B5C1,C2,C3,C4,C5D1,D2,D3,D4,D5E1,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一起即为前52、若第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次赛马可得答案。