51Testing软件测试论坛

标题: 他遇到的一个经典题目（转） [打印本页]

作者: pcl2004_27 时间: 2005-1-9 19:33
标题: 他遇到的一个经典题目（转）
一个朋友经过n轮面试去上海微软了。

他遇到的一个经典题目：

有25匹赛马，每次赛只能有5匹参加，问最少赛几次能找出最快的3匹马，并排出名次。

作者: pcl2004_27 时间: 2005-1-9 19:42
给个答案：
先将25匹分为3组，分别测试，得到每组最快的各3匹，一共9匹马。
再从9匹中任选5匹比赛，得出前3，淘汰最后2个。
然后从前3中任选一匹（剩2匹），加入9匹剩下的4匹中，组成5匹，比赛，
淘汰最后2匹，得到前3。
再此前3与括号（）中的那2匹，组成5匹，比赛，最后得到前3，分出结果。

作者: wsj112233 时间: 2005-1-9 20:40
不是每次赛只能有5匹参加吗？
上面的答案怎么写“先将25匹分为3组，分别测试，得到每组最快的各3匹，一共9匹马”呢？

作者: 依伊卜舍 时间: 2005-1-10 08:54
对呀，我也有楼上的疑问。

作者: joriqian 时间: 2005-1-10 09:53
能不能说明白一点呀。

作者: pcl2004_27 时间: 2005-1-10 10:03
我只是把人家给的答案拿出来，让大家自己动动脑，没有说这个答案就是对的

大家可以自己把自己的答案拿出来！提供自己的思路!

作者: Nio 时间: 2005-1-10 10:19
25<=3*9：将马分成3组，不过每次参加比赛的还是5匹，参加比赛：5=9-4(暂不参加)
5=3+2(将被淘汰)——3组：第一轮淘汰2*3共6匹。
5=3-2(暂不参加)+4(or 3)——3组：第二轮加上第一轮没参加的4匹,再进行一次淘汰，不过有两组在第一轮进行分组时只有8匹，故此轮只能淘汰4匹(或在第一轮淘汰4匹，第二轮淘汰6匹)。
5=3+2——3组：第三轮加上第二轮没参加的2匹，每组第一名用来排名次。

作者: Nio 时间: 2005-1-10 10:25
楼主，你这个答案是正确答案么？

——此题的关键在于每次只能有5匹马参加，而每次比赛的前三必须能够参加下一轮比赛。

[ Last edited by Nio on 2005-1-10 at 10:33 ]

作者: lucifer 时间: 2005-1-11 09:11
疑惑中

作者: 冰河 时间: 2005-1-11 09:41
标题: 把你们各自的答案再解释清楚一点好吗?特别是楼主的答案!!!

作者: 赌一把 时间: 2005-1-21 13:18
我是想不出来了,累,懒的想

作者: beiyue 时间: 2005-1-21 16:39
标题: 不是吧，楼上的斑竹！

作者: Nio 时间: 2005-1-21 18:36
只要9次比赛就可以了哟:p

[ Last edited by Nio on 2005-1-21 at 18:37 ]

作者: songfun 时间: 2005-1-21 22:18
标题: 两次。
其实微软的绝招就是这几招，有本书叫《微软的选修秘密》，会发现这道题跟另一道极为相似，改头换面一下就出来了。有兴趣可以专门研究研究这些题目的共通之处，所谓一法通万法通。相信不难的。
这道题是：
假定你有8个撞球，其中有1个比其他球重，如果只能利用天平来判定哪一个重，请问要找到重的那个球至少要几次？（答案见题目）

作者: songfun 时间: 2005-1-21 22:27
知道为什么只要两次么？嗯，答案下期公布。。。呵呵

作者: 小子不信邪 时间: 2005-1-24 11:49
拿6个，各3个，剩下两个。对3个的两组进行比较
1，如果两边一样重，那么对剩下的比较；
2，如果两边不一样重，对重的那边进行分组，各取一个进行比较，结果就出来了。

作者: songfun 时间: 2005-1-24 16:33
没错，呵呵，正如楼上说的。

作者: owen.wang 时间: 2005-2-3 16:58
好难啊，这样的题目，面试的时候一定是做不出来的。

作者: adamstao 时间: 2005-2-17 12:07
标题: 我觉得是8次

作者: shiling 时间: 2005-2-17 13:37
我的天那，我就是计算不出来

作者: time 时间: 2005-2-21 14:43
我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

作者: time 时间: 2005-2-21 14:44
我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

作者: time 时间: 2005-2-21 14:45
我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

作者: revolution 时间: 2005-2-21 15:40
我靠

作者: time 时间: 2005-2-21 17:41
不小心发了三遍，sorry

作者: Nio 时间: 2005-2-22 09:58
time:

先分了5 组进行比赛，比赛5次，剩余15匹；
用二叉树原理，比赛1次，去掉两组（6匹），剩余9匹；
‘c组的后两名也可淘汰；b组的最后一名也可以淘汰。’去掉3匹，剩余6匹；去第一名，剩5匹，比赛1次；

Great!!

作者: xinyijiu25 时间: 2005-2-28 10:50
恩好像很有道理的 Great!

作者: lifadonglfd 时间: 2005-3-2 13:17
标题: 哈哈，真的不错啊！是七次！！

作者: xm3525 时间: 2005-3-2 13:37
厉害，7次真不错啊

作者: zero零 时间: 2012-2-20 16:40
最简单的两次：25匹马，分5组，每组取第一名，再比下得出前三；

不过这个遗漏性太大了，可能第一组的第二名优于其他组的第一名哇。

作者: 朱小燕0616 时间: 2012-3-1 13:54
太厉害了，使用二叉树进行排除

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