核心要点

  • 构造均匀大空间：(rand7()-1)*7 + rand7() 得到 1..49 上的均匀整数。

  • 取能被 10 整除的前缀：保留 1..40，对其余 41..49 拒绝并重抽。

  • 映射：把 1..40 用 (num-1)%10 + 1 折叠到 1..10，等概率。

  • 期望调用：每轮成功概率 40/49，期望约 49/40·2 ≈ 2.45 次 rand7。

标准回答

目标是用只能产出 1..7 均匀整数的 rand7() 等概率产出 1..10。

第一步，扩大样本空间到 49（10 的倍数 40 的母空间）：令 num = (rand7() - 1) * 7 + rand7()。第一项 (rand7()-1) 取 {0,7,14,21,28,35,42}，第二项取 {1..7}，两者相加无重叠地覆盖 1..49，且每个值概率均为 1/49（两次调用独立均匀）。

第二步，拒绝采样使空间能被 10 整除：若 num 落在 1..40，接受；若落在 41..49，丢弃并重新来过。在接受条件下，1..40 上仍是均匀分布。

第三步，折叠映射：返回 (num - 1) % 10 + 1，把 1..40 等分成 4 组每组 10 个，映射到 1..10，每个结果概率 4/40 = 1/10。

拒绝部分（41..49 共 9 个值）保证了均匀性，不能简单对 49 取模——因为 49 不是 10 的倍数，直接取模会让某些余数偏多。期望每轮接受概率 40/49，期望循环 49/40 轮、约 2.45 次 rand7 调用。下方为标准实现。

python
import random

def rand7():
    """题目给定：等概率返回 1..7"""
    return random.randint(1, 7)

def rand10():
    """等概率返回 1..10，拒绝采样保证均匀"""
    while True:
        num = (rand7() - 1) * 7 + rand7()   # 均匀落在 1..49
        if num <= 40:                        # 接受 1..40
            return (num - 1) % 10 + 1        # 折叠到 1..10
        # 41..49：拒绝，重新循环

if __name__ == '__main__':
    from collections import Counter
    cnt = Counter(rand10() for _ in range(1000000))
    for k in range(1, 11):
        print(k, round(cnt[k] / 1000000, 3))  # 应都 ≈ 0.1

常见误区

⚠️ 常见踩坑

不要对 49 直接取模映射 1..10（49 不是 10 的倍数，会偏置）；也别忘了拒绝分支必须 continue/重抽，把 41..49 强行映射会破坏均匀性。

追问

追问 1：能否复用被拒绝的 41..49 以减少 rand7 调用？

可以。被拒绝的 41..49 是 9 个均匀值，等价于一个 rand9 的部分信息；进一步与新的 rand7 组合可摊薄消耗，但实现复杂、收益有限，面试中说明思路即可。常见优化是把剩余熵继续累积进下一轮。

追问 2：一般地，如何用 randM 实现 randN？

把若干次 randM 拼成均匀的 0..M^k-1 空间，取其中最大的 N 的倍数 t=floor(M^k/N)*N，接受 [0,t) 并对 N 取模，超出则拒绝重抽。这是通用的拒绝采样构造。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

📖 术语表

🛠️ AI 工具

  • Continue

    开源 AI 编程助手，33K+ stars。支持 VS Code 和 JetBrains IDE，集成多种 LLM 提供商，提供代码补全、对话、编辑等能力，是 Cursor 的开源替代方案。

🎯 相关面试题