[Google/腾讯]赛马

总共25匹马，每次只能5匹一起跑，那么最少跑几次才能比出第1、2、3名？
不得使用timer之类的东西……只能靠一个场上跑来分名次。

9次。。。
不知道对不对：
先分5组，跑5次，每次取前3名出来：分别为1.1, 1.2, 1.3, ..., 5.1, 5.2, 5.3
然后所有第一名分一组(a)，第二名分一组(b)，第三名分一组(c)，跑3次：分别为a.1, a.2, a.3, ..., c.1, c.2, c.3
然后发现a.1一定是第一名
c组只有c.1才可能是前三（因为在第一轮分五组的时候，c.1是第三名，肯定有两个比他快）
同理，b组只有b.1, b.2才有可能
a组a.2, a.3都有可能
所以把 a.2, a.3, b.1, b.2, c.1抓出来再跑一次

一共 5 + 3 + 1 = 9

补充：b2跑不跑两可哈~~~~
至少a1,a2,b1快过它

回复 1# zach
之前看过一个解答，好像是7次。先赛五次，然后五个第一名再赛一次，假如结果是a1>b1>c1>d1>e1。目前共六次。
这样组d组e就全被淘汰了，身下的可能是前三的有：a1,a2,a3,b1,b2,c1。其中a1肯定是。所以后五个再赛一次取前两名即可。

   

LSV5

我做错没
1.
5个一组先跑5组，分别叫组1,2,3,4,5
跑出来的名次分别是ABCDE

2. A1, A2, A3, A4, A5比赛一次(6th)，第一就出来了, wlg假定是A1

3. B1, A2, A3, A4, A5 比赛一次(7th)，第二就出来了，无论是谁，

4. 最后一次比赛(8th)，由同组的下一个名次顶替上去，第三就出来了
假设第二名是B1, 那么 B2, A2, A3, A4, A5 比赛
假设第二名是A2, 那么 B2, B2, A3, A4, A5 比赛
etc

4楼v5

回复 7# 小K
惭愧，我自己想的时候只想到了8次还是9次的方法，那个是网上看别人说的


   

回复  zach
之前看过一个解答，好像是7次。先赛五次，然后五个第一名再赛一次，假如结果是a1>b1>c1>d1>e1 ...
darksteel 发表于 2011-4-20 10:56

赞解法！

4L是我目前知道的最好的办法。

下面是截至目前的总结：
10次、9次都是比较简单但是不好的算法
K姐8次的答案很常见，但是不是最好。因为在比完6次以后没有淘汰那些肯定进不了前三的马
7次bingo～