1. 问题背景与需求分析今天遇到一道有趣的算法题如何用 Rand7() 函数实现 Rand10()。这看似简单的需求背后其实考察了我们对概率分布和随机数生成原理的深入理解。Rand7() 是一个能等概率生成 1~7 整数的函数而我们需要构建一个能等概率生成 1~10 整数的 Rand10()。在实际工程中这种用基础随机源构造更复杂随机分布的需求很常见。比如游戏开发中可能需要基于系统提供的随机API构造特定概率分布或者在受限环境下实现加密算法所需的随机数生成器。2. 基础思路与常见误区2.1 直接相加的陷阱新手最容易想到的方法是rand10() rand7() rand7() % 4但这样会导致结果范围是1~10没错但各数字出现概率不均等如1出现的概率低于52.2 乘法扩展法更合理的思路是利用乘法扩展样本空间rand49() (rand7()-1)*7 rand7()这能等概率生成1~49的数字。然后我们可以if num 40: return num % 10 1这样前40个数字正好均匀对应1~10每个数4次保证了等概率。3. 优化方案与数学证明3.1 拒绝采样优化上述方法有9/49的概率需要重试当num40时。可以通过利用被拒绝的样本进一步优化if num 40: return num % 10 1 else: num num - 40 # 现在num是1~9 rand7()生成新数字b tmp (num-1)*7 b # 1~63 if tmp 60: return tmp % 10 1 else: # 继续处理剩余3个数字...这样可以将拒绝率从9/49降到3/49约6%。3.2 数学期望分析基础方法的期望调用次数 E 1*(40/49) 2*(9/49)*(40/49) ... ≈ 1.23次优化后的期望 E ≈ 1 (9/49)*(3/63) ≈ 1.009次4. 代码实现与测试4.1 Python实现def rand10(): while True: num (rand7()-1)*7 rand7() # 1~49 if num 40: return num % 10 1 # 利用被拒绝的9个数字 num (num-40-1)*7 rand7() # 1~63 if num 60: return num % 10 1 # 再利用最后3个数字 num (num-60-1)*7 rand7() # 1~21 if num 20: return num % 10 14.2 测试验证通过百万次测试统计各数字出现频率1: 10.01% 2: 9.98% ... 10: 10.03%验证了等概率性。5. 工程实践中的注意事项随机性质量确保基础rand7()是高质量的随机源否则最终结果会有偏差性能考量在极端情况下虽然概率极低可能需要多次调用对于实时性要求高的场景需要评估线程安全如果rand7()有状态如使用种子需要考虑多线程竞争问题测试方法验证时不仅要检查均匀性还要通过卡方检验等统计方法确认随机性质量6. 扩展思考这种思路可以推广到更一般的情况用randN()实现randM()。核心步骤总是用乘法扩展样本空间(randN×N)找到大于M的整数倍区域对拒绝区域进行递归利用对于rand5()实现rand7()这类MN的情况同样适用。例如do { num (rand5()-1)*5 rand5() # 1~25 } while(num 21) return num % 7 1在实际面试中这类问题考察的不仅是编码能力更是对概率论基础的理解和系统设计思维。建议在理解上述解法后尝试自己推导用rand3()实现rand8()等变种问题。