一道Intel的面试题

题目：
有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匹中的前三名
题目是不难
但是要能在面试的环境下快速的整理思路，还是有点难度的：）

评论

14 楼 imjl 2007-12-14  

有点不明白，为什么不说个比较实际的问题，而非弄个抽象问题，让人对问题不明或者理解错误。

13 楼 keenvi 2007-12-13  

这样的问题
面试主考官可能考的是你的逻辑思维能力和排序算法
个人认为这两个才是考点

12 楼 hax 2007-10-10  

认为这是脑筋急转弯的朋友是当面试的人傻瓜啊。

就算是脑筋急转弯，说5次的同志也不及格。

11 楼 lixiao 2007-10-09  

抛出异常的爱 写道

lixiao 写道

aiut 写道

5次。

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

你用的方式已经是最简单的了
不过没看出来与程序有什么关系，顶多是个脑筋急转弯的题了。

看起来是和程序没有太大的关系
但是通过一道题能看出一个人的思路如何
我当时是先和HR确认排除其他因素后再进行思考的。

不太赞同这个是脑筋急转弯题
现在大公司面试通通有不少这样的题

10 楼 realreal2000 2007-10-09  

这个就看公司看重什么了，拿秒表给赛马计时这个是很正常的吧，很多时候，达到一件事有很多方法，看待问题的不同，体现一个人的生活经历的不同，也表现性格

9 楼 抛出异常的爱 2007-10-09  

lixiao 写道

aiut 写道

5次。

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

你用的方式已经是最简单的了
不过没看出来与程序有什么关系，顶多是个脑筋急转弯的题了。

8 楼 lixiao 2007-10-09  

aiut 写道

5次。

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

7 楼 抛出异常的爱 2007-10-09  

realreal2000 写道

realreal2000 写道

这个题目很明显没有现实中的偶然性，就像男子100米，所以计算机要永远也无法预言2008奥运会100米的前三

不能说永远，至少现在不能，

汗。。。
可预见比赛成绩的话有谁去看比赛呢？

6 楼 realreal2000 2007-10-09  

realreal2000 写道

这个题目很明显没有现实中的偶然性，就像男子100米，所以计算机要永远也无法预言2008奥运会100米的前三

不能说永远，至少现在不能，

5 楼 realreal2000 2007-10-09  

这个题目很明显没有现实中的偶然性，就像男子100米，所以计算机要永远也无法预言2008奥运会100米的前三

4 楼 bcccs 2007-10-09  

抛出异常的爱 写道

realreal2000 写道

aiut 写道

5次。

同意，题目本来就不严谨

需求都是不严谨的。
PS：用秒表。。。

这种题目明显是类似与基于比较的排序如何确定前3大元素，不过唯一的区别就是每次可以5个元素参与一次排出顺序，算一次比较而已。
ps:如果赛马场只有2个道，那么这就是一个经典的计算机排序问题了。

3 楼 抛出异常的爱 2007-10-09  

realreal2000 写道

aiut 写道

5次。

同意，题目本来就不严谨

需求都是不严谨的。
PS：用秒表。。。

2 楼 realreal2000 2007-10-09  

aiut 写道

5次。

同意，题目本来就不严谨

1 楼 aiut 2007-10-09  

5次。