锁定老帖子 主题:一道Intel的面试题
精华帖 (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匹中的前三名 题目是不难 但是要能在面试的环境下快速的整理思路,还是有点难度的:) 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2007-10-09
5次。
|
|
返回顶楼 | |
发表时间:2007-10-09
aiut 写道 5次。
同意,题目本来就不严谨 |
|
返回顶楼 | |
发表时间:2007-10-09
realreal2000 写道 aiut 写道 5次。
同意,题目本来就不严谨 PS:用秒表。。。 |
|
返回顶楼 | |
发表时间:2007-10-09
抛出异常的爱 写道 realreal2000 写道 aiut 写道 5次。
同意,题目本来就不严谨 PS:用秒表。。。 这种题目明显是类似与基于比较的排序如何确定前3大元素,不过唯一的区别就是每次可以5个元素参与一次排出顺序,算一次比较而已。 ps:如果赛马场只有2个道,那么这就是一个经典的计算机排序问题了。 |
|
返回顶楼 | |
发表时间:2007-10-09
这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三
|
|
返回顶楼 | |
发表时间:2007-10-09
realreal2000 写道 这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三
不能说永远,至少现在不能, |
|
返回顶楼 | |
发表时间:2007-10-09
realreal2000 写道 realreal2000 写道 这个题目很明显没有现实中的偶然性,就像男子100米,所以计算机要永远也无法预言2008奥运会100米的前三
不能说永远,至少现在不能, 可预见比赛成绩的话有谁去看比赛呢? |
|
返回顶楼 | |
发表时间:2007-10-09
aiut 写道 5次。
5次怎么排?望赐教。。 另外,本身就是道面试题,肯定不会考虑什么秒表之类的因素了 其他还有什么不严谨的方面,我真没怎么看出来。 |
|
返回顶楼 | |
发表时间:2007-10-09
lixiao 写道 aiut 写道 5次。
5次怎么排?望赐教。。 另外,本身就是道面试题,肯定不会考虑什么秒表之类的因素了 其他还有什么不严谨的方面,我真没怎么看出来。 你用的方式已经是最简单的了 不过没看出来与程序有什么关系,顶多是个脑筋急转弯的题了。 |
|
返回顶楼 | |