浏览 2282 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2008-11-12
最后修改:2008-11-12
题目如下: 这个是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轮能分出前五名。 分析:每轮能战胜其他第一名的肯定能战胜所有的马匹。但是有个问题,如果两匹马一样快的话就要同时胜出。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2008-11-26
既然是“每匹马都跑的很稳定”,也就是说马的速度是稳定的,也就是马的成绩是稳定的,而且问题是“最少得比多少场才能知道跑得最快的5匹马。”也就是说没有让你排除前五名的排名次序,只要是前五就行,这就排除了马的成绩相同的情况,如此,我认为只要跑五次就行了,记录成绩就可以了,何必弄的这么复杂、?
或许,面试官要得不是精确的答案呢? |
|
返回顶楼 | |