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

题目要求用一个已知均匀随机的rand7()生成1~7等概率来构造rand10()生成1~10等概率。思路题目要求用均匀分布生成另一个均匀分布。1.前提rand7()可以均匀生成1234567目标是rand10()均匀生成1 ~ 10。2.不能用简单的rand7() * 10 / 7之类的方法因为它们不是均匀的会偏向某些数。举例rand7()取值1234567乘以1010203040506070除以712457810目标应该是1~10每个数的概率都为1/10结果12457810的概率为1/7369的概率为0不合题意。3.拒绝采样法利用rand7() - 1 * 7 rand7()可以生成1 ~ 49之间的等概率随机数。证明1令a rand7() - 1取值0123456均匀。2令b rand7()取值1234567均匀。3公式变成了a * 7 b。这实际上是在构造一个两位的7进制数。当a固定时a 00 * 7 b 1 ~ 7。a 11 * 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(a3) × P(b2) (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.nextInt7是生成一个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.nextInt7是生成一个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(); } }