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

这个是google的一个面试题，觉得挺有意思的，问题是这样的：一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。[也许至少会产生误解，换成最少，就是考虑你的算法的最坏情况下]

以上就是这个问题。其实拿起笔来，仔细看看倒是不是很难。  (后来仔细想了想，其实并不简单)

如果推而广之，有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马。

在CSDN上看到另外一个题，http://topic.csdn.net/u/20081017/14/826303de-1871-4e50-89e8-47ed56f49acc.html
实际上就是把N换成256， M换成2， Y换成3
-----
另外有个朋友提出的描述方法浅显易懂，反正25匹马要分5组的，大家在下列统一的马匹归类下讨论比较容易

前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

第6轮目前比较统一的做法是让 每个组的第一，即A1,B1,C1,D1, E1比一场，假设 A1>B1>C1>D1>E1 那么这个时候可以淘汰一些马了，淘汰的用--表示，如下:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --

分歧就在第7轮了，我也没想清楚最佳方法，我就不在第一个帖子说了。

评论

82 楼 lilili0229 2008-11-12  

这样跑：
也是分五组，各小组先决胜出最快的，然后记录下各组跑的快慢次序，假设如下这样
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场

81 楼 qufulin 2008-11-12  

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

80 楼 nciky1984 2008-11-12  

stormspire 写道

nciky1984 写道

以下是我的思路- -

首先前6次比赛按照楼主的思路..

然后画出结果表格。如附件1的图1，表格里的数字代表这批马可能跑到的最好排名

根据前6场的比赛结果我们可以很容易得到以下3条结果：

从横向方向来看：右边那匹马的可能的最好成绩是左边一匹最好成绩+1，比如A2可能的最好成绩是第2，则A3的可能最好成绩是第3

从纵向方向上来看：在第1列上，下面那匹马的最好成绩是是上面那匹马的最好成绩+1，比如B1可能的最好成绩是第2，则C1可能的最好成绩是第3

表格中数字唯一：即代表这批马的排名...比如A1是第一。为了方便起见，标明为绿色

下面是第7轮的比赛算法..
选择没有确定排名的，数字最小的5匹马进行比赛，如附件1中图1的红色部分标明的5匹马..把排名填写在表中。因为第一名已经确认，所以从第2名开始排列

假设排名结果如附件1图2这样的结果（紫色部分）。

根据前面得到的3个条件，更新表格中马匹的最好成绩...见附件1图3。

很显然，最好成绩在第6名以后的可以直接淘汰..

然后重复以上循环即可得出跑得最快的5匹马...

最少需要8轮，即附件1所示那种情况。

以上算法可以扩展到有N匹马，M个赛道中...

但是题目问的是 至少 需要多少场比赛...也就是说运气最好的情况下可以确认前5的比赛场数...

所以答案得靠...凑

首先每匹马都得至少进行一场比赛，所以前5场比赛没有悬念...

关键在于第6场...将A5和B1，C1，D1，E1拉一起比...
如果运气够好，A5第一胜出...
排名就是A1，A2，A3，A4，A5。
最少需要 6场 比赛就能够确定名次..

表格中最后一个图没法在一轮就能决定最后的两名

楼主给出的题目有歧义

当时题目问的是至少，不是至多...

我对至少的理解是：算法在最好的情况下所能得出的场次

79 楼 jiazhigang 2008-11-11  

applefeng_52 写道

计时器是干毛用的？科学的发明不利用是落后还是返古？。。。

你的话引出了一个更深入的问题

78 楼 applefeng_52 2008-11-11  

计时器是干毛用的？科学的发明不利用是落后还是返古？。。。

77 楼 stormspire 2008-11-11  

nciky1984 写道

以下是我的思路- -

首先前6次比赛按照楼主的思路..

然后画出结果表格。如附件1的图1，表格里的数字代表这批马可能跑到的最好排名

根据前6场的比赛结果我们可以很容易得到以下3条结果：

从横向方向来看：右边那匹马的可能的最好成绩是左边一匹最好成绩+1，比如A2可能的最好成绩是第2，则A3的可能最好成绩是第3

从纵向方向上来看：在第1列上，下面那匹马的最好成绩是是上面那匹马的最好成绩+1，比如B1可能的最好成绩是第2，则C1可能的最好成绩是第3

表格中数字唯一：即代表这批马的排名...比如A1是第一。为了方便起见，标明为绿色

下面是第7轮的比赛算法..
选择没有确定排名的，数字最小的5匹马进行比赛，如附件1中图1的红色部分标明的5匹马..把排名填写在表中。因为第一名已经确认，所以从第2名开始排列

假设排名结果如附件1图2这样的结果（紫色部分）。

根据前面得到的3个条件，更新表格中马匹的最好成绩...见附件1图3。

很显然，最好成绩在第6名以后的可以直接淘汰..

然后重复以上循环即可得出跑得最快的5匹马...

最少需要8轮，即附件1所示那种情况。

以上算法可以扩展到有N匹马，M个赛道中...

但是题目问的是 至少 需要多少场比赛...也就是说运气最好的情况下可以确认前5的比赛场数...

所以答案得靠...凑

首先每匹马都得至少进行一场比赛，所以前5场比赛没有悬念...

关键在于第6场...将A5和B1，C1，D1，E1拉一起比...
如果运气够好，A5第一胜出...
排名就是A1，A2，A3，A4，A5。
最少需要 6场 比赛就能够确定名次..

表格中最后一个图没法在一轮就能决定最后的两名

76 楼 stormspire 2008-11-11  

blurm 写道

stormspire 写道

我也并不知道标准答案，下面是我的思路:
第6轮完毕是
A组 A1,A2,A3,A4,A5
B组 B1,B2,B3,B4,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--
假设 A1>B1>C1>D1>E1

第二名没有什么悬念，肯定是A2,B1中的一个
第三名也没有悬念，是A2,A3,B1,B2,C1中的一个

所以拿A2,B1,A3,B2,C1 比一轮 （第7轮），那么可以得出第2、3名，并且可以淘汰第5名，以及第5名所在的其余成员
下面的就麻烦了。

1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以
2. 如果A2,B1是前两名，再比第8轮也可以得出结果。我就不仔细分析了。
3. 最复杂的情况就是B1和C1是前两名，
   3.1 如果A3是最后一名，剩下
A组 A1,A2,--,--,--
B组 B1,B2,B3,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  这里就有A2,B2,B3,C2,C3,D1,D2,E1 8匹马来竞争最后的2个名额. A2,B2比过，所以
第4名可以在 A2,B2中的快者，然后加上C2,D1中比出来，假设我第8轮只用3匹马比，可以得出第4，而且可以淘汰第3名以及比第3名慢的马。所以第8轮可以至少淘汰2匹，加上选出来的第4，那么第9轮只剩下5匹马了，可以得出结果。

  3.2 如果B2是最后一名，剩下
A组 A1,A2,A3,--,--
B组 B1,--,--,--,--
C组 C1,C2,C3,--,--
D组 D1,D2,--,--,--
E组 E1,--,--,--,--

  可以发现这个图比上面的还简单，所以不会比3.1多

综上，觉得至少应该比9轮

关于第七轮的分析:
1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以

如何能够确定B3,B4就在前五名开外呢?

因为现在是A1,A2,A3是前3名，然后还有两个名额，如果B3在前5名，然后B1>B2>B3,所以B1,B2也得在前5名，这样就不符合两个名额的推理了。

75 楼 liudaoru 2008-11-08  

“至少”的话就相当简单了，五队分类赛排出名次，然后五队的第一再赛一次，排出队列的名次，这时第一队的第一一定是第一了。
把第二队的第一放到第一队，我们可以保证第二队的第一一定是后面几队中最快的。第二队的第一和第一队的其他马比，如果是第四或者第五，那么名次就一定出来了。。。

所以至少是七次！

74 楼 wfbshiwo 2008-11-07  

最多21场吧
先随便挑五个赛，的、挑出最慢的来，跟另外四个比，如果在比那四个都慢就需要比把那四个放到原来的组去比，每次裁掉一个最慢的，这样理论上最慢的话要21场
最快就是第一次选出的五匹马就是前五名的话只需6次就行了

73 楼 liouxiao 2008-11-07  

支持zhangkaitao，最撞大运的方法，在概率上6场是可能选出最快的5匹马

72 楼 chencao 2008-11-07  

<p>呃。。。</p>
<p> </p>

71 楼 our651 2008-11-07  

这个比较不好说,要是我去考试.我就会写6场
根据题目的描述来说,没有限制方法,从广义考虑,我们有方法可以在6场中分出胜负

分5组
1>每组第一名跑到目的地时,目测每匹马的身位差别,心记之
2>把5个第一拉来跑一场,同样目测每匹马的身位差别,心记之
3>以某匹马为标准值,心算每匹马的权值,列出前5
4>OK

70 楼 magic650 2008-11-07  

blurm 写道

1，先赛五场
2，第六场，每场的第一名赛一次，此次的第一名拿出去
3，第七场，第六场第一名在（1）里队伍的第二名顶上来再加上第六场的剩下四名比赛，此次的第一名再拿出去。
4，第七场的第一名在（1）里的下一个名次的马继续顶上来，和剩下的四匹马比赛

这样算下来得赛10场，不知道对不对

我表述的太烂了。。。sigh，自己寒一个

我觉这个差不多
借前面的形式
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
快<===慢
第6场：拿A1 B1 C1 D1 E1 来比，可以得到最快的一匹，这个没问题了，在第6场假设是A1最快，E1最慢
第7场：用A2 B1 C1 D1 E1 来比（这里这5匹应该是剩下的最快的5匹了），如果A2最快，那么结果出来了，最快的5匹就是A1 A2 A3 A4 A5,如果C1最快，就拿剩下的A2 B1 C2 D1 E1再去比第8场（B1最快，就用A2 B2 C1 D1 E1比第8场）
思想就是每次都拿A[] B[] C[] D[] E[] 中最快一个来比

。。。感觉结果是最快7场，最慢10场。。。

69 楼 sys53 2008-11-07  

至少8场！
多种情况都可以演算。
本人用最笨的反推法。

68 楼 zhangqidi 2008-11-06  

讨论那么多...我觉得最少7轮,最多8轮

所谓最少7轮,就是数据顺序凑巧,到第七轮的时候就ok了
任何数据顺序,到第8轮都可以出结果

当然,以上的最多最少都是足够"科学"的比较方法上而言,如果愿意,设计一个至少50轮出结果的方法也是可能的

67 楼 xiaocheng 2008-11-06  

前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

第6轮目前比较统一的做法是让 每个组的第一，即A1,B1,C1,D1, E1比一场，假设 A1>B1>C1>D1>E1 那么这个时候可以淘汰一些马了，淘汰的用--表示，如下:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --

第7轮 A5 vs B1 假设A5>B1 则结束比赛 A1>A2>A3>A4>A4
 
题目都说了，最少！，那么当然我们向最好的方面假设啦！

66 楼 xuyoumi 2008-11-05  

liuxinqing 写道

xuyoumi 写道

至少，就是 保证一定可以得出前五名，而场数要最少。

而这个题我觉得 8 场是一定可以得出前五名的，

七场不一定可以得出来。所以它不是至少要的场数。不知道理解得对不对。

不是这样地，因为选的马都是随机的，第六场最快的A组中的马也有可能比最慢的E队中的马慢.

马是稳定的，第六场最快是五匹各队第一的马比，所以第六场最快快的马肯定是所有马中最快的啦，又怎么会比E队中的马慢呢？ 第六场可以得出第一名，第七场肯定可以得出第二名和第三名。第八场肯定可以得出第四名和第五名，所以8场够了。我在前面分析过原因。

FocusSpeed 写道

10轮 先五场 取出每场的第一名
这5匹马赛一场 确定1-5，取出第一名a
然后拿a队第二名跟剩下的4名组成一队比赛，取出第一名b
然后拿b所在队紧挨b的后一名跟上面的4匹马比赛，取出第一名c，
然后拿c所在队紧挨c的后一名跟上面的4匹马比赛，取出第一名d，
然后拿d所在队紧挨d的后一名跟上面的4匹马比赛，取出第一名e，
ok 5匹最快的马出来了

10轮 太多，关键在于“a队第二名跟剩下的4名组成一队比赛，取出第一名b”，因为马是稳定的，“剩下的4名”再比没有多大的意义，结果基本上等于“a队第二名跟剩下的4名中最快的比取快一点的”两赛道够了，我们应该利用第七场还有三道得出更多的信息才能更快得出结论。不知道这样是不是会更好呢？

65 楼 FocusSpeed 2008-11-05  

10轮 先五场 取出每场的第一名
这5匹马赛一场 确定1-5，取出第一名a
然后拿a队第二名跟剩下的4名组成一队比赛，取出第一名b
然后拿b所在队紧挨b的后一名跟上面的4匹马比赛，取出第一名c，
然后拿c所在队紧挨c的后一名跟上面的4匹马比赛，取出第一名d，
然后拿d所在队紧挨d的后一名跟上面的4匹马比赛，取出第一名e，
ok 5匹最快的马出来了

64 楼 liuxinqing 2008-11-05  

xuyoumi 写道

至少，就是 保证一定可以得出前五名，而场数要最少。

而这个题我觉得 8 场是一定可以得出前五名的，

七场不一定可以得出来。所以它不是至少要的场数。不知道理解得对不对。

不是这样地，因为选的马都是随机的，第六场最快的A组中的马也有可能比最慢的E队中的马慢.

63 楼 xuyoumi 2008-11-05  

至少，就是 保证一定可以得出前五名，而场数要最少。

而这个题我觉得 8 场是一定可以得出前五名的，

七场不一定可以得出来。所以它不是至少要的场数。不知道理解得对不对。