|
锁定老帖子 主题：讨论一个算法，GOOGLE的一个面试题
精华帖 (8) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-11-07
最后修改：2008-11-07
blurm 写道 1，先赛五场
2，第六场，每场的第一名赛一次，此次的第一名拿出去 3，第七场，第六场第一名在（1）里队伍的第二名顶上来再加上第六场的剩下四名比赛，此次的第一名再拿出去。 4，第七场的第一名在（1）里的下一个名次的马继续顶上来，和剩下的四匹马比赛 这样算下来得赛10场，不知道对不对 我表述的太烂了。。。sigh，自己寒一个 我觉这个差不多 借前面的形式 A1 A2 A3 A4 A5 B1 B2 B3 B4 B5 C1 C2 C3 C4 C5 D1 D2 D3 D4 D5 E1 E2 E3 E4 E5 快<===慢 第6场：拿A1 B1 C1 D1 E1 来比，可以得到最快的一匹，这个没问题了，在第6场假设是A1最快，E1最慢 第7场：用A2 B1 C1 D1 E1 来比（这里这5匹应该是剩下的最快的5匹了），如果A2最快，那么结果出来了，最快的5匹就是A1 A2 A3 A4 A5,如果C1最快，就拿剩下的A2 B1 C2 D1 E1再去比第8场（B1最快，就用A2 B2 C1 D1 E1比第8场） 思想就是每次都拿A[] B[] C[] D[] E[] 中最快一个来比 。。。感觉结果是最快7场，最慢10场。。。 |
| 返回顶楼 | |
|
发表时间：2008-11-07
这个比较不好说,要是我去考试.我就会写6场
根据题目的描述来说,没有限制方法,从广义考虑,我们有方法可以在6场中分出胜负 分5组 1>每组第一名跑到目的地时,目测每匹马的身位差别,心记之 2>把5个第一拉来跑一场,同样目测每匹马的身位差别,心记之 3>以某匹马为标准值,心算每匹马的权值,列出前5 4>OK |
| 返回顶楼 | |
|
发表时间：2008-11-07
支持zhangkaitao，最撞大运的方法，在概率上6场是可能选出最快的5匹马
|
| 返回顶楼 | |
|
发表时间：2008-11-07
最多21场吧
先随便挑五个赛，的、挑出最慢的来，跟另外四个比，如果在比那四个都慢就需要比把那四个放到原来的组去比，每次裁掉一个最慢的，这样理论上最慢的话要21场 最快就是第一次选出的五匹马就是前五名的话只需6次就行了 |
| 返回顶楼 | |
|
发表时间：2008-11-08
最后修改：2008-11-08
“至少”的话就相当简单了，五队分类赛排出名次，然后五队的第一再赛一次，排出队列的名次，这时第一队的第一一定是第一了。
把第二队的第一放到第一队，我们可以保证第二队的第一一定是后面几队中最快的。第二队的第一和第一队的其他马比，如果是第四或者第五，那么名次就一定出来了。。。 所以至少是七次！ |
| 返回顶楼 | |
|
发表时间：2008-11-11
blurm 写道 stormspire 写道 我也并不知道标准答案，下面是我的思路:
第6轮完毕是 A组 A1,A2,A3,A4,A5 B组 B1,B2,B3,B4,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 假设 A1>B1>C1>D1>E1 第二名没有什么悬念，肯定是A2,B1中的一个 第三名也没有悬念，是A2,A3,B1,B2,C1中的一个 所以拿A2,B1,A3,B2,C1 比一轮 （第7轮），那么可以得出第2、3名，并且可以淘汰第5名，以及第5名所在的其余成员 下面的就麻烦了。 1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以 2. 如果A2,B1是前两名，再比第8轮也可以得出结果。我就不仔细分析了。 3. 最复杂的情况就是B1和C1是前两名， 3.1 如果A3是最后一名，剩下 A组 A1,A2,--,--,-- B组 B1,B2,B3,--,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 这里就有A2,B2,B3,C2,C3,D1,D2,E1 8匹马来竞争最后的2个名额. A2,B2比过，所以 第4名可以在 A2,B2中的快者，然后加上C2,D1中比出来，假设我第8轮只用3匹马比，可以得出第4，而且可以淘汰第3名以及比第3名慢的马。所以第8轮可以至少淘汰2匹，加上选出来的第4，那么第9轮只剩下5匹马了，可以得出结果。 3.2 如果B2是最后一名，剩下 A组 A1,A2,A3,--,-- B组 B1,--,--,--,-- C组 C1,C2,C3,--,-- D组 D1,D2,--,--,-- E组 E1,--,--,--,-- 可以发现这个图比上面的还简单，所以不会比3.1多 综上，觉得至少应该比9轮 关于第七轮的分析: 1. 最简单情况，如果A2，A3是前两名，那么第4、5名就是A4,A5,B1,B2,C1里面，再比第8轮就可以 如何能够确定B3,B4就在前五名开外呢? 因为现在是A1,A2,A3是前3名，然后还有两个名额，如果B3在前5名，然后B1>B2>B3,所以B1,B2也得在前5名，这样就不符合两个名额的推理了。 |
| 返回顶楼 | |
|
发表时间：2008-11-11
nciky1984 写道 以下是我的思路- -
首先前6次比赛按照楼主的思路.. 然后画出结果表格。如附件1的图1，表格里的数字代表这批马可能跑到的最好排名 根据前6场的比赛结果我们可以很容易得到以下3条结果： 从横向方向来看：右边那匹马的可能的最好成绩是左边一匹最好成绩+1，比如A2可能的最好成绩是第2，则A3的可能最好成绩是第3 从纵向方向上来看：在第1列上，下面那匹马的最好成绩是是上面那匹马的最好成绩+1，比如B1可能的最好成绩是第2，则C1可能的最好成绩是第3 表格中数字唯一：即代表这批马的排名...比如A1是第一。为了方便起见，标明为绿色 下面是第7轮的比赛算法.. 选择没有确定排名的，数字最小的5匹马进行比赛，如附件1中图1的红色部分标明的5匹马..把排名填写在表中。因为第一名已经确认，所以从第2名开始排列 假设排名结果如附件1图2这样的结果（紫色部分）。 根据前面得到的3个条件，更新表格中马匹的最好成绩...见附件1图3。 很显然，最好成绩在第6名以后的可以直接淘汰.. 然后重复以上循环即可得出跑得最快的5匹马... 最少需要8轮，即附件1所示那种情况。 以上算法可以扩展到有N匹马，M个赛道中... 但是题目问的是 至少 需要多少场比赛...也就是说运气最好的情况下可以确认前5的比赛场数... 所以答案得靠...凑 首先每匹马都得至少进行一场比赛，所以前5场比赛没有悬念... 关键在于第6场...将A5和B1，C1，D1，E1拉一起比... 如果运气够好，A5第一胜出... 排名就是A1，A2，A3，A4，A5。 最少需要 6场 比赛就能够确定名次.. 表格中最后一个图没法在一轮就能决定最后的两名 |
| 返回顶楼 | |
|
发表时间：2008-11-11
计时器是干毛用的？科学的发明不利用是落后还是返古？。。。
|
| 返回顶楼 | |
|
发表时间：2008-11-11
applefeng_52 写道 计时器是干毛用的？科学的发明不利用是落后还是返古？。。。
你的话引出了一个更深入的问题 |
| 返回顶楼 | |
|
发表时间：2008-11-12
stormspire 写道 nciky1984 写道 以下是我的思路- -
首先前6次比赛按照楼主的思路.. 然后画出结果表格。如附件1的图1，表格里的数字代表这批马可能跑到的最好排名 根据前6场的比赛结果我们可以很容易得到以下3条结果： 从横向方向来看：右边那匹马的可能的最好成绩是左边一匹最好成绩+1，比如A2可能的最好成绩是第2，则A3的可能最好成绩是第3 从纵向方向上来看：在第1列上，下面那匹马的最好成绩是是上面那匹马的最好成绩+1，比如B1可能的最好成绩是第2，则C1可能的最好成绩是第3 表格中数字唯一：即代表这批马的排名...比如A1是第一。为了方便起见，标明为绿色 下面是第7轮的比赛算法.. 选择没有确定排名的，数字最小的5匹马进行比赛，如附件1中图1的红色部分标明的5匹马..把排名填写在表中。因为第一名已经确认，所以从第2名开始排列 假设排名结果如附件1图2这样的结果（紫色部分）。 根据前面得到的3个条件，更新表格中马匹的最好成绩...见附件1图3。 很显然，最好成绩在第6名以后的可以直接淘汰.. 然后重复以上循环即可得出跑得最快的5匹马... 最少需要8轮，即附件1所示那种情况。 以上算法可以扩展到有N匹马，M个赛道中... 但是题目问的是 至少 需要多少场比赛...也就是说运气最好的情况下可以确认前5的比赛场数... 所以答案得靠...凑 首先每匹马都得至少进行一场比赛，所以前5场比赛没有悬念... 关键在于第6场...将A5和B1，C1，D1，E1拉一起比... 如果运气够好，A5第一胜出... 排名就是A1，A2，A3，A4，A5。 最少需要 6场 比赛就能够确定名次.. 表格中最后一个图没法在一轮就能决定最后的两名 楼主给出的题目有歧义 当时题目问的是至少，不是至多... 我对至少的理解是：算法在最好的情况下所能得出的场次 |
| 返回顶楼 | |
