[Google/腾讯]赛马

能否证明不能用更少次数搞定？

能否证明不能用更少次数搞定？
小K 发表于 2011-4-19 23:18

或者求一下M匹马找前N名的通解？都是很好的引申……

或者求一下M匹马找前N名的通解？都是很好的引申……
zach 发表于 2011-4-20 12:29

那实际上就是n个数有限次分组比较对前m大项进行排序的问题

可以推广成并行算法？

那实际上就是n个数有限次分组比较对前m大项进行排序的问题

可以推广成并行算法？
wwtpcsuper 发表于 2011-4-19 23:33

赞总结

总共6次：先跑一组，以决出最快的那匹马A为参照物，以及其余四匹在跑A到达终点时与它的距离。后面每次都用A以及四匹未跑过的构成一组，只需要再跑5次，记录每次A到达终点时与A的距离即可决出25匹马的排名。
PS：在Quora上看到的另类答案。。。

应该是7次吧 上面那个6次的似乎违背了题目的原则 只能靠一个场上跑来分名次

同意楼上的

我也觉得是7次：

第一步：把25匹马分成5组，分别记为g1-g5，赛5次；
第二步（寻找第一名）：用5组里的第一名组成一组，记为g6，赛一次，获得25匹马中的第一名；
第三步（寻找第二三名）：新建一个组g7。g6中的最后一名不可能是25匹马中的第二或第三，所以仅仅将g6中的第二三四名加入g7中；设第二步中找到的第一名来自gi组，那么gi组里的第二名和第三名也可能是25匹马里的第二名和第三名，将它们也加入g7。g7赛一次，第一和第一即为25匹马中的第二和第三。

共7次。