他遇到的一个经典题目(转)
一个朋友经过n轮面试去上海微软了。他遇到的一个经典题目:
有25匹赛马,每次赛只能有5匹参加,问最少赛几次能找出最快的3匹马,并排出名次。 给个答案:
先将25匹分为3组,分别测试,得到每组最快的各3匹,一共9匹马。
再从9匹中任选5匹比赛,得出前3,淘汰最后2个。
然后从前3中任选一匹(剩2匹),加入9匹剩下的4匹中,组成5匹,比赛,
淘汰最后2匹,得到前3。
再此前3与括号()中的那2匹,组成5匹,比赛,最后得到前3,分出结果。 不是每次赛只能有5匹参加吗?
上面的答案怎么写“先将25匹分为3组,分别测试,得到每组最快的各3匹,一共9匹马”呢? 对呀,我也有楼上的疑问。 能不能说明白一点呀。 我只是把人家给的答案拿出来,让大家自己动动脑,没有说这个答案就是对的
大家可以自己把自己的答案拿出来!提供自己的思路! 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匹,每组第一名用来排名次。 楼主,你这个答案是正确答案么?
——此题的关键在于每次只能有5匹马参加,而每次比赛的前三必须能够参加下一轮比赛。
[ Last edited by Nio on 2005-1-10 at 10:33 ] 疑惑中
把你们各自的答案再解释清楚一点好吗?特别是楼主的答案!!!
我是想不出来了,累,懒的想不是吧,楼上的斑竹!
只要9次比赛就可以了哟:p[ Last edited by Nio on 2005-1-21 at 18:37 ]
两次。
其实微软的绝招就是这几招,有本书叫《微软的选修秘密》,会发现这道题跟另一道极为相似,改头换面一下就出来了。有兴趣可以专门研究研究这些题目的共通之处,所谓一法通万法通。相信不难的。这道题是:
假定你有8个撞球,其中有1个比其他球重,如果只能利用天平来判定哪一个重,请问要找到重的那个球至少要几次?(答案见题目) 知道为什么只要两次么?嗯,答案下期公布。。。呵呵 拿6个,各3个,剩下两个。对3个的两组进行比较
1,如果两边一样重,那么对剩下的比较;
2,如果两边不一样重,对重的那边进行分组,各取一个进行比较,结果就出来了。 没错,呵呵,正如楼上说的。 好难啊,这样的题目,面试的时候一定是做不出来的。
我觉得是8次
我的天那,我就是计算不出来
页:
[1]
2