一道据说是Google的面试题：25匹马的角逐

Love The Way You Lie 2022-10-01 04:55 144阅读 0赞

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

注意： "假设每匹马都跑的很稳定" 的意思是在上一场比赛中A马比B马快，则下一场比赛中A马依然比B马快。

**稍微想一下，可以采用一种 竞标赛排序(Tournament Sort) 的思路。**

(1) 首先将25匹马分成5组，并分别进行5场比赛之后得到的名次排列如下：

A组：  \[A1  A2  A3   A4  A5\]

B组：  \[B1  B2  B3   B4  B5\]

C组：  \[C1  C2  C3  C4  C5\]

D组：  \[D1  D2  D3  D4  D5\]

E组：  \[E1  E2  E3   E4  E5\]

其中，每个小组最快的马为\[A1、B1、C1、D1、E1\]。

(2) 将\[A1、B1、C1、D1、E1\]进行第6场，选出第1名的马，不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将\[A2、B1、C1、D1、E1\]进行第7场，此时选择出来的必定是第2名的马，不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场，选择\[A2、B2、C1、D1、E1\]角逐出第3名的马。

(4) 依次类推，第9，10场可以分别决出第4，5名的吗。

因此，依照这种竞标赛排序思想，需要10场比赛是一定可以取出前5名的。

**仔细想一下，如果需要减少比赛场次，就一定需要在某一次比赛中同时决出2个名次，而且每一场比赛之后，有一些不可能进入前5名的马可以提前出局。 **当然要做到这一点，就必须小心选择每一场比赛的马匹。

我们在上面的方法基础上进一步**思考**这个问题，希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论：有一些马在前6场比赛之后就决定出局的命运了(下面绿色字体标志出局)。

A组：  \[A1  A2  A3   A4  A5\]

B组：  \[B1  B2  B3   B4  B5 \]

C组：  \[C1  C2  C3  C4 C5 \]

D组：  \[D1  D2  D3  D4  D5 \]

E组：  \[E1  E2  E3   E4  E5 \]

(3) 第7场比赛是关键，能否同时决出第2，3名的马呢？我们首先做下分析：

在上面的方法中，第7场比赛\[A2、B1、C1、D1、E1\]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1)，试问？有B1在的比赛，C1、D1、E1还有可能争夺第2名吗？ 当然不可能，也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名，剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗？

能够优化的关键出来了，我们是否能够通过剩下的3个跑道来决出第3名呢？当然可以，我们来进一步分析第3名的情况？

● 如果A2>B1(即第2名为A2)，那么根据第6场比赛中的(B1>C1>D1>E1)。 可以断定第3名只能在A3和B1中产生。

● 如果B1>A2(即第2名为B1)，那么可以断定的第3名只能在A2, B2,C1 中产生。

好了，结论也出来了，只要我们把\[A2、B1、A3、B2、C1\]作为第7场比赛的马，那么这场比赛的第2，3名一定是整个25匹马中的第2，3名。

我们在这里列举出第7场的2，3名次的所有可能情况：

①  第2名=A2，第3名=A3

②  第2名=A2，第3名=B1

③  第2名=B1，第3名=A2

④  第2名=B1，第3名=B2

⑤  第2名=B1，第3名=C1

(4)  第8场比赛很复杂，我们要根据第7场的所有可能的比赛情况进行分析。

①  第2名=A2，第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

● 如果第4名=A4，那么第5名只能在A5、B1中产生。

● 如果第4名=B1，那么第5名只能在A4、B2、C1中产生。

不管结果如何，此种情况下，第4、5名都可以在第8场比赛中决出。其中比赛马匹为\[A4、A5、B1、B2、C1\]

②  第2名=A2，第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

● 如果第4名=A3，那么第5名只能在A4、B2、C1中产生。

● 如果第4名=B2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=C1，那么第5名只能在A3、B2、C2、D1中产生。

那么，第4、5名需要在马匹\[A3、B2、B3、C1、A4、C2、D1\]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

③  第2名=B1，第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

情况和②一样，必须角逐第9场

④  第2名=B1，第3名=B2。 那么此种情况下第4名只能在A2、B3、C1中产生。

● 如果第4名=A2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=B3，那么第5名只能在A2、B4、C1中产生。

● 如果第4名=C1，那么第5名只能在A2、B3、C2、D1中产生。

那么，第4、5名需要在马匹\[A2、B3、B4、C1、A3、C2、D1\]七匹马中产 生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

⑤  第2名=B1，第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

● 如果第4名=A2，那么第5名只能在A3、B2、C2、D1中产生。

● 如果第4名=B2，那么第5名只能在A2、B3、C2、D1中产生。

● 如果第4名=C2，那么第5名只能在A2、B2、C3、D1中产生。

● 如果第4名=D1，那么第5名只能在A2、B2、C2、D2、E2中产生。

那么，第4、5名需要在马匹\[A2、B2、C2、D1、A3、B3、C3、D2、E1\]九匹马中 产 生，因此也必须比赛两场，也就是到第9长决出胜负。

总结：最好情况可以在第8场角逐出前5名，最差也可以在第9场搞定。

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java面试题一道，据说90%的程序员答不上来

前两天发出来一道面试题：[打印平行四边型][Link 1]，今天把解题思路放出来。先复习一下题目：题目要求：输入一个数字，打印出如下平行四边形。 ![在这里插入

男娘i/ 2024年01月20日 07:18/ 0 赞/ 42 阅读

相关白话经典算法系列之十一道有趣的GOOGLE面试题

最近在[微博][Link 1]上看到一道有趣的GOOGLE面试题，见下图： ![format_png][] 文字版：一个大小为n的数组，里面的数都属于范围\[0, n-

红太狼/ 2023年06月18日 07:56/ 0 赞/ 13 阅读

相关一道据说是Google的面试题：25匹马的角逐

问题是这样的：一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少

Love The Way You Lie/ 2022年10月01日 04:55/ 0 赞/ 145 阅读

相关一道面试题

问：已有一个函数f(),它等概率的生成1－5的整数，问如何利用该函数，等概率的生成1-7的整数？解：先抛开这个问题，换另一个问题进行思考：假若我们现在有一个

以你之姓@/ 2022年09月20日 06:05/ 0 赞/ 278 阅读

相关一道 Google 竞赛题的解法

一道 Google 竞赛题的解法一、竞赛题目 Problem Statement You are given a String\[\] grid

ゝ一世哀愁。/ 2022年09月19日 14:22/ 0 赞/ 192 阅读

相关亚马逊一道智力面试题

亚马逊一道面试题，50个白球，50个黑球，两个箱子，如何放，获取白球的机率更大？这个还是比较容易，可以采用边界值的思维考虑，要么一个箱子中放50个白球，另外一个箱

清疚/ 2022年08月19日 05:49/ 0 赞/ 287 阅读

相关从 Google 的一道面试题说起·

内容选自：《程序员的数学基础课》 2004 年，在硅谷的交通动脉 101 公路上出现了一块巨大的广告牌，上面是道数学题： \{ e 的连续数字中最先出现的 10 位质数 \}

╰+哭是因爲堅強的太久メ/ 2022年02月22日 09:24/ 0 赞/ 214 阅读

相关从 Google 的一道面试题说起·

内容选自：《程序员的数学基础课》 2004 年，在硅谷的交通动脉 101 公路上出现了一块巨大的广告牌，上面是道数学题： \{ e 的连续数字中最先出现的 10 位质数 \}

喜欢ヅ旅行/ 2022年02月22日 05:55/ 0 赞/ 244 阅读

相关一道阿里的面试题

随便写写： package com.test; / 有一堆石子共100枚，甲乙轮流从该堆中取石子，每次可以去2、4或6枚，取得最后

曾经终败给现在/ 2021年12月13日 22:59/ 0 赞/ 340 阅读

相关一道面试题

大四第一学期，就只有两个晚上有选修课，正好快11周，选修课也结束了。就开始思量着找工作，前几天花费了一天时间在大街网写了一份简历，可大街网上提供的岗位太少。在室友的推荐下，转战

素颜马尾好姑娘i/ 2021年06月24日 16:00/ 0 赞/ 601 阅读