51Testing软件测试论坛

 找回密码
 (注-册)加入51Testing

QQ登录

只需一步,快速开始

微信登录,快人一步

手机号码,快捷登录

查看: 2742|回复: 10
打印 上一主题 下一主题

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

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2009-2-18 12:37:45 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
面试被问了一个问题,愚蠢的脑袋在那么短的时间里没有想起来,问题如下:

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

不知各位还有什么不同意见,欢迎评论
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏
回复

使用道具 举报

  • TA的每日心情
    慵懒
    2020-8-11 08:18
  • 签到天数: 114 天

    连续签到: 1 天

    [LV.6]测试旅长

    2#
    发表于 2009-2-19 00:16:32 | 只看该作者
    偶觉得这个就是个归并排序亚~
    不过最终不需要完整的序列就不需要那么复杂了。。。

    其实只需要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轮
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    3#
    发表于 2009-2-25 21:15:30 | 只看该作者
    需要这么麻烦嘛。想简单点不行?先每匹一个号码,1跑道1匹。计时。5次不就可以了?
    或者。跑道很宽。1次就可以。前3个。不就是了?
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    4#
    发表于 2009-3-2 15:52:36 | 只看该作者
    7轮。

    3楼的想象力很丰富
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    5#
    发表于 2009-3-2 19:41:51 | 只看该作者
    同意三楼的意见,所有马只跑一次,结果不就出来了吗?
    跑那么多轮~~马的发挥会受影响的哦~~
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    6#
    发表于 2009-3-3 19:21:01 | 只看该作者
    如果是计时的话,一次不就够了?!

    [ 本帖最后由 wendy42 于 2009-3-3 19:27 编辑 ]
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    7#
    发表于 2009-3-3 21:14:12 | 只看该作者
    一次,同意3楼
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    8#
    发表于 2009-3-3 23:38:05 | 只看该作者
    同路之人还不少~~
    回复 支持 反对

    使用道具 举报

    该用户从未签到

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

    [ 本帖最后由 lanlanlan 于 2009-3-3 23:40 编辑 ]
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    10#
     楼主| 发表于 2009-3-5 16:32:50 | 只看该作者
    原来只要7轮,让我在想想
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    11#
     楼主| 发表于 2009-3-5 16:39:23 | 只看该作者
    之前没有看过归并排序,看了2楼的分析,才觉得我原有的分析又浪费了 5个第一名一起跑的结果 这一资源....
    回复 支持 反对

    使用道具 举报

    本版积分规则

    关闭

    站长推荐上一条 /1 下一条

    小黑屋|手机版|Archiver|51Testing软件测试网 ( 沪ICP备05003035号 关于我们

    GMT+8, 2024-11-22 19:20 , Processed in 0.074710 second(s), 30 queries .

    Powered by Discuz! X3.2

    © 2001-2024 Comsenz Inc.

    快速回复 返回顶部 返回列表