51Testing软件测试论坛

标题: 25匹马的问题--来之六期一小菜 [打印本页]

作者: fflastjay 时间: 2009-2-18 12:37
标题: 25匹马的问题--来之六期一小菜
面试被问了一个问题,愚蠢的脑袋在那么短的时间里没有想起来,问题如下:

条件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轮

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

作者: puchonghui 时间: 2009-2-19 00:16
偶觉得这个就是个归并排序亚~
不过最终不需要完整的序列就不需要那么复杂了。。。

其实只需要7轮就行了
假设分为abcde五组
5轮以后按名次得到
a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5

第六轮： a1 b1 c1 d1 e1
假设结果为a1 > b1 > c1 > d1 > e1
显然a1是跑最快的
并且： d1 e1是不可能进入前3的
那么： d2 d3 e2 e3都被淘汰了
另外还有：因为b1 b2 最多成为第二第三名，所以b3 也不可能进入前三；
同理：c2 c3 也不可能进入前三
淘汰掉这些
剩下 a2 a3 b1 b2 c1再跑一轮就够了

所以：最少需要7轮

作者: szflone521 时间: 2009-2-25 21:15
需要这么麻烦嘛。想简单点不行？先每匹一个号码，1跑道1匹。计时。5次不就可以了？
或者。跑道很宽。1次就可以。前3个。不就是了？

作者: livehome2008 时间: 2009-3-2 15:52
7轮。

3楼的想象力很丰富

作者: 木可 时间: 2009-3-2 19:41
同意三楼的意见，所有马只跑一次，结果不就出来了吗？
跑那么多轮~~马的发挥会受影响的哦~~

作者: wendy42 时间: 2009-3-3 19:21
如果是计时的话，一次不就够了？！

[ 本帖最后由 wendy42 于 2009-3-3 19:27 编辑 ]

作者: xy-113 时间: 2009-3-3 21:14
一次，同意3楼

作者: 木可 时间: 2009-3-3 23:38
同路之人还不少~~

作者: lanlanlan 时间: 2009-3-3 23:39
-0- 这个问题我也被问过不过是是36匹马6条跑道的
马是不能编号和进行计时的
这就是纯粹一个考思维的问题 - -。。。不考虑现实中是否会出现这样的情况
2楼的思考方式就是正解~ 当时被问过之后想了好久才想出来。。。
根据当时考官的说法这是一个考逆向思维的问题。。。。

[ 本帖最后由 lanlanlan 于 2009-3-3 23:40 编辑 ]

作者: fflastjay 时间: 2009-3-5 16:32
原来只要7轮,让我在想想

作者: fflastjay 时间: 2009-3-5 16:39
之前没有看过归并排序,看了2楼的分析,才觉得我原有的分析又浪费了 5个第一名一起跑的结果这一资源....

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)