知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 赛马问题 ## 题目 有 64 匹马,8 个赛道(每次能让 8 匹马同时比赛),没有计时器(只能知道名次顺序)。问:找出**前 4 名**最少需要多少场比赛? ## 大白话理解 你是马场老板,有 64 匹马,但赛道一次只能跑 8 匹。你没秒表,只能看到谁先到谁后到。现在要挑出跑得最快的 4 匹去参加大赛,怎么用最少的比赛次数找出来? ``` 脑子里的误区: "把 64 匹马分成 8 组跑 8 场,每组取前 4 → 32 匹 → 再跑 4 场 → 16 匹 → ..." 这太浪费了!因为你忽略了一个重要信息:组内的排名反映了相对快慢! ``` --- ### 常见变体与答案 ``` 25 匹马,5 个赛道,找前 3 名 → 7 场比赛 64 匹马,8 个赛道,找前 4 名 → 10 场比赛(也可能 11 场,看具体策略) ``` --- ### 64 匹马找前 4 名:完整推导 #### 第 1 步:分组赛(8 场) ``` 64 匹马分成 8 组(A~H),每组 8 匹。每组跑一场。 A 组:[A1, A2, A3, A4, A5, A6, A7, A8] ← A1 最快 B 组:[B1, B2, B3, B4, B5, B6, B7, B8] ← B1 最快 C 组:[C1, C2, C3, C4, C5, C6, C7, C8] D 组:[D1, D2, D3, D4, D5, D6, D7, D8] E 组:[E1, E2, E3, E4, E5, E6, E7, E8] F 组:[F1, F2, F3, F4, F5, F6, F7, E8] G 组:[G1, G2, G3, G4, G5, G6, G7, G8] H 组:[H1, H2, H3, H4, H5, H6, H7, H8] 每组内排序: A1 > A2 > A3 > A4 > A5 > A6 > A7 > A8(> 表示更快) 共 8 场比赛 ``` #### 第 2 步:冠军赛(第 9 场) ``` 每组第一名比赛:A1, B1, C1, D1, E1, F1, G1, H1 结果(假设):A1 > B1 > C1 > D1 > E1 > F1 > G1 > H1 冠军确定:A1 是全球最快!✓ ``` #### 第 3 步:排除法——哪些马不可能进前 4? ``` A1 已经是冠军了(必进前 4) 跑得快的方向 → ┌──────────────────────────────────────────────────────┐ │ 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 ... ← 全组淘汰! │ │ F1 F2 F3 F4 F5 ... ← 全组淘汰! │ │ G1 G2 G3 G4 G5 ... ← 全组淘汰! │ │ H1 H2 H3 H4 H5 ... ← 全组淘汰! │ └──────────────────────────────────────────────────────┘ 排除逻辑: 1. D 组的第一名 D1 在冠军赛中排第 4 D 组其他马(D2, D3, ...)都慢于 D1 而 D1 已经是第 4 名 → D 组后面的绝对进不了前 4 2. E、F、G、H 组的第一名排第 5~8 整组最强者都排 5~8,组内其他马更没希望 → E、F、G、H 组全灭! 3. 组内排除: A 组:A1 是冠军。A5 及以后比 A4 慢,且 A 组已经有 A1 占一个名额 → 淘汰 A5~A8 B 组:B1 排第 2。B4 及以后比 B3 慢 → 淘汰 B4~B8 C 组:C1 排第 3。C3 及以后比 C2 慢 → 淘汰 C3~C8 D 组:D1 排第 4。D2 及以后比 D1 慢 → 淘汰 D2~D8 ``` ``` 淘汰后剩余: ┌─────────────────────────────────┐ │ A1 A2 A3 A4 │ A1 冠军,候选:A2, A3, A4 │ B1 B2 B3 │ 候选:B1, B2, B3 │ C1 C2 │ 候选:C1, C2 │ D1 │ 候选:D1 └─────────────────────────────────┘ 剩余:A2, A3, A4, B1, B2, B3, C1, C2, D1(9 匹) 争夺 3 个名额(前 4 名中 A1 已占一个) ``` #### 第 4 步:决赛(第 10 场) ``` 但 9 匹马,赛道只能跑 8 匹!怎么办? 关键观察:A1 已经是冠军,D1 在冠军赛中排第 4, C2 比 C1 慢,C1 排第 3 能否再排除一些? 候选名单按"最少比赛能进的"排: - 一定需要比的有:A2, A3, B1, B2, C1 - 大概率需要的:A4, B3, C2, D1 策略:任选 8 匹跑第 10 场(比如排除最不可能进的 D1 或 C2) 根据结果判断是否还需要第 11 场。 但有一种更严谨的做法: ┌─────────────────────────────────────────────┐ │ 第 10 场:A2, A3, B1, B2, C1, A4, B3, C2 │ │ (8 匹马刚好凑满) │ │ D1 暂时排除(它在冠军赛表现最差) │ └─────────────────────────────────────────────┘ 第 10 场结果分析: 情况 1:D1 不在前 3 → 不需要第 11 场 前 3 + A1 = 前 4 名 ✓ → 共 10 场 情况 2:如果前 3 的成绩差到连 D1 都可能 威胁 → 需要第 11 场确认 → 共 11 场 总结:10~11 场。通常面试回答 10 场即可。 ``` --- ### 25 匹马找前 3 名(7 场) ``` 这是更常见的面试题,思路完全一样: 第 1~5 场:25 匹分 5 组,每组 5 匹,跑 5 场 结果:A1>A2>A3>A4>A5, B1>B2>..., 等等 第 6 场:每组第一名比赛(A1, B1, C1, D1, E1) 假设结果:A1 > B1 > C1 > D1 > E1 排除: D 组、E 组全灭(第一名都排 4、5) A 组:A4, A5 淘汰 B 组:B3, B4, B5 淘汰 C 组:C2, C3, C4, C5 淘汰 剩余:A2, A3, B1, B2, C1(5 匹) 争夺 2 个名额(A1 冠军已定) 第 7 场:A2, A3, B1, B2, C1 比赛 前 2 名 + A1 = 前 3 名 ✓ 共 7 场比赛! ``` ``` ASCII 图解 25 匹马: 第 6 场后(冠军赛结果 A1>B1>C1>D1>E1) A1 ── A2 ── A3 ── A4 ── A5 │ B1 ── B2 ── B3 ── B4 ── B5 │ C1 ── C2 ── C3 ── C4 ── C5 ← C1 第3名,但已是小组第1 │ D1 ── ...(全组淘汰,D1 只是第 4) │ E1 ── ...(全组淘汰) ┌─────────────────────────────────────┐ │ 第 7 场比赛候选(5 匹): │ │ A2, A3(可能前 3 的 A 组选手) │ │ B1, B2(可能前 3 的 B 组选手) │ │ C1(C 组最强,可能挑战前 3) │ │ │ │ 为什么没有 A4?因为 A4 前面有 │ │ A1, A2, A3, B1 至少 4 个更快的 │ │ → A4 绝对进不了前 3 │ └─────────────────────────────────────┘ ``` --- ## 一句话总结 锦标赛思维:先分小组赛,再用各组冠军排序做排除。每轮比赛后,利用"比你组里快的"和"比其他组冠军快的"两个维度做排除,大幅缩减候选范围——25 匹找前 3 只需 7 场,64 匹找前 4 只需约 10 场。 --- 下一篇:[05 - 扔鸡蛋问题](./05-egg-drop.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入