他遇到的一个经典题目（转）

pcl2004_27 · 发表于 2005-1-9 19:33:42

一个朋友经过n轮面试去上海微软了。

他遇到的一个经典题目：

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

pcl2004_27 · 发表于 2005-1-9 19:42:19

给个答案：
先将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:53

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

依伊卜舍 · 发表于 2005-1-10 08:54:40

对呀，我也有楼上的疑问。

joriqian · 发表于 2005-1-10 09:53:32

能不能说明白一点呀。

pcl2004_27 · 发表于 2005-1-10 10:03:06

我只是把人家给的答案拿出来，让大家自己动动脑，没有说这个答案就是对的

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

Nio · 发表于 2005-1-10 10:19:56

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:04

楼主，你这个答案是正确答案么？

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

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

lucifer · 发表于 2005-1-11 09:11:23

疑惑中

冰河 · 发表于 2005-1-11 09:41:54

赌一把 · 发表于 2005-1-21 13:18:32

我是想不出来了,累,懒的想

beiyue · 发表于 2005-1-21 16:39:56

Nio · 发表于 2005-1-21 18:36:01

只要9次比赛就可以了哟:p

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

songfun · 发表于 2005-1-21 22:18:26

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

songfun · 发表于 2005-1-21 22:27:00

知道为什么只要两次么？嗯，答案下期公布。。。呵呵

小子不信邪 · 发表于 2005-1-24 11:49:57

拿6个，各3个，剩下两个。对3个的两组进行比较
1，如果两边一样重，那么对剩下的比较；
2，如果两边不一样重，对重的那边进行分组，各取一个进行比较，结果就出来了。

songfun · 发表于 2005-1-24 16:33:59

没错，呵呵，正如楼上说的。

owen.wang · 发表于 2005-2-3 16:58:31

好难啊，这样的题目，面试的时候一定是做不出来的。

adamstao · 发表于 2005-2-17 12:07:54

shiling · 发表于 2005-2-17 13:37:14

我的天那，我就是计算不出来

		自动登录	找回密码
密码			(注-册)加入51Testing

他遇到的一个经典题目（转）

相关帖子

把你们各自的答案再解释清楚一点好吗?特别是楼主的答案!!!

不是吧，楼上的斑竹！

两次。

我觉得是8次

站长推荐 /1