一个优化的面试题求解

heavensword

有35个马，一个跑道，每次最多只能跑6匹马，不能计时，问如何最快的找出跑得最快的三匹马？
谢谢

tyc611

用淘汰的方法？

heavensword

如何淘汰？说说看啦

ddvv

1、把马分成六组，各组分别比赛，然后选出各组的前3名（保持分组），那么最快的3匹吗将在里面产生。
2、取各组的第1名比赛，优胜的就是35匹马中最快的。
3、取第2步里面优胜马所在组的第2名同其他组的第1名跑，这次优胜的将是35匹马中的次快的。
。。。。。
第4步就不用说了吧，不过不知道是不是最优的方法。。。。

heavensword

这个方法好 只要6＋1＋1＋1 ＝ 9次 就可以了 呵呵

ypxing

如果这种方法可以的话,8次

原帖由 heavensword 于 2007-9-16 20:11 发表
这个方法好 只要6＋1＋1＋1 ＝ 9次 就可以了 呵呵

beyond2004

以前是用天平称东西，现在改跑马了

laputadancer

原帖由 ddvv 于 2007-9-16 15:58 发表
1、把马分成六组，各组分别比赛，然后选出各组的前3名（保持分组），那么最快的3匹吗将在里面产生。
2、取各组的第1名比赛，优胜的就是35匹马中最快的。
3、取第2步里面优胜马所在组的第2名同其他组的第1名跑 ...

我举个反例：如果本该前3的马放在一组的话，按这种算法就不对了吧？

ypxing

1. 6, 6, 6, 6, 6, 5跑6次,决出各组前3名
2.各组第一名跑一次,决出前3名
3.在2步中的1,2,3名所在的组,设为A,B,C
A组第二第三
B组第一第二
C组第一第二
跑一次取前两名

再加上A组的第一

所以8次可以
估计还有更好的办法

原帖由 laputadancer 于 2007-9-17 20:29 发表



我举个反例：如果本该前3的马放在一组的话，按这种算法就不对了吧？

laputadancer

原帖由 ypxing 于 2007-9-17 20:50 发表
1. 6, 6, 6, 6, 6, 5跑6次,决出各组前3名
2.各组第一名跑一次,决出前3名
3.在2步中的1,2,3名所在的组,设为A,B,C
A组第二第三
B组第一第二
C组第一第二
跑一次取前两名

再加上A组的第一

所以8次可以 ...

抱歉我上面那贴考虑不仔细，那个该是对的，最后一步该是胜的那组的下一名继续与其他比吧？
但这里也不够仔细，即第2步中败者组的第2名未必比胜者组的第2或3名差。