25匹马的问题--来之六期一小菜

fflastjay

面试被问了一个问题,愚蠢的脑袋在那么短的时间里没有想起来,问题如下:

条件1: 25匹马....

条件2: 5跑道

求: 如何找出跑的快的前3匹马?最少跑几次(比1轮算1次)

答:冥想中...........想一会儿再去baidu..(原来不是时间长短问题,而是脑袋大小问题...)







还是找了baidu.不过没有找到答案,但是给了我重要的提示,估计百度上有些答案也是copy的,废话少说,来了:

步骤1,海选:25匹马分5组,跑5轮,决出每组前3,  要点:只有每组的前3才有可能成为全部马的前3

步骤2 利用步骤1的结果,把每组的第1, 第2,第3名分别组成1组,这样跑3轮, 1名组(第一名组成的小组,下同), 我们取前3, 2名组取前2, 3名组取前1,
要点:1名组的前3有可能成为全部马的前3, 2名组只有前2名才能成为全部马的前3, 因为不要忘记这个小组的特性,它是2名小组,肯定有匹1名组的马排在2名组头马的前面.(有点饶,好好理解), 同样的道理,3名组只取1个.

先在让我们总结下:2步骤共跑了8轮,得到了前6匹马, 而且得到了第一名马,就是1名组的第一,他肯定是第一了,毫无疑问.

所以步骤3:剩下的5匹马在跑1轮,得出前2名即可.



所以一共需要9轮

不知各位还有什么不同意见,欢迎评论

fflastjay

原来只要7轮,让我在想想

fflastjay

之前没有看过归并排序,看了2楼的分析,才觉得我原有的分析又浪费了 5个第一名一起跑的结果 这一资源....