6

面试题:你有 25 匹马,需要多少场比赛才能找出跑得最快的 3 匹马?你没有秒表,每场比赛只能同时让 5 匹马参赛。(算法题,也可以视为逻辑题)

求答案及详细推理过程。

投票6好问题烂问题同问修改
1个解答
6

正确答案

7 场。

推理过程

你可以先询问面试官,「最快」的意思,是不是指比赛时总能赢?在真实情况下并非如此。但倘若你假设, A 在比赛中跑赢了 B , A 就无可争议地跑得更快,这就极大地简化了这道谜题。

面试官会告诉你,这么想没有问题,比赛就是为了选出跑得最快的马。通常,你会下意识地想,至少需要 5 场比赛。任何一匹马都可能排名前三,所以,你必须让所有的 25 匹马都参加比赛。可每次只让 5 匹马参赛,少于 5 场比赛没法让所有的马都参赛。

很好。接下来你的结论会是:只有 5 场比赛还不够。第一轮,把 25 匹马分为 5 组,每组里的马只跑一次,只跟同组的马匹竞争。一轮比赛结果大概会是这样:

  • 第一名:「奔腾」
  • 第二名:「北舞」
  • 第三名:「凯速」
  • 第四名:「上将」
  • 第五名:「跳影」

你无法断定「奔腾」是 25 匹马里跑得最快的,甚至无法担保它能排进前三名。举个极端情况下的相反例子:其他 4 场比赛中跑得最慢的马,也可能比「奔腾」跑得快,因为它的速度可能在 25 匹马里排第 21 名。

那么,从这场比赛里我们是否了解到什么东西呢?当然了。我们了解到这 5 匹马的排名情况。我们还了解到,「上将」和「跳影」可以排除在外了。既然它们在这一轮比赛里排不进前三,那么在所有的 25 匹马里,它们同样不可能排进前三。。这个道理,也适用于其他轮比赛里的第 4 名和第 5 名。每一轮比赛可以排除掉两匹马。在第一轮的 5 场比赛中,我们可以刷掉 10 匹马,留下 15 匹马竞争前三名。

第二轮,即第 6 场比赛,要测试在最初 5 场比赛中表现出色者。合理的方案是让 5 匹上一轮比赛的「第一名」对战。就这么做吧!让「奔腾」和其他 4 场比赛的第一名跑一回。结果可能会是这样:

  • 第一名:「易歌尔」
  • 第二名:「奔腾」
  • 第三名:「终结者」
  • 第四名:「红朗姆」
  • 第五名:「菲尔拉普」

这一次,我们又可以排除两匹马,「红朗姆」和「菲尔拉普」。从这一次的比赛结果看,它们不可能是 25 匹马里的前三名。我们还了解到,「易歌尔」是所有马里跑得最快的!如果问题问的只是 25 匹马里跑得最快的是谁,那么答案就是「易歌尔」。

可我们要的是前三名。我们不光可以排除掉「红朗姆」和「菲尔拉普」,还可以排除掉第一轮比赛中所有败给它们的马。败给它们的马跑得更慢,而我们又已经知道「红朗姆」和「菲尔拉普」进不了前三了。

接下来是「奔腾」。从这场最新的比赛结果来看,它有可能是所有马里跑得第二快的。但以下可能性仍然存在:第一场比赛排在「奔腾」之后的「北舞」,是所有马里跑得第三快的。那么,最终排名就是「易歌尔」、「奔腾」和「北舞」。第一场比赛中排第三的「凯速」,现在出局了。

「易歌儿」第一次比赛时排在它后头的第二名和第三名,仍在候选之列。这两匹马的速度完全有可能比「奔腾」快,因为它们并没有比试过。

总之,现在候选名单里还有 6 匹马。它们是:本场比赛的前三名;与本场比赛第一名在第一场比赛中获第二、第三名的两匹马;在第一场比赛中仅次于本场比赛第二名的一匹马。

我们已经知道「易歌儿」是跑得最快的马,因此,让它参赛没有任何意义了,于是就只剩下 5 匹马。自然,第三轮,我们会让这 5 匹马进行第 7 场,也是最后一场比赛。第 7 场比赛的前两匹马就是所有 25 匹马中跑得第二快和第三快的。

总结一下

先进行 5 场资格赛;之后让资格赛的第一名们进行冠军争夺赛,本场比赛的获胜者就是所有马里速度最快的;再对逻辑上仍有资格的 5 匹马进行最后一场比赛。这次比赛里的前两名,就是 25 匹马里跑第二和第三快的。

收藏感谢修改

我的解答