从rand()到拒绝采样：深入解析随机数生成原理与LeetCode 470实战

1. 项目概述：从“会用”到“玩转”随机数

在编程世界里，随机函数就像一把瑞士军刀，看似简单，但用不好就容易伤到自己。无论是C++里的rand()、mt19937，还是Java里的Random、ThreadLocalRandom，很多开发者都停留在“调用一下，得到一个数”的层面。直到在LeetCode上遇到像第470题“用Rand7()实现Rand10()”这样的经典概率题，才猛然发现，自己对随机函数的理解还停留在表层。这道题之所以能“打败99%的选手”，恰恰是因为它精准地考察了开发者对随机数生成原理、概率均等性以及算法设计的综合能力，而不仅仅是API调用。今天，我们就抛开简单的调用手册，深入C++和Java的随机数引擎内部，并结合这道高频面试题，彻底把随机函数“玩明白”。无论你是正在准备面试，还是希望在日常开发中写出更健壮、更高效的随机逻辑，这篇深度解析都将为你提供从理论到实战的完整路径。

2. 核心原理：随机数生成器的“引擎盖”之下

2.1 伪随机与真随机的本质区别

首先要破除一个迷思：我们在编程中使用的绝大多数“随机数”都是“伪随机数”。它们并非真正的物理随机（如量子涨落），而是由一个确定的、复杂的数学公式（称为算法或生成器）根据一个初始值（种子）计算出来的数列。由于算法是确定的，所以只要种子相同，生成的随机数序列就完全一样。这既是缺点（不可用于密码学等需要绝对随机的场景），也是优点（便于调试和复现程序行为）。真随机数则需要依赖物理世界的熵源，如硬件噪声、鼠标移动等，在通用编程中较少直接使用。

2.2 C++随机数库的“现代”与“古典”

C++11对随机数库进行了一次重大革新，引入了<random>头文件，提供了更灵活、更高质量的随机数生成方案。

古典派：rand()与srand()这是C语言遗留下来的方法，至今仍被广泛使用，但问题颇多。

#include <cstdlib> #include <ctime> // 初始化种子，通常用时间 srand(time(nullptr)); // 生成一个[0, RAND_MAX]之间的整数 int randomNum = rand(); // 生成[0, N)的整数 int numInRange = rand() % N;

注意：rand() % N是极不推荐的做法。因为rand()生成的随机数低比特位可能周期性较弱（取决于实现），且当N不是2的幂时，会导致结果分布不均匀。例如，若RAND_MAX=32767，取模7，那么0-4出现的概率会比5、6略高。

现代派：<random>库这是目前C++中生成随机数的推荐方式，它清晰地将“随机数引擎”和“分布器”分离。

• 引擎：负责生成高质量的原始随机数序列。最常用的是std::mt19937（梅森旋转算法），周期极长，性能好。
• 分布器：负责将引擎生成的数映射到我们想要的统计分布上，如均匀分布uniform_int_distribution、正态分布normal_distribution等。

#include <random> #include <iostream> int main() { // 1. 定义随机数引擎，使用真随机设备初始化种子 std::random_device rd; // 用于获取种子，可能慢或非真随机 std::mt19937 gen(rd()); // 以rd()的输出作为种子初始化引擎 // 2. 定义分布器，生成[1, 10]的均匀分布整数 std::uniform_int_distribution<> distrib(1, 10); // 3. 生成随机数 for (int i = 0; i < 5; ++i) { std::cout << distrib(gen) << ' '; } return 0; }

这种方式的优点是分布均匀、可控性强，并且不同分布之间互不干扰。

2.3 Java随机数生成的多面手

Java提供了多个随机数生成类，适用于不同场景。

基础款：java.util.Random这是最常用的类，线程安全但并发下性能有竞争开销。它使用一个48位的种子，通过线性同余公式进行修改。

import java.util.Random; Random rand = new Random(); // 默认以系统时间纳秒为种子 int randomNum = rand.nextInt(10); // 生成[0,10)的整数，分布均匀 double randomDouble = rand.nextDouble(); // 生成[0.0, 1.0)的double

实操心得：Random的构造函数如果使用无参构造，其种子源于System.nanoTime()，这在单次运行中没问题。但如果需要在程序多次启动间获得不可预测的序列，应使用SecureRandom或传入更复杂的种子。

高性能并发款：java.util.concurrent.ThreadLocalRandom这是Java 7为高并发场景引入的。每个线程都维护自己独立的随机数生成器实例，彻底消除了竞争，性能极高。

import java.util.concurrent.ThreadLocalRandom; int randomNum = ThreadLocalRandom.current().nextInt(1, 11); // 生成[1, 11)即[1,10]的整数

注意事项：ThreadLocalRandom必须在调用线程内通过current()方法获取，不能跨线程共享实例。它非常适合在循环、并行流等场景中生成随机数。

密码学安全款：java.security.SecureRandom它旨在生成密码学意义上强健的随机数，可用于生成密钥、盐值。其实现可能依赖操作系统提供的真随机源（如/dev/random），速度较慢。

import java.security.SecureRandom; SecureRandom secRand = new SecureRandom(); byte[] salt = new byte[16]; secRand.nextBytes(salt); // 用随机字节填充数组

3. 实战剖析：LeetCode 470. 用 Rand7() 实现 Rand10()

理解了基础，我们进入核心战场。LeetCode 470题提供了一个完美的场景，让我们应用上述原理。题目要求：给定一个可以生成[1,7]均匀随机整数的函数rand7()，请你实现一个生成[1,10]均匀随机整数的函数rand10()。你只能调用rand7()，且要尽量减少调用次数。

3.1 错误思路与均匀分布陷阱

最常见的错误想法是：rand7() + rand7() - 1或者(rand7() - 1) * 7 + rand7()。前者得到的是[1,13]，但分布不均匀（和为7的概率远高于和2或12）。后者其实是生成[1,49]均匀分布的标准方法（等会会用到），但直接取模% 10会破坏均匀性，因为49不能被10整除，会导致[1,9]的数字比10多一次出现机会。

3.2 标准解法：拒绝采样（Rejection Sampling）

这是解决此类问题的通用且高效的方法。核心思想是：利用已知的均匀随机源，构造一个更大范围的均匀随机空间，然后通过拒绝（丢弃）部分结果，使得剩余结果的范围恰好能被目标范围整除，从而保证均匀性。

步骤拆解：

1. 构造更大的均匀空间：用两次rand7()调用，可以独立且均匀地生成两个[1,7]的整数。将它们看作一个二维坐标(a, b)，其中a = rand7(),b = rand7()。这个二维空间共有7 * 7 = 49个点，每个点出现的概率都是1/49，是完全均匀的。
2. 映射到一维线性空间：为了便于处理，我们将这个二维坐标映射到一个一维的线性索引。公式为：idx = (a - 1) * 7 + (b - 1)。这个公式计算的是(a,b)在49个点中的线性位置（从0开始编号）。idx的取值范围是[0, 48]，共49个数，且每个数出现的概率相等（1/49）。
3. 应用拒绝采样：我们的目标是[1,10]，即10个数。49不能被10整除。如果我们对idx取模% 10，得到0-9，然后+1得到1-10。但49个idx值映射到10个结果上，前40个idx（0-39）每个结果会出现4次，而后9个idx（40-48）会导致前9个结果（1-9）额外多出现一次，破坏了10这个结果的均匀性。 因此，我们拒绝（丢弃）最后9个idx值（40-48）。只接受前40个idx值（0-39）。
4. 计算最终结果：对于被接受的idx（0-39），我们通过idx % 10 + 1将其均匀地映射到[1,10]。因为40能被10整除，所以这40个idx会均匀地分配给10个结果，每个结果恰好对应4个idx。

代码实现（Java版）：

/** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */ class Solution extends SolBase { public int rand10() { int idx; do { int a = rand7(); int b = rand7(); idx = (a - 1) * 7 + (b - 1); // 生成 [0, 48] 的均匀随机整数 } while (idx >= 40); // 拒绝采样：只接受 [0, 39] return idx % 10 + 1; // 均匀映射到 [1, 10] } }

代码实现（C++现代风格版）：假设我们有一个已实现的rand7()函数。

// 预定义的rand7() int rand7(); class Solution { public: int rand10() { std::random_device rd; std::mt19937 gen(rd()); // 注意：这里为了演示拒绝采样逻辑，我们仍然用循环。 // 在实际解题中，我们无法控制rand7()的内部引擎。 int idx; do { int a = rand7(); int b = rand7(); idx = (a - 1) * 7 + (b - 1); } while (idx >= 40); return idx % 10 + 1; } };

实操心得：在LeetCode环境中，我们无法使用外部的std::mt19937来替代rand7()，因为题目限制只能调用rand7()。这里的C++版只是为了展示在现代C++框架下的代码风格，核心算法与Java版一致。

3.3 算法性能与优化分析

• 期望调用次数：每次do...while循环需要调用2次rand7()。循环退出的概率是40/49。因此，期望的循环次数是1 / (40/49) = 49/40 = 1.225次。期望的总rand7()调用次数为2 * 1.225 = 2.45次。这已经非常高效。
• 为什么拒绝采样是高效的：它避免了像“不断累加直到范围足够大”这类可能调用次数波动很大的方法。其调用次数的数学期望是稳定且可计算的。
• 能否更优化？可以，但代码会更复杂。例如，被拒绝的idx（40-48）共9个数，它们本身也构成了一个均匀的[0,8]空间。我们可以利用这个空间，再调用一次rand7()来生成一个新的[0,48]空间的一部分，从而“榨干”每一次随机调用的价值。但这会显著增加代码复杂度，在面试中给出标准拒绝采样解法并清晰解释其期望调用次数，通常就已足够。

4. 从理论到应用：随机函数设计的常见“坑”与最佳实践

4.1 性能陷阱与并发安全

1. 避免在循环中重复创建Random对象：在Java中，new Random()本身开销不大，但如果在紧凑循环中每秒创建成千上万个，也会成为瓶颈。更严重的是，如果使用类似System.currentTimeMillis()作为种子，而在短时间内快速创建多个Random实例，它们可能会获得相同的种子，从而生成完全相同的随机序列。

   // 错误示范 for (int i = 0; i < 1_000_000; i++) { Random badRand = new Random(); // 性能差，且可能种子冲突 int num = badRand.nextInt(); } // 正确示范 Random goodRand = new Random(); for (int i = 0; i < 1_000_000; i++) { int num = goodRand.nextInt(); } // 高并发正确示范 for (int i = 0; i < 1_000_000; i++) { int num = ThreadLocalRandom.current().nextInt(); }

2. C++中random_device的跨平台问题：在C++中，std::random_device被用来获取真随机种子。但标准只规定它是一个均匀分布的随机数生成器，并未强制要求它是非确定性的（即真随机）。在一些旧编译器或特定平台上，它可能回退到伪随机实现（如用固定种子）。对于需要密码学安全的场景，这不是可靠选择。

   排查技巧：一个简单的测试方法是连续生成几个数看看是否变化，但更可靠的是查阅编译器文档。在关键应用中，可以考虑使用操作系统提供的接口（如/dev/urandomon Linux,CryptGenRandomon Windows）。

4.2 分布均匀性验证

如何验证你生成的随机数确实是均匀的？特别是自己实现了类似rand10()的函数后。一个简单的方法是进行蒙特卡洛模拟。

# 一个简单的Python验证脚本思路 import collections def my_rand10(): # 这里是你的实现，假设我们测试的是标准拒绝采样法 pass counts = collections.Counter() num_trials = 1000000 for _ in range(num_trials): counts[my_rand10()] += 1 for i in range(1, 11): prob = counts[i] / num_trials print(f"{i}: {prob:.4f} (理论值 0.1000)")

如果每个数字的概率都稳定在0.1附近，说明你的实现是均匀的。对于rand7() % 5这类不均匀的实现，你会发现某些数字的概率明显偏离0.2。

4.3 设计自己的随机函数：通用公式

遇到“用RandA()实现RandB()”这类问题，可以套用以下通用思路：

1. 扩大：用k次调用RandA()，生成一个[0, A^k - 1]范围内的均匀随机整数idx。通常k取能满足A^k >= B的最小值，以最小化单次尝试的调用次数。
2. 拒绝：如果idx落在[0, R-1]范围内，其中R是小于等于A^k且能被B整除的最大整数，则接受。否则，拒绝并重试。
3. 映射：对接受的idx，通过idx % B + 1映射到目标范围[1, B]。

期望调用次数计算：每次尝试调用k次RandA()，尝试成功的概率是R / A^k。因此期望尝试次数是A^k / R，期望的总调用次数为k * A^k / R。我们的目标就是选择合适的k，使得这个值最小。对于Rand7()到Rand10()，k=2（生成49个数）就是最优解之一。

5. 高级话题与扩展思考

5.1 非均匀分布的生成

有时我们需要生成符合特定分布（如正态分布、泊松分布）的随机数。现代库都提供了支持。

• C++：直接使用<random>库中相应的分布类，如std::normal_distribution,std::poisson_distribution。
• Java：Random类只提供均匀分布和正态分布（nextGaussian）。更复杂的分布需要借助第三方库（如Apache Commons Math）或自己实现转换算法（如Box-Muller变换生成正态分布）。

5.2 随机性与测试

随机性给单元测试带来了挑战。一个依赖于随机结果的函数，其输出是不确定的。常用的解决策略有：

1. 依赖注入：将随机数生成器作为参数传入函数，在测试时传入一个固定种子的生成器（如new Random(12345)），从而得到确定性的、可断言的结果。
2. 测试统计属性：不测试具体的输出值，而是测试其统计属性。例如，调用函数十万次，检验输出结果的分布是否与期望分布吻合（使用卡方检验等）。
3. Mock/Stub：在测试框架中，将随机函数调用替换为返回固定序列的桩函数。

5.3 游戏开发中的随机数应用

在游戏开发中，随机数不仅用于掉落、暴击，还用于AI决策、地图生成等。

• 可重复的随机：像《我的世界》这类游戏，需要根据种子生成相同的世界。这直接利用了伪随机数种子固定的特性。
• 公平性与感知公平：玩家常觉得“随机”不公平。有些游戏会采用“伪随机分布”（PRD）来调整暴击概率，使实际分布更接近玩家直觉，减少连续不暴击或连续暴击的极端情况。
• 性能：在每帧需要大量随机数的游戏（如粒子系统）中，随机数生成速度至关重要。可能会使用更轻量、周期较短的生成器，或者使用预生成的随机数表。

彻底理解随机函数，意味着你能在需要的时候精确地控制“不确定性”，而不是被它控制。从rand()到mt19937，从Random到ThreadLocalRandom，再到LeetCode上巧妙的拒绝采样，这条学习路径最终指向的是对概率、算法和系统性能的深刻把握。下次当你再看到rand()的时候，希望你能立刻想到均匀分布、拒绝采样和期望调用次数，这才是真正“玩明白了”。