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

选第一名最快的需要6次，

在剩下的马里要决出第二名，的话 直接把第一名所在组的第二名不是，就可以出第二名了，

以此类推

+1+1+1+1

总共是10次

共6场，分组随机性很强，可以把其他组第一名和第一组的第五名比……如果运气好，6场决胜负

看了LS这么多的分析,我觉得至少跑6场,最多跑10场就可以得出前5名

errorr

我觉得是10场
5+1+1+1+1+1=10

前5场决出每队的第一名，后面每一场决出一名

 

一共八场，原理是从第七场之后利用剩余跑道，两个名次比赛一起跑。

 

经过5论比赛每组名次如下

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

 

第六场

a1 b1 c1 d1 e1

假设结果

d1 b1 a1 e1 c1

 

d1为第一名

 

b1是第二名候选,b1比a1, e1和c1都快，不用跟这三个组比了。要比就跟d2比，谁快谁第二

 

b1和d2比第二，如果b1赢，b2和d2以及a1争第三，如果d2赢，b1和d3争第三。既然跑到可以跑5匹马，上面这些组合加起来正巧5匹。一起跑吧。出来结果之后根据结果安排第八场，原理一样，第四名和第五名比赛一起跑。

 

第七场合并一下：b1 vs d2 vs b2 vs a1 vs d3

 

第七场结果1	第七场结果2	第八场安排
b1第二 b2 vs d2 vs a1比第三	b2 第三 d2 > a1	b3 vs d2   vs a1 vs b4 vs d3	前两个比第四，后三个跟前面失败的那个比第五。已经证明a1比d2慢，a1所以不用争第四了
b2 第三 a1 > d2	b3 vs a1   vs d2 vs b4 vs e1
d2 第三
a1 第三
d2第二 b1 vs d3比第三	b1 第三
d3 第三

 

 

算法导论   很经典的书啊  回头有时间再看一看了

这个要是想无差错的计算 貌似只有10次把
比方说
//1:12345
//2:12345
//3:12345
//4:12345
//5:12345
是前5次 5个队的排序 在刨除第一队的NO.1后,将第1队的NO.2提到NO.1的位置 和其他四匹比赛(第七场),然后把这次的NO.1剔除,再将该NO.1的队伍的下一个提前,依次类推.我看很多人都在追求最少,而没注意题目里的至少,这个至少应该包括所有的排列组合情况.

8轮

6轮后 
1  2+ 3+ 4+ 5+
2+ 3+ 4+ 5+
3+ 4+ 5+
4+ 5+
5+

第7轮再拿 2+ 3+的五只
最少能确定 第2 3 名

第8轮就OK了