面试被问了一个问题,愚蠢的脑袋在那么短的时间里没有想起来,问题如下:
条件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轮
不知各位还有什么不同意见,欢迎评论 |