使用 Rand7() 实现 Rand10()（C++）

随机数生成是大多数算法和应用程序的基本组成部分，从简单的模拟到 加密 应用。很多时候，我们可能会遇到现有随机数生成器不足的情况。例如，假设 Rand7() 是一个生成 {1, 2, 3, 4, 5, 6, 7} 集合中均匀随机整数的现有函数。然而，解决特定任务需要创建 Rand10()，它是一个仅范围在 1 到 10 的随机整数。这个问题看似简单，但要保证游戏的公平性，即保证 10 种可能结果的概率相等，并非易事。

用 Rand7() 来定义 Rand10() 不仅是一个编程问题，也是深入了解随机性本质以及一种随机分布如何转化为另一种随机分布的绝佳机会。这个问题通常出现在技术面试和编程竞赛中，既作为理论问题也作为实践问题。

Rand7() 在生成随机数方面的最大难点在于它只有七种不同的结果，并且所有结果的概率都相同。因此，另外三种结果也必须独立且均匀地选择，以便能够均匀地选择 1 到 10 之间的数字。这是一个需要认真对待的重要方面，并且需要一种方法来以平等的标准实现这两个范围之间的匹配。

在这篇文章中，我们将讨论这个问题，回顾解决问题背后的 数学 概念，然后逐步描述在 C++ 中实现的解决方案。首先，我们将考虑问题及其所有特殊性，然后考虑有助于找到解决方案的思维方式。最后，我们将对解决方案进行离散化，使代码既高效又正确。在本文结束时，您不仅将获得 Rand10() 的实现，还将理解生成随机数的原理及其在计算机科学领域的重要性。

理解问题

为了理解这个问题，让我们首先详细了解 Rand7() 函数。此函数返回 1 到 7 范围内的随机整数，并且该范围内的每个值都是可能的。换句话说，数学上，获得任何特定数字（假设为 x，其中 x 是介于 1 和 7 之间的整数）的概率是 P(x) = 1/7。

现在让我们来讨论需要创建的 Rand10() 函数。顾名思义，此函数应生成一个介于 1 到 10 之间（包括 1 和 10）的整数，并且该函数的每个整数结果都应具有相等的概率 p(y) = 1/10。这里的任务是仅使用 Rand7() 来获得 Rand10()，同时保持 1 到 10 的数字概率相等。

核心问题在于 Rand7() 产生七个结果，而 Rand10() 需要十个结果。换句话说，没有一种方法可以将 Rand7() 的七个结果映射到 Rand10() 所需的十个结果，同时避免偏差。原始意图是将 7 个结果映射到 Rand7() 的 10 个可能结果。如果将得到的结果移至 1:10 的范围，则某些数字将被过度近似，这将违反等密度规则。

为了解决这个问题，我们必须开始使用更多的潜在结果，以便可以将 1 到 10 的数字均匀地等同起来。所使用的技术之一是通过汇总 Rand7() 的调用结果，以获得更大的结果范围。因此，如果我们调用两次 Rand7()，我们可以得到一个介于 1 到 49 之间的数字集合（因为 7*7=49）。这个足够大的范围提供了比随机过程潜在结果更多的数字变化，我们可以使用模运算和拒绝采样来使随机数在 1 到 10 的数字范围内均匀分布。

编码

输出

 
Distribution of numbers generated by Rand10() over 1000000 trials: 
1: 100064 times (10.0064%) 
2: 99954 times (9.9954%) 
3: 100095 times (10.0095%) 
4: 99836 times (9.9836%) 
5: 100076 times (10.0076%) 
6: 100145 times (10.0145%) 
7: 99965 times (9.9965%) 
8: 100074 times (10.0074%) 
9: 100128 times (10.0128%) 
10: 99663 times (9.9663%)    

说明

• Rand7() 函数： Rand7() 函数模拟一个从 1 到 7 生成随机数的函数，作为种子的可能表示。它使用 C++ 的 rand() 函数，该函数生成一个随机整数。这意味着 rand() % 7 + 1 表达式可确保表达式的结果在 1 到 7 之间。
• Rand10() 实现： 激活 Rand10() 函数，它会生成更多样化的后续方案，因为它会调用两次 Rand7()。这些调用以 7x7 矩阵的方式模拟，其中行号加上列号会产生介于 1 到 49 之间的“幸运”数字。这是通过转换公式 (row - 1) * 7 + col 实现的，该公式将二维对 (row, col) 映射到一个唯一的数字。
• 拒绝采样： 鉴于 49 个结果不能被 10 个可能结果整除，因此必须采用拒绝采样。输入的数字必须在 1 到 40 之间，因为只有这样它才能被 10 整除。如果生成的数字大于 40，则将其拒绝，并生成另一个数字，直到生成正确的数字为止。
• 映射到 1-10 的范围： 最后，要获得一个范围在 1 到 10 之间的值，可以使用公式 (num - 1) % 10 + 1。它在数据集中保持适当的总体方差，以在所需范围内提供均匀分布。
• 随机数生成器播种： 在此之前，使用 srand(time(0)) 设置随机数生成器，以便每次运行程序时都能生成不同的随机序列。
• 样本生成和计数： 创建的程序使用 Rand10() 函数生成 1,000,000 个样本。之后，它遍历 1 到 10 的数字，计算范围内有多少数字符合条件，并将计数存储在 counts 数组中。

结论

总之，如何使用 Rand7() 实现 Rand10() 的问题是元数学和随机分布转换实际应用的又一个例子。该解决方案还基于多次获得 Rand7() 的总体可能性变化，并使用拒绝采样作为一种有助于使值范围更加多样的技术。通过仔细将结果缩放到 1 到 10 的范围，该方法确保所有数字都具有相同的概率。这种方法不仅能够解决特定问题，还能通过利用数学思维和算法方法的强大功能来获得均匀性，从而对如何处理随机化和类似问题提供更深入的理解。