讨论一个算法，GOOGLE的一个面试题

有些对问题的理解有点问题, 题目问的是最少需要赛多少次, 那就是说最乐观的情况下的某种算法的结果, 也就是说运气最好并且可以肯定得到结果, 我可以说其中的一个算法: 前五次比赛都一样分组, 在第六次比赛时随机选中其中一组的第二名和其它四组比赛并且恰好它跑到了最后一名, 这时结果就出来了最快的马就是每组的第一名, 也许这个算法很烂, 但是在最乐观情况下六次就可以得到最快的五匹马.

这样跑：
也是分五组，各小组先决胜出最快的，然后记录下各组跑的快慢次序，假设如下这样
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）胜出，然后由他所在的那个组的第二名（假设A2）补上与B1,C1,D1,E1比赛，然后决出第一名再由它所在的队伍的第二名补上......依次比下去直到胜出5名比赛结束。
这样就可以选出跑的最快的5匹马了，一共需要11场

分析结果漏洞百出。

其实赛5场就够了。弄个秒表计下。（玩笑）

跑完6次后的结果（A到E、1到5）
A1 B1 C1 D1 E1
A2 B2 C2 D2 E2
A3 B3 C3 D3 E3
A4 B4 C4 D4 E4
A5 B5 C5 D5 E5
然后可以pass掉将近一半的马
  B1 C1 D1 E1
A2 B2 C2 D2
A3 B3 C3
A4 B4
A5
为什么可以pass掉？比如C4，肯定比C4快的有C1C2C3A1B1，超过5匹，其它的自己去想
A1肯定最快也去掉了
第7场比较A2 B1 A3 B2 C1(斜线)
可以确定前3
第8场是第6场的后3、4名加上 第6场的第2名后面的3匹

最多8场

楼上Good Job！

然后第六场每对最快的马比。这一场过后，将跑得最慢的那匹马的所在的队伍整队都淘汰掉（无需比了，最快的都跑得比别人慢）
这个不一定吧。
可能跑的最慢的也比最快的队伍中第2名的要快

我的算法是
先跑第1轮
那么结果是
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

上面是第1轮跑出的结果，跑第2轮的时候得出的结果是：
找出第2轮跑的最慢的马，然后跟第2梯队进行比赛。
我们假设跑的最慢的是
Horse slow = getSlowHorse();
Horse secondFast = getSecondFast(); // 获取第2梯队跑的最慢的马
slow 跟secondFast 进行比赛如果slow比secondFast 快，那么结果就出来了。7场就可以出结果了，5+1+1；
如果慢的话，则淘汰slow的那5匹马。
如此循环，直到筛选出最快的5匹马，最后的情况就是全面进行遍历筛选了。
剩下，不好算啊。
呵呵。复杂。

不过话又说回来，google的题，应该是发散的。
因为在赛场上，什么结果都会出现，真实客观的来说，没法得出结果。
如果全部一起跑哪还知道，没匹马跑出的速度在每场比赛得出的速度都不一样

一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。

假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。[也许至少会产生误解，换成最少，就是考虑你的算法的最坏情况下]
-------------------------------
1. 不考虑算法:
最少应该是在6场,
前五场是没问题的,第六场是A5和B1,C1,D1,E1跑一场,A5第一,第六场出结果.

2. 考虑算法:

前五场是一样的,第六场:A2,B2,C2,D2,E2跑一场.
同样也可以得出A2>B2>C2>D2>E2的结果;
最后的筛选得出有机会的马为:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3
C组 C1
D组 D1
E组 E1

待续......

想想应该最多9轮：
前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

第六轮，各组的第3名比(粗体表示)，那么非第一名所在组的第3、4、5名均被淘汰（加删除线），理由很简单，如果B3在前5名的话，比其快的还有A1、A2、A3 B2 B3，再加上自己已经6匹，不可能：

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

 

第七轮，上一轮跑第1名的组再次用该组的第3名A3和其它组的第二名比，结果可能以下几种，最坏的情况是第一种，仅淘汰3匹（淘汰分析原因同上），下一轮以第一种情况为例说明，其它情况更好只会更少轮数

A组 A1 A2 A3 A4 A5 
B组      B1 B2 
C组     C1 C2  
D组     D1 D2  
E组     E1 E2  

 

 
B组      B1 B2 

A组 A1 A2 A3 A4 A5
C组     C1 C2  
D组     D1 D2  
E组     E1 E2  

 

B组      B1 B2 
C组     C1 C2  

A组 A1 A2 A3 A4 A5 
D组     D1 D2  
E组     E1 E2  

 

B组      B1 B2 
C组     C1 C2  

D组     D1 D2  

A组 A1 A2 A3 A4 A5 
E组     E1 E2  

 

B组      B1 B2 
C组     C1 C2  

D组     D1 D2  

E组     E1 E2  

A组 A1 A2 A3 A4 A5 

 

第八轮，还用最快的一组的第3名和其它组的第一名比，情况可能如下，第一种情况最坏，还剩下7个，第5种情况次之，科还剩下6个，其它三种情况仅剩下5个，结果已确定，下一轮以第一种情况为例讨论：

A组 A1 A2 A3 A4 A5 
B组           B1  
C组          C1   
D组          D1   
E组          E1  

 

B组           B1  

A组 A1 A2 A3 A4 A5 
C组          C1   
D组          D1   
E组          E1  

 

B组           B1  

C组          C1   

A组 A1 A2 A3 A4 A5 
D组          D1   
E组          E1  

 

B组           B1  

C组          C1  

D组          D1   

A组 A1 A2 A3 A4 A5 
E组          E1  

 

B组           B1  

C组          C1  

D组          D1   

E组          E1  

A组 A1 A2 A3 A4 A5 

 

第九轮，前轮第一名的组的前3名必是前五名，仅需要对其它4匹马比较，再取前两名即可确定最后结果

 

A组 A1 A2 A3 A4 A5 
B组           B1  
C组          C1   
D组             
E组           

看到最后，有点失望。如果换成是5000匹马，取最快的2000批，按照上面列位的穷举法... 怎么就没有人把这个算法用算数式表达出来呢？