用rand7()函数构造函数rand10()

题目要求：用一个已知均匀随机的rand7()（生成1~7等概率）来构造rand10()（生成1~10等概率）。

思路：题目要求用均匀分布生成另一个均匀分布。

1.前提：rand7()可以均匀生成1，2，3，4，5，6，7，目标是rand10()均匀生成1 ~ 10。

2.不能用简单的（rand7() * 10 / 7）之类的方法，因为它们不是均匀的（会偏向某些数）。

举例：

rand7()取值：1，2，3，4，5，6，7

乘以10：10，20，30，40，50，60，70

除以7：1，2，4，5，7，8，10

目标应该是1~10每个数的概率都为1/10，结果1，2，4，5，7，8，10的概率为1/7，3，6，9的概率为0，不合题意。

3.拒绝采样法：利用（rand7() - 1） * 7 + rand7()可以生成1 ~ 49之间的等概率随机数。

证明：

（1）令a = rand7() - 1，取值：0，1，2，3，4，5，6（均匀）。

（2）令b = rand7()，取值：1，2，3，4，5，6，7（均匀）。

（3）公式变成了a * 7 + b。这实际上是在构造一个两位的7进制数。

当a固定时：

a = 0：0 * 7 + b = 1 ~ 7。

a = 1：1 * 7 + b = 8 ~ 14。

a = 2： 2 * 7 + b = 15 ~ 21。

a = 3： 3 * 7 + b = 22 ~ 28。

a = 4： 4 * 7 + b = 29 ~ 35。

a = 5： 5 * 7 + b = 36 ~ 42。

a = 6： 6 * 7 + b = 43 ~ 49。

完美覆盖了1 ~ 49的所有整数。

之所以a * 7 + b这样构造是均匀的，是因为a和b是独立的随机变量，也就是两次独立的rand7()调用。概率计算：P(得到某个特定数 x) = P(a = 某值) × P(b = 某值)。实际上是在做笛卡尔积。通过(a'-1)*7 + b映射到 1~49，这是一个双射（一一对应），所以分布保持均匀。

举例：

P(得到23) = P(a=3) × P(b=2) = (1/7) × (1/7) = 1/49

任何1 ~ 49的数都能唯一表示为a * 7 + b的形式，所以每个数的概率都是1/49。

4.（rand7() - 1） * 7 + rand7()生成等概率随机数的步骤。从1 ~ 49中只取1 ~ 40的数字（映射到1 ~ 10），遇到41 ~ 49则重试。这是因为转换为rand10()的话，最大概率是将1 ~ 49分成10组，每组4个数（但49不是10的倍数），因此必须让num落在1 ~ 40范围内才有用，否则丢弃重新生成，保证1 ~ 10均匀。

附代码：

class Solution { private Random random = new Random(); // 假设提供的 rand7() 是均匀的 private int rand7() { // random.nextInt（7）是生成一个0到6之间的随机整数（包含0，不包含7） //random.nextInt(7) + 1就是生成一个1到7之间的随机整数 return random.nextInt(7) + 1; } public int rand10() { while (true) { int num = (rand7() - 1) * 7 + rand7(); // 1 ~ 49 均匀 if (num <= 40) { // 将1 ~ 40的数映射到1 ~ 10 // 如果是num % 10，那么1 % 10 + 1 = 2，映射错误，所以是(num - 1) % 10 // 要求返回1 ~ 10，而不是0 ~ 9，所以应该 + 1，不加1的映射范围是0 ~ 9 return (num - 1) % 10 + 1; // 如果 num = 41~49，则丢弃，重新生成 } } } }

ACM模式：

import java.util.Random; import java.util.Scanner; class Solution { private Random random = new Random(); // 假设提供的 rand7() 是均匀的 private int rand7() { // random.nextInt（7）是生成一个0到6之间的随机整数（包含0，不包含7） //random.nextInt(7) + 1就是生成一个1到7之间的随机整数 return random.nextInt(7) + 1; } public int rand10() { while (true) { int num = (rand7() - 1) * 7 + rand7(); // 1 ~ 49 均匀 if (num <= 40) { // 将1 ~ 40的数映射到1 ~ 10 // 如果是num % 10，那么1 % 10 + 1 = 2，映射错误，所以是(num - 1) % 10 // 要求返回1 ~ 10，而不是0 ~ 9，所以应该 + 1，不加1的映射范围是0 ~ 9 return (num - 1) % 10 + 1; // 如果 num = 41~49，则丢弃，重新生成 } } } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 需要生成多少个随机数 Solution sol = new Solution(); for (int i = 0; i < n; i++) { System.out.print(sol.rand10()); if(i < n - 1){ System.out.print(" "); } } System.out.println(); scanner.close(); } }