他遇到的一个经典题目（转）

pcl2004_27

一个朋友经过n轮面试去上海微软了。

他遇到的一个经典题目：

有25匹赛马，每次赛只能有5匹参加，问最少赛几次能找出最快的3匹马，并排出名次。

朱小燕0616

太厉害了，使用二叉树进行排除

zero零

最简单的两次：25匹马，分5组，每组取第一名，再比下得出前三；

不过这个遗漏性太大了，可能第一组的第二名优于其他组的第一名哇。

xm3525

厉害，7次真不错啊

lifadonglfd

xinyijiu25

恩 好像很有道理的 Great!

Nio

time:

先分了5 组进行比赛，比赛5次，剩余15匹；
用二叉树原理，比赛1次，去掉两组（6匹），剩余9匹；
‘c组的后两名也可淘汰；b组的最后一名也可以淘汰。’去掉3匹，剩余6匹；去第一名，剩5匹，比赛1次；

Great!!

time

不小心发了三遍，sorry

revolution

我靠

time

我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

time

我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

time

我的答案是7次。
具体如下，请大家帮忙测试，看有否bug：
分成5组。
赛5次得到每组前3名：
a1、a2、a3；
b1、b2、b3；
c1、c2、c3；
d1、d2、d3；
e1、e2、e3。
将5个第一名进行比赛，得到前3名，不妨假设按名次依次为a1、b1、c1。
这样，依据二叉树排序原理，因最终只取前三名，所以从a1算起超过三个节点的均被淘汰，故：d和e组可淘汰；c组的后两名也可淘汰；b组的最后一名也可以淘汰。
第一名a1不需再赛，剩余的5匹a2、a3、b1、b2、c1赛一次取出前两名，即为总成绩第二和第三。
所以，共赛7次。

shiling

我的天那，我就是计算不出来

adamstao

owen.wang

好难啊，这样的题目，面试的时候一定是做不出来的。

songfun

没错，呵呵，正如楼上说的。

小子不信邪

拿6个，各3个，剩下两个。对3个的两组进行比较
1，如果两边一样重，那么对剩下的比较；
2，如果两边不一样重，对重的那边进行分组，各取一个进行比较，结果就出来了。

songfun

知道为什么只要两次么？嗯，答案下期公布。。。呵呵

songfun

其实微软的绝招就是这几招，有本书叫《微软的选修秘密》，会发现这道题跟另一道极为相似，改头换面一下就出来了。有兴趣可以专门研究研究这些题目的共通之处，所谓一法通万法通。相信不难的。
这道题是：
假定你有8个撞球，其中有1个比其他球重，如果只能利用天平来判定哪一个重，请问要找到重的那个球至少要几次？（答案见题目）

Nio

只要9次比赛就可以了哟:p

[ Last edited by Nio on 2005-1-21 at 18:37 ]