图 1:本文封面,答案是 7 场。
先说明属性:这是一篇经典题解析,题目出自本地历史面试资料,与任何公司的当前招聘无关。题面很短:25 匹马、5 条赛道,每场比赛只能知道同场五匹马的相对名次,没有计时器,问找出全场最快的前三名,最少要比几场?
先把答案立住:7 场。难点不在记住这个数字,而在推出它的那条缩圈逻辑。整道题只有一条推理规则反复使用:一匹马只要被证实「有至少三匹马比它快」,它就和前三名无缘,直接出局。
**第一步:5 场分组赛。**把 25 匹马分成 5 组,每组赛一场,得到每组内部的名次。这一步的意义是把「全场未知」压缩成「五个组内有序」。
**第二步:第 6 场,头马对决。**让五个组的第一名同场比一次。这场做完有两件事被确定:其一,这场的冠军就是全场第一——它赢过本组全部四匹,又赢过其他四组的头马,而其他组的每匹马都慢于自己的头马,传递下来它比全部 24 匹都快;其二,按这场名次给五个组排个序,后面就叫冠军组、亚军组、季军组和第四、第五名组。
**第三步:排除,这是全题的钥匙。**对着六场比赛的结果逐匹问那句「有三匹比它快吗」:第四名组的头马前面有冠军组头马、亚军组头马、季军组头马三匹,整组出局;第五名组同理整组出局;季军组里,第二名前面已经有「冠军组头马、亚军组头马、季军组头马」三匹,所以季军组只有头马还活着;亚军组里,第三名前面有「冠军组头马、亚军组头马、亚军组第二名」,所以亚军组只剩前两匹;冠军组自己,头马已锁定全场第一不再参赛,第四名、第五名前面各有组内三匹更快的,也出局。数一遍:候选只剩五匹——冠军组的第二、三名,亚军组的前两名,季军组的头马。
**第四步:第 7 场,五匹候选决胜。**这场的前两名就是全场第二、第三。第一名早已确定,不参加这场。
图 2:四步缩圈,排除规则是「被证实有三匹更快即出局」。
**为什么 6 场不够,7 场一定够?**光讲道理容易心虚,直接写代码验证。思路:给 25 匹马随机生成隐藏的真实速度(人看不到,只能通过比赛拿到名次),严格按上面的七场方案执行,最后比对算法给出的前三和真实前三。用 Node.js 22.15.0 直接运行(node horses.js):
'use strict';
// 可复现随机数(固定种子,输出稳定)
function mulberry32(seed) {
return function () {
seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
// 跑一遍完整方案:25 匹马有隐藏的真实速度,人只能比赛看名次
function runOnce(rand) {
const horses = Array.from({ length: 25 }, (_, id) => ({ id, speed: rand() }));
// 第 1~5 场:分 5 组,各赛一场,组内排出名次
const groups = [];
for (let g = 0; g < 5; g++) {
groups.push(horses.slice(g * 5, g * 5 + 5).sort((a, b) => b.speed - a.speed));
}
// 第 6 场:各组头马对决,按名次给组排序(groups[0] 是冠军组)
groups.sort((g1, g2) => g2[0].speed - g1[0].speed);
// 排除后只剩 5 匹候选:冠军组第 2、3 名,亚军组前 2 名,季军组头马
const candidates = [groups[0][1], groups[0][2], groups[1][0], groups[1][1], groups[2][0]];
// 第 7 场:候选对决,前两名即全场第二、第三(第一是冠军组头马)
candidates.sort((a, b) => b.speed - a.speed);
const answer = [groups[0][0].id, candidates[0].id, candidates[1].id];
const truth = [...horses].sort((a, b) => b.speed - a.speed).slice(0, 3).map((h) => h.id);
// 顺带记录:只赛 6 场时,真正的全场第二名落在哪一组
return { ok: answer.join() === truth.join(), secondGroup: groups.findIndex((g) => g.some((h) => h.id === truth[1])) };
}
const N = 100000;
let pass = 0;
const secondAt = [0, 0, 0, 0, 0];
const rand = mulberry32(20261025);
for (let i = 0; i < N; i++) {
const r = runOnce(rand);
if (r.ok) pass++;
secondAt[r.secondGroup]++;
}
console.log(`随机 ${N} 种速度分布,7 场方案找对前三:${pass}/${N}`);
console.log(`只赛 6 场时,真实第二名的分布:冠军组第 2 名 ${secondAt[0]} 次,亚军组头马 ${secondAt[1]} 次,其余组 ${secondAt[2] + secondAt[3] + secondAt[4]} 次`);
实测输出:
随机 100000 种速度分布,7 场方案找对前三:100000/100000
只赛 6 场时,真实第二名的分布:冠军组第 2 名 16689 次,亚军组头马 83311 次,其余组 0 次
第一行说明七场方案在十万种随机速度分布下全部找对。第二行是「6 场不够」的实锤:赛完六场后,真实的全场第二名有时是冠军组的第二名、有时是亚军组的头马——两种可能都会真实出现,不加赛第七场就无法确定,所以 7 场既是充分的也是必要的。
**常见误区。**一是上来想「一场定胜负」,25 匹马无法同场,此路不通;二是试图变相计时,比如「多比几次取平均」,题目明确没有计时器,相对名次是唯一信息;三是排除时只敢整组淘汰,漏掉组内排除——其实亚军组的第三、四、五名同样满足「三匹更快」,敢用到组内这一层,候选才能收敛到五匹;四是以为第六场之后按组排座次就能直接读出全场名次,实测数据已经说明不行。
跳出题目看,这是一种「只能小组比较、无法全局排序」场景下的成本控制思维——锦标赛排序、两两对比评测都是同构问题:比较次数就是预算,每比一场都要让排除面尽量大。你第一次见这道题时,给出的答案是几场?欢迎分享。