 构造均匀 rand10() 的拒绝采样原理与 Go 实现)
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 是一道经典的随机数放大问题只给你一个能等概率生成 17 的rand7()要求你仅凭它实现出等概率生成 110 的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]注意点rand7是预定义好的直接调用即可每个测试用例只有一个参数n代表rand10()被调用的次数返回的是每次调用的结果序列。进阶问题Follow up是本题的精华所在实现过程中调用rand7()的期望值是多少你能否尽量减少rand7()的调用次数第一个问题考察对拒绝采样数学期望的推导能力第二个问题则引导思考更高效的随机数复用方案下文会分别给出解答。核心思路从小随机数放大为大随机数rand7()等概率产生 1, 2, 3, 4, 5, 6, 7只有 7 种结果而rand10()需要 10 种等概率结果。直觉上的难点在于7 不是 10 的约数无法靠一次调用直接映射。题解文档给出的破题思路是分三步走先构造一个范围是 10 的整数倍的randN()再通过取模得到rand10()。具体链路为rand7() -- rand49() -- rand40() -- rand10()其中每一步的构造依据如下rand7()等概率地产生 1, 2, 3, 4, 5, 6, 7rand7() - 1等概率地产生 [0, 6](rand7() - 1) * 7等概率地产生 0, 7, 14, 21, 28, 35, 42(rand7() - 1) * 7 (rand7() - 1)等概率地产生 [0, 48] 这 49 个数字——这正是rand49()若第 4 步的结果大于等于 40则重复第 4 步直到产生的数落在 [0, 39]得到rand40()即拒绝采样丢弃 4048将第 5 步的结果 mod 10 再加 1即等概率地随机生成 [1, 10]。为什么 (rand7()-1)*7 (rand7()-1) 能均匀覆盖 [0, 48]这一步是整个方案的基石其本质是七进制组合把两次独立的rand7()调用看成一位高位和一位低位。高位(rand7() - 1)均匀取 [0, 6] 中的一个值低位(rand7() - 1)也均匀取 [0, 6] 中的一个值组合数高位 * 7 低位的取值范围是 [0×70, 6×76] [0, 48]共 49 个值。由于两次调用相互独立且各自等概率7×7 49 种(高位, 低位)组合一一对应 49 个不同的整数因此这 49 个整数出现概率完全相同——rand49()是均匀的。为什么过滤后再取模仍然均匀[0, 48] 中的数字对 10 取模08 各出现 5 次9 只出现 4 次直接% 10 1会破坏均匀性。因此先执行拒绝采样丢弃 4048 这 9 个值只保留 [0, 39]。在 [0, 39] 内09 每个数字各出现 4 次0-9、10-19、20-29、30-39对 10 取模后 09 严格等概率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()生成 17 的均匀整数而实现文件中为了方便本地运行将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 -covermodeatomic -coverprofilecoverage.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() 的调用次数答案是肯定的优化方向主要有两条复用被拒绝的样本丢弃 4048 这 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的转换步骤固定为构造足够大的randX()用randN()组合出randX()要求 X ≥ M 且 X 是 M 的整数倍。例如本题中构造的 49 10且 49 的倍数截断点 40 是 10 的倍数拒绝采样过滤将randX()的结果中大于等于某个 M 的整数倍上界 YY 是 M 的倍数且 Y ≤ X的部分丢弃重试得到等概率的randY()取模映射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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 470：用 rand7() 构造均匀 rand10() 的拒绝采样原理与 Go 实现
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 是一道经典的随机数放大问题只给你一个能等概率生成 17 的rand7()要求你仅凭它实现出等概率生成 110 的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]注意点rand7是预定义好的直接调用即可每个测试用例只有一个参数n代表rand10()被调用的次数返回的是每次调用的结果序列。进阶问题Follow up是本题的精华所在实现过程中调用rand7()的期望值是多少你能否尽量减少rand7()的调用次数第一个问题考察对拒绝采样数学期望的推导能力第二个问题则引导思考更高效的随机数复用方案下文会分别给出解答。核心思路从小随机数放大为大随机数rand7()等概率产生 1, 2, 3, 4, 5, 6, 7只有 7 种结果而rand10()需要 10 种等概率结果。直觉上的难点在于7 不是 10 的约数无法靠一次调用直接映射。题解文档给出的破题思路是分三步走先构造一个范围是 10 的整数倍的randN()再通过取模得到rand10()。具体链路为rand7() -- rand49() -- rand40() -- rand10()其中每一步的构造依据如下rand7()等概率地产生 1, 2, 3, 4, 5, 6, 7rand7() - 1等概率地产生 [0, 6](rand7() - 1) * 7等概率地产生 0, 7, 14, 21, 28, 35, 42(rand7() - 1) * 7 (rand7() - 1)等概率地产生 [0, 48] 这 49 个数字——这正是rand49()若第 4 步的结果大于等于 40则重复第 4 步直到产生的数落在 [0, 39]得到rand40()即拒绝采样丢弃 4048将第 5 步的结果 mod 10 再加 1即等概率地随机生成 [1, 10]。为什么 (rand7()-1)*7 (rand7()-1) 能均匀覆盖 [0, 48]这一步是整个方案的基石其本质是七进制组合把两次独立的rand7()调用看成一位高位和一位低位。高位(rand7() - 1)均匀取 [0, 6] 中的一个值低位(rand7() - 1)也均匀取 [0, 6] 中的一个值组合数高位 * 7 低位的取值范围是 [0×70, 6×76] [0, 48]共 49 个值。由于两次调用相互独立且各自等概率7×7 49 种(高位, 低位)组合一一对应 49 个不同的整数因此这 49 个整数出现概率完全相同——rand49()是均匀的。为什么过滤后再取模仍然均匀[0, 48] 中的数字对 10 取模08 各出现 5 次9 只出现 4 次直接% 10 1会破坏均匀性。因此先执行拒绝采样丢弃 4048 这 9 个值只保留 [0, 39]。在 [0, 39] 内09 每个数字各出现 4 次0-9、10-19、20-29、30-39对 10 取模后 09 严格等概率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()生成 17 的均匀整数而实现文件中为了方便本地运行将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 -covermodeatomic -coverprofilecoverage.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() 的调用次数答案是肯定的优化方向主要有两条复用被拒绝的样本丢弃 4048 这 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的转换步骤固定为构造足够大的randX()用randN()组合出randX()要求 X ≥ M 且 X 是 M 的整数倍。例如本题中构造的 49 10且 49 的倍数截断点 40 是 10 的倍数拒绝采样过滤将randX()的结果中大于等于某个 M 的整数倍上界 YY 是 M 的倍数且 Y ≤ X的部分丢弃重试得到等概率的randY()取模映射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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考