题目
来源：腾讯独有高频（LC 470）—— 概率类手写题的代表作。
已有函数
rand7()，它均匀随机地返回
[1, 7] 的整数。请
只用 rand7() 实现
rand10()：均匀随机地返回
[1, 10] 的整数。
两个硬要求：
- 期望调用次数尽量少（不能写死次数硬试）；
- 能证明均匀性 —— 每个 1..10 的输出概率严格是 1/10。
百度变体：用 rand4()（均匀返回 0~4）实现 rand6()（均匀返回 0~6）—— 同一台机器换个参数就是它。
先说一句容易走偏的方向：
一个 rand7() 只有 7 个状态，7 不能均分成 10 份 —— 不管怎么加、减、取模都没用（7 % 10、7 × 3 % 10 都不是均匀的）。出路只有一条：
创造更大的、能被 10 整除的状态空间。
一、核心洞察：乘积空间 —— 两次 rand7 凑出 49 个等概率状态
两次
独立的
rand7() 构成一个二元组
(a, b)，共有
7 × 7 = 49 种组合，
每种的概率都是 1/49。把二维拍平成一维：
v = (a - 1) × 7 + b → v 均匀取 1..49
49 里
能被 10 整除的最大块是 40（
40 = 4 × 10）：
v ≤ 40 → 接受，输出 (v - 1) % 10 + 1；v ≥ 41 → 拒绝（9 个状态，概率 9/49），这两个 rand7() 作废，整组重掷。
def rand10() -> int:
while True:
v = (rand7() - 1) * 7 + rand7() # 均匀取 1..49
if v <= 40:
return (v - 1) % 10 + 1 # 均匀取 1..10
三行代码，但每一行都有讲究：乘 7 是「七进制进位」（把 (a-1) 挪到十位、b 放个位）；
- 1 让 a 从 0 起（否则乘积空间会有空洞）；
(v-1) % 10 + 1 把 1..40 映射成 1..10 各四次。
二、为什么「接受区切得动、拒绝区不捣乱」
看一眼 49 格被怎么切：
每个输出恰好 4 个来源状态，一个不多一个不少；40 格被 10 个输出均分、零重叠零遗漏。这就是均匀性的全部来源 —— 动画二就是这张表的逐组点亮。
三、动画怎么看
动画一（
algo-viz--lc470）：
拒绝采样流程。左边是 7×7 的状态表（行 = a、列 = b，格子里是
(a-1)×7+b；
绿色 1..40 是接受区、红色 41..49 是拒绝区）；右边是两颗骰子（两次
rand7()）、合成公式、判定（接受 / 拒绝）和输出序列。盯住三件事：
每次都要掷两次（调用计数成对增长）、
命中格落在哪区（金框）决定去留、
拒绝帧不产出（输出序列不动）。
动画二（
algo-viz--lc470uni）：
均匀性证明。同一张 49 格表，按
输出分组着色：输出 1..10 各一种颜色，逐组点亮（每组恰好 4 格），拒绝的 9 格永远灰色。跑完时右侧清单「输出 k ×4」十行齐平 —— 这就是「每个输出概率相等」的字面证据。
四、完整推演表
动画一（拒绝采样） 的默认脚本逐帧：
输出序列
[8, 3, 2, 6, 10]，共调用 12 次（6 轮 × 2）、拒绝 1 次。
每次拒绝只是多花两次调用，不会污染任何一次输出的分布。
动画二（状态切分）：40 个接受状态的分组表（见第二节的表）—— 十组、每组 4 格、拒绝 9 格，合计
10 × 4 + 9 = 49。
五、均匀性证明
设 A 是「本轮被接受」事件，O 是输出：
P(O = k 且 A) = 4/49 （输出 k 的 4 个来源状态，每个 1/49）
P(A) = 40/49
⇒ P(O = k | A) = (4/49) / (40/49) = 4/40 = 1/10
：设第 m 轮才接受，则
P(第 m 轮接受且输出 k) = (9/49)^(m-1) × 4/49
对所有 m 求和 = (4/49) / (1 - 9/49) = (4/49) × (49/40) = 1/10
每一步重掷都与之前
独立同分布，所以「第一次落进接受区」的那一轮，条件分布仍是均匀的 —— 拒绝只消耗次数，不改变概率。
想亲手验证：跑 5 万次统计频数（每个输出应接近 5000 次），或者做卡方检验；本文仓库里的单测就是这么干的（固定随机源 + 频数带 + 结构断言「每个输出恰好 4 个来源状态」）。
六、期望次数与下界
期望推导：每轮的接受概率
p = 40/49，轮数服从几何分布：
E[轮数] = 1/p = 49/40 = 1.225
E[调用数] = 2 × 1.225 = 2.45 次 rand7()
也就是
平均每产出 1 个 rand10() 结果要掷 2.45 次；拒绝率 9/49 ≈ 18.4% 是这套方案的必要浪费。
下界在哪里：每次
rand7() 携带
log2(7) ≈ 2.807 bit 信息，一个
rand10() 需要
log2(10) ≈ 3.322 bit —— 所以
任何方案都至少要
3.322 / 2.807 ≈ 1.18 次调用。2.45（简单拒绝法）到 1.18（下界）之间的差距，属于进阶话题：
回收拒绝值：把被拒绝的状态折算进下一轮（比如把 1..9 的余数乘以 7 再补一次掷骰，凑出新的状态空间再切），期望可以继续下降 —— 面试里能提这一句，说明你理解「拒绝 = 浪费信息」，而不是死记 2.45。
七、百度变体：0~4 → 0~6（附同族题）
同一台机器，参数换一换：
rand4() 均匀返回
0~4（
5 个值），要造
rand6()（均匀返回
0~6，7 个值）。
- 两次独立抽样：
v = a × 5 + b（a、b ∈ 0..4）→ 均匀 0..24，共 25 个状态；
- 25 里能被 7 整除的最大块：
21 = 3 × 7 → v ≤ 20 接受、21..24 拒绝；
- 输出
v % 7（0..6），每个输出恰好 3 个来源状态；
- 期望调用：
2 × 25/21 = 50/21 ≈ 2.381 次。
def rand6() -> int: # rand4() 返回 0..4
while True:
v = rand4() * 5 + rand4() # 均匀 0..24
if v <= 20:
return v % 7 # 均匀 0..6
对照记一下两个数字：
49 → 40（每输出 4 个来源）、
25 → 21（每输出 3 个来源）。
「最多能切出多少、每份分几个」永远看 ⌊状态数 / 目标数⌋ × 目标数。
同族题（随机化家族）：LC 384 打乱数组（Fisher–Yates，等概率的关键在「从后往前交换」）、LC 398 随机数索引（水塘抽样）、LC 528 按权重随机选择（前缀和 + 二分）、LC 478 在圆内随机生成点（拒绝采样，或极坐标里对半径先开方）、LC 497 非重叠矩形中的随机点（面积加权 + 矩形内均匀）。它们和本题共享同一条世界观：
均匀性要靠结构证明，不能靠感觉。
八、Java 版
class Solution {
public int rand10() {
while (true) {
int v = (rand7() - 1) * 7 + rand7(); // 1..49
if (v <= 40) {
return (v - 1) % 10 + 1; // 1..10
}
}
}
}
Java 两个注意点：
(rand7() - 1) * 7 + rand7() 的
两个调用顺序无关（必须独立），但千万别写成
rand7() * 7 + rand7() - 7 这种化简 —— 中间态会越界、可读性也差；另外不要在循环外缓存
rand7() 结果想「省一次」—— 每次重掷都必须是
新鲜的两个独立样本。
九、边界与常见坑
- 只掷一次：
rand7() * 10 / 7、rand7() % 10 之类都不是均匀的 —— 7 的状态空间切不出 10 份均分；
(a-1) * 7 + b 写成 a * 7 + b：得到 8..56，0 和 7 的边界状态概率被扭曲（其实是 8..56 有 49 个数，但 a=0 不存在，映射会撞车 —— 总之不是均匀 1..49）；- 取模写成
v % 10：v = 10 会输出 0。正确写法 (v - 1) % 10 + 1；
- 拒绝区间写成
v ≥ 40：把 v = 40 错误拒绝，接受区只剩 39 个、切不成 4×10。判据是 v ≤ 40（acceptLimit = ⌊49/10⌋ × 10）；
- 拒绝后只重掷一颗骰子：必须重新掷两个。复用旧的一个值会破坏独立性（旧值和新值的联合分布不再是均匀的 49 格）；
- 想「省调用」而改小拒绝率：接受区必须能被 10 整除，40 就是 49 里的最优解 —— 更小的「浪费」只能靠回收余数，而不是缩小接受区；
- 死循环担心：理论上有无限重掷的可能，但概率以
(9/49)^m 衰减，期望有限（2.45 次）——不是 bug；
- 验证均匀性时样本太少：几万次起步才看得出偏差；判断标准用频数带或卡方，而不是「看着挺均匀」。
十、复杂度与期望
十一、面试怎么答
第一段 · 思路：一次
rand7() 只有 7 个状态，凑不出 10 份均分；两次独立调用构成 49 个等概率状态（乘积空间），取
v = (a-1)×7 + b 得到 1..49 均匀；49 里能被 10 整除的最大块是 40 —— 接受
v ≤ 40、输出
(v-1)%10+1，
v > 40 整组重掷。
第二段 · 证明与期望（
这段是区分度所在）：每个输出恰好 4 个来源状态 → 条件概率
4/40 = 1/10；几何级数求和证明重掷不破坏均匀；期望
2 × 49/40 = 2.45 次。顺手报出信息论下界 1.18，说明你知道 2.45 不是终点。
第三段 · 变体与追问：换参数（0~4 → 0~6：25 → 21、每份 3 个、期望 50/21）、回收拒绝值的进阶写法、以及「怎么验证均匀」（大样本频数 / 卡方）。
一句话收尾：「这道题只有一句口诀 ——
两次采样凑乘积空间，切出能被目标数整除的最大块；剩下的是把『拒绝不改变条件分布』证清楚、把期望 2.45 算明白。」
结语
rand7 → rand10 的全部内容就是「造大状态空间 + 切整齐」：49 个等概率状态里切出 40 个（4 × 10）接受、9 个拒绝重掷；均匀性来自「每组恰好 4 个来源状态」，期望 2.45 来自几何分布，1.18 是它够不到的下界。把它写对的人，换任何一组参数（5 → 7、3 → 5……）都能一眼报出：状态数、切块、每份几个、期望多少。
下一篇见。