论坛首页 综合技术论坛

针对论坛里的一个讨论“讨论一个算法,GOOGLE的一个面试题”给出我的解法

浏览 2282 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2008-11-12   最后修改:2008-11-12
今天在论坛看到了个题目,说是Google的面试题,我想了个解法,大家来推敲下。

题目如下:
这个是google的一个面试题,觉得挺有意思的,问题是这样的:
一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。
假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问最少得比多少场才能知道跑得最快的5匹马。

我想了个算法。
一、前五轮。分五组,比出1, 2, 3, 4, 5
二、让每组的第一再比赛,选出第一不用比了,肯定是最快的。暂定为a1胜出,剩下的排序如下
    1  2  3  4  5 
1  a2 b1 c1 d1 e1
2  a3 b2 c2 d2 e2
3  a4 b3 c3 d3 e3
4  a5 b4 c4 d4 e4
5     b5 c5 d5 e5
三、然后让剩下的各组第一比赛,获胜的是第二
...

以此类推,最后选出5个来。

最后应该是10轮能分出前五名。

分析:每轮能战胜其他第一名的肯定能战胜所有的马匹。但是有个问题,如果两匹马一样快的话就要同时胜出。
   发表时间:2008-11-26  
既然是“每匹马都跑的很稳定”,也就是说马的速度是稳定的,也就是马的成绩是稳定的,而且问题是“最少得比多少场才能知道跑得最快的5匹马。”也就是说没有让你排除前五名的排名次序,只要是前五就行,这就排除了马的成绩相同的情况,如此,我认为只要跑五次就行了,记录成绩就可以了,何必弄的这么复杂、?
或许,面试官要得不是精确的答案呢?
0 请登录后投票
论坛首页 综合技术版

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