企业官网建设流程全解析

LeetCode-Go 题解 470：用 rand7() 构造均匀 rand10() 的拒绝采样原理与 Go 实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

LeetCode 470 是一道经典的"随机数放大"问题：只给你一个能等概率生成 1～7 的rand7()，要求你仅凭它实现出等概率生成 1～10 的rand10()，并且禁止使用系统级随机数 API。本文以 LeetCode-Go 仓库中 0470 题解文档 为核心骨架，完整讲解"组合放大 → 拒绝采样 → 取模映射"的解题链路，结合仓库内的 Go 源码 Using Rand7().go>) 与 测试用例 Using Rand7()_test.go>) 印证实现细节，并推导进阶问题中rand7()期望调用次数。读完本文，你将掌握任意randN() → randM()（M > N）的通用构造方法，并能独立完成这类"拒绝采样"型随机数题目的推导与编码。

题目理解

题目给出一个已预定义的方法rand7()，它能均匀（uniform）地生成 1 到 7 范围内的随机整数；要求编写rand10()，均匀生成 1 到 10 范围内的随机整数，且不得使用系统自带的Math.random()等现成随机 API。

示例行为如下：

Input: 1 Output: [7] Input: 2 Output: [8,4] Input: 3 Output: [8,1,10]

注意点：

1. rand7是预定义好的，直接调用即可；
2. 每个测试用例只有一个参数n，代表rand10()被调用的次数，返回的是每次调用的结果序列。

进阶问题（Follow up）是本题的精华所在：

1. 实现过程中调用rand7()的期望值是多少？
2. 你能否尽量减少rand7()的调用次数？

第一个问题考察对"拒绝采样"数学期望的推导能力，第二个问题则引导思考更高效的随机数复用方案，下文会分别给出解答。

核心思路：从小随机数放大为大随机数

rand7()等概率产生 1, 2, 3, 4, 5, 6, 7，只有 7 种结果；而rand10()需要 10 种等概率结果。直觉上的难点在于：7 不是 10 的约数，无法靠一次调用直接映射。

题解文档给出的破题思路是分三步走：先构造一个范围是 10 的整数倍的randN()，再通过取模得到rand10()。具体链路为：

rand7() --> rand49() --> rand40() --> rand10()

其中每一步的构造依据如下：

1. rand7()等概率地产生 1, 2, 3, 4, 5, 6, 7；
2. rand7() - 1等概率地产生 [0, 6]；
3. (rand7() - 1) * 7等概率地产生 0, 7, 14, 21, 28, 35, 42；
4. (rand7() - 1) * 7 + (rand7() - 1)等概率地产生 [0, 48] 这 49 个数字——这正是rand49()；
5. 若第 4 步的结果大于等于 40，则重复第 4 步，直到产生的数落在 [0, 39]，得到rand40()（即拒绝采样，丢弃 40～48）；
6. 将第 5 步的结果 mod 10 再加 1，即等概率地随机生成 [1, 10]。

为什么 (rand7()-1)*7 + (rand7()-1) 能均匀覆盖 [0, 48]

这一步是整个方案的基石，其本质是七进制组合：把两次独立的rand7()调用看成一位"高位"和一位"低位"。

• 高位(rand7() - 1)均匀取 [0, 6] 中的一个值；
• 低位(rand7() - 1)也均匀取 [0, 6] 中的一个值；
• 组合数高位 * 7 + 低位的取值范围是 [0×7+0, 6×7+6] = [0, 48]，共 49 个值。

由于两次调用相互独立且各自等概率，7×7 = 49 种(高位, 低位)组合一一对应 49 个不同的整数，因此这 49 个整数出现概率完全相同——rand49()是均匀的。

为什么过滤后再取模仍然均匀

[0, 48] 中的数字对 10 取模，0～8 各出现 5 次，9 只出现 4 次，直接% 10 + 1会破坏均匀性。因此先执行拒绝采样：丢弃 40～48 这 9 个值，只保留 [0, 39]。在 [0, 39] 内，0～9 每个数字各出现 4 次（0-9、10-19、20-29、30-39），对 10 取模后 0～9 严格等概率，+1后即为等概率的 [1, 10]。

丢弃意味着可能要多轮重试，但每轮之间相互独立，成功概率为 40/49（约 81.6%），因此算法几乎必然终止（无限重试的概率为 0），且不会引入任何偏差——这正是"拒绝采样"（rejection sampling）的标准形态。

仓库 Go 源码实现

仓库中 470 题解目录 下的 实现文件 Using Rand7().go>) 提供了两个函数，分别对应两种写法：

package leetcode import "math/rand" func rand10() int { rand10 := 10 for rand10 >= 10 { rand10 = (rand7() - 1) + rand7() } return rand10%10 + 1 } func rand7() int { return rand.Intn(7) } func rand101() int { rand40 := 40 for rand40 >= 40 { rand40 = (rand7()-1)*7 + rand7() - 1 } return rand40%10 + 1 }

对照前文的分析可以确认：

• rand101()严格对应题解文档描述的rand49 → rand40 → rand10标准链路。表达式(rand7()-1)*7 + rand7() - 1即文档中的(rand7() - 1) * 7 + (rand7() - 1)（两次rand7()独立调用），循环条件rand40 >= 40实现拒绝采样，最后rand40%10 + 1完成取模映射；
• rand10()是仓库中的另一种写法，构造思路同样是"组合出一个更大范围 → 过滤超界值 → 取模"，但组合方式不同：(rand7() - 1) + rand7()是两次调用之和而非七进制拼接，两种实现恰好展示了同一思想下的不同组合策略。

需要说明的是：题目约定rand7()生成 1～7 的均匀整数，而实现文件中为了方便本地运行，将rand7()定义为rand.Intn(7)（返回 [0, 6]），等价于把题目中rand7()的结果整体减 1 后使用。在实际提交时，应使用 LeetCode 预定义的rand7()（返回 [1, 7]），并据此微调表达式偏移；核心的"组合放大 + 拒绝采样 + 取模"框架不变。

测试与验证方式

同目录下的 测试文件 Using Rand7()_test.go>) 采用 LeetCode-Go 仓库统一的Test_Problem470组织方式：

func Test_Problem470(t *testing.T) { qs := []question470{ {para470{}, ans470{2}}, {para470{}, ans470{0}}, {para470{}, ans470{1}}, } fmt.Printf("------------------------Leetcode Problem 470------------------------\n") for _, q := range qs { _, p := q.ans470, q.para470 fmt.Printf("【input】:%v 【output】:%v\n", p, rand10()) rand101() } fmt.Printf("\n\n\n") }

测试中依次调用rand10()与rand101()，打印每次生成的随机数，用于冒烟验证两个函数可正常执行且输出落在合理范围内。每个题目目录都是独立的package leetcode，因此可单独运行：

go test -v -run Test_Problem470 ./leetcode/0470.Implement-Rand10-Using-Rand7/

仓库根目录的 gotest.sh 还提供了全量覆盖率的生成方式（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），生成的 coverage.txt 即为仓库覆盖率报告，说明该仓库对题解代码有系统的覆盖测试支撑。

进阶一：rand7() 期望调用次数是多少

这是题解文档 Follow up 直接抛出的问题，可以用几何分布精确回答。

在标准方法中，每一轮尝试消耗 2 次rand7()（一次构造高位、一次构造低位），成功接受的概率为：

p = 40 / 49

设完成一次rand10()所需的轮数为 T，则 T 服从成功概率为 p 的几何分布。几何分布的期望为：

E[T] = 1 / p = 49 / 40 = 1.225

因此生成一个rand10()平均消耗的rand7()调用次数为：

2 × E[T] = 2 × 49/40 = 98/40 = 2.45 次

也就是说，平均每次rand10()大约需要调用rand7()2.45 次。这个数值正是拒绝采样"以少量重试换均匀性"的代价体现。

进阶二：能否尽量减少 rand7() 的调用次数

答案是肯定的，优化方向主要有两条：

• 复用被拒绝的样本：丢弃 40～48 这 9 个值其实浪费了信息。可以将被拒绝样本映射到下一次尝试的"高位"，让被丢弃的随机性部分参与后续构造，从而降低平均调用次数，使其从 2.45 进一步向理论下界逼近；
• 更大的组合基数：构造rand7() × rand7() × rand7()这类更高维的组合（如 343 区间），一次消耗 3 次调用但接受率更高，可摊薄单次调用的浪费。从信息论角度看，每次rand7()携带 log₂7 ≈ 2.807 bit 熵，生成 [1, 10] 至少需要 log₂10 ≈ 3.322 bit，即理论下界约为 log₇10 ≈ 1.18 次调用/每次输出——任何实现都无法低于该下界，实际可行方案只能无限逼近它。

对于面试或竞赛而言，掌握"标准方法 + 期望值推导"已足以通关；追求极致效率时，再考虑被拒绝样本的信息复用即可。

通用推广：用 randN() 实现 randM()（M > N）

题解文档将本题提炼为一般性方法，可用于任意randN()→randM()（M > N）的转换，步骤固定为：

1. 构造足够大的randX()：用randN()组合出randX()，要求 X ≥ M 且 X 是 M 的整数倍。例如本题中构造的 49 > 10，且 49 的倍数截断点 40 是 10 的倍数；
2. 拒绝采样过滤：将randX()的结果中大于等于某个 M 的整数倍上界 Y（Y 是 M 的倍数且 Y ≤ X）的部分丢弃重试，得到等概率的randY()；
3. 取模映射：randY() % M + 1即得到等概率的randM()。

题解文档给出三个生动的实例，可以对照验证公式：

例一：用rand3()生成rand11()

先构造rand27()：3 * 3 * (rand3() - 1) + 3 * (rand3() - 1) + (rand3() - 1)——这是三进制组合，覆盖 [0, 26] 共 27 个等概率值；以 22 为过滤界限（22 是 11 的倍数），保留 [0, 21] 后取模，即得rand11()。

例二：用rand7()生成rand9()

先构造rand49()：(rand7() - 1) * 7 + (rand7() - 1)，覆盖 [0, 48]；以 45 为过滤界限（45 是 9 的倍数），保留 [0, 44] 后取模，即得rand9()。

例三：用rand6()生成rand13()

先构造rand36()：(rand6() - 1) * 6 + (rand6() - 1)，覆盖 [0, 35]；以 26 为过滤界限（26 是 13 的倍数），保留 [0, 25] 后取模，即得rand13()。

三个例子贯穿同一条方法论：进制组合放大 → 以目标值的整数倍为界拒绝采样 → 取模映射。只要 N 进制组合后能覆盖 M 的某个整数倍上界，问题就必然可解。

小结

LeetCode 470 表面是一道"随机数放大"题，实质考察的是对概率均匀性的严谨把控：组合必须一一对应、拒绝采样必须不引入偏差、取模前必须保证余数等频。LeetCode-Go 仓库以rand49() → rand40() → rand10()的标准链路给出了简洁的 Go 实现，并配套测试与全量覆盖率脚本，可以作为面试手写"拒绝采样"类题目的标准参考模板。掌握本文的推导，你不仅能解决本题，还能把randN()扩展到任意randM()场景，从容应对同类变体题。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go