加载中…
个人资料
老徐
老徐
  • 博客等级:
  • 博客积分:0
  • 博客访问:837,584
  • 关注人气:157
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

面试题:赛马问题

(2012-06-03 13:11:29)
标签:

面试

赛马

it

分类: Algorithm/DateStructure

有25匹马,速度都不同,但每匹马的速度都是定值。现在只有5条赛道,无法计时,即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名?百度2008年面试题

每匹马都至少要有一次参赛的机会,所以25匹马分成5组,一开始的这5场比赛是免不了的。接下来要找冠军也很容易,每一组的冠军在一起赛一场就行了(第6 场)。最后就是要找第2和第3名。我们按照第6场比赛中得到的名次依次把它们在前5场比赛中所在的组命名为A、B、C、D、E。即:A组的冠军是第6场的 第1名,B组的冠军是第6场的第2名……每一组的5匹马按照他们已经赛出的成绩从快到慢编号:

A组:1,23,4,5
B组:12,3,4,5
C组:1,2,3,4,5
D组:1,2,3,4,5
E组:1,2,3,4,5

从 现在所得到的信息,我们可以知道哪些马已经被排除在3名以外。只要已经能确定有3匹或3匹以上的马比这匹马快,那么它就已经被淘汰了。可以看到,只有上表 中粗体的那5匹马是有可能为2、3名的。即:A组的2、3名;B组的1、2名,C组的第1名。取这5匹马进行第7场比赛,第7场比赛的前两名就是25匹马 中的2、3名。故一共最少要赛7场。

这道题有一些变体,比如64匹马找前4名。方法是一样的,在得出第1名以后寻找后3名的候选竞争者就可以了。

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有