论坛首页 招聘求职论坛

一道Intel的面试题

浏览 9412 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2007-10-08  
题目:
有25匹马,一个5道的赛马场,最少比赛几次,能把这25匹马中的1,2,3名找出来,并排出1,2,3名?如何组织每次比赛?
马可以重复赛,不考虑疲倦影响速度等其他问题。


思路:
首先肯定,25匹要分组赛。
最容易掉入,也最容易识别的陷阱就是:
5匹一组,赛5次,然后每组第一名再赛一次,总共六次,就ok了。这样的问题就在于又可能某组的第二名比其他4组的第一名都快。进而想到最坏的 可能就是,分组的时候把真正的前三名分到同一组了。
问题的关键变成了第6次以后应该怎么挑选再赛的马

5分钟左右,应该就能想到下面的正确思路。
前6次就按照刚才的赛法,5次小组赛,一次各小组第一名赛,然后按各小组第一名在第六次比赛中的名次给各组编号。
第六次跑第一那匹马所在的组就是第一组。
这样,首先确定了真正的第一名,就是第一组第一名,下面要找真正的第二名和第三名。
想一下,4,5组所有马匹已经不可能了,直接排除
下面在1组4匹,2,3各5匹共14匹马力用最少的比赛次数决定真正的2,3名
真正可能来竞争这个2,3名的,也只有第一组2,3名,第二组1,2名,和第三组第1名。仔细想想就明白了
所以只要挑这5匹出来,再赛一次,取前两名
总共7次,就排出了25匹中的前三名
题目是不难
但是要能在面试的环境下快速的整理思路,还是有点难度的:)
  • 描述: description
  • 大小: 9.9 KB
   发表时间:2007-10-09  
5次。
0 请登录后投票
   发表时间:2007-10-09  
aiut 写道
5次。

同意,题目本来就不严谨
0 请登录后投票
   发表时间:2007-10-09  
realreal2000 写道
aiut 写道
5次。

同意,题目本来就不严谨
需求都是不严谨的。
PS:用秒表。。。
0 请登录后投票
   发表时间:2007-10-09  
抛出异常的爱 写道
realreal2000 写道
aiut 写道
5次。

同意,题目本来就不严谨
需求都是不严谨的。
PS:用秒表。。。

这种题目明显是类似与基于比较的排序如何确定前3大元素,不过唯一的区别就是每次可以5个元素参与一次排出顺序,算一次比较而已。
ps:如果赛马场只有2个道,那么这就是一个经典的计算机排序问题了。
0 请登录后投票
   发表时间:2007-10-09  
这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三
0 请登录后投票
   发表时间:2007-10-09  
realreal2000 写道
这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三


不能说永远,至少现在不能,
0 请登录后投票
   发表时间:2007-10-09  
realreal2000 写道
realreal2000 写道
这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三


不能说永远,至少现在不能,
汗。。。
可预见比赛成绩的话有谁去看比赛呢?
0 请登录后投票
   发表时间:2007-10-09  
aiut 写道
5次。

5次怎么排?望赐教。。
另外,本身就是道面试题,肯定不会考虑什么秒表之类的因素了
其他还有什么不严谨的方面,我真没怎么看出来。
0 请登录后投票
   发表时间:2007-10-09  
lixiao 写道
aiut 写道
5次。

5次怎么排?望赐教。。
另外,本身就是道面试题,肯定不会考虑什么秒表之类的因素了
其他还有什么不严谨的方面,我真没怎么看出来。

你用的方式已经是最简单的了
不过没看出来与程序有什么关系,顶多是个脑筋急转弯的题了。
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics