算法刷题目其他题目
Source
Edit
History

从5随机到7随机及其扩展

从5随机到7随机及其扩展

一、题目

给定一个等概率随机产生 1 - 5 的随机函数 rand1To5。如下：

1
2
3
int rand1To5() {
	return (int)((random() * 5) + 1);
}

除此之外，不能使用任何额外的随机机制，请用 rand1To5 实现等概率随机产生 1-7 的随机函数 rand1To7

二、解析

先解决原问题，具体步骤如下：

  1. rand1To5() 等概率随机产生 1,2,3,4,5
  2. rand1To5()-1 等概率随机产生 0,1,2,3,4
  3. (rand1To5() - 1) * 5 等概率随机产生 0,5,10,15,20
  4. (rand1To5()-1)*5 + (rand1To5()-1) 等概率随机产生 0,1,2,3, ... ,23,24
  5. 如果步骤 4 产生的结果 20，则重复进行步骤 4，知道产生的结果在 0 - 20 之间。同时可以轻易知道出现 21 - 24 的概率，会平均分配到 0 - 20 上
  6. 步骤 5 会等概率随机产生 0 - 20，所以步骤 5 的结果再进行 %7 操作，就会等概率的随机产生 0 - 6
  7. 步骤 6 的结果再加 1，就会等概率随机产生 1 - 7

三、代码

1
2
3
4
5
6
7
8
9
10
public int rand1To5() {
		return (int)((Math.random() * 5) + 1);
}
public int rand1To7() {
		int num = 0;
		do {
				num = (rand1To5() - 1) * 5 + rand1To5() - 1;
		} while (num > 20);
		return num % 7 + 1;
}

四、补充问题

给定一个以 p 概率产生 0，以 1-p 概率产生 1 的随机函数 rand01p 如下：

1
2
3
4
5
public int rand01p() {
		// 可随意改变 p
		double p = 0.83;
		return Math.random() < p ? 0 : 1;
}

请用 rand01p 实现等概率随机产生 1-6 的随机函数 rand1To6

分析如下：

  1. rand01p 产生 01 和 10 的概率都是 p(1-p) 。所以可以利用这点来实现等概率随机产生 0 和 1 的函数。
1
2
3
4
5
6
7
public int rand01() {
		int num;
		do {
				num = rand01p();
		} while(num == rand01p());
		return num;
}

  1. rand01() 方法可以等概率随机产生 0 和 1，rand01()*2 等概率随机产生 0 和 2。

  2. rand01()*2 + rand01() 等概率随机产生 0,1,2,3

1
2
3
public int rand0To3() {
		return rand01() * 2 + rand01();
}
  1. rand0To3()*4 + rand0To3() 等概率随机产生 0,1,2 ... 14,15。这个就是插空的过程。
  2. 如果步骤 4 产生的结果大于 11，则重复进行步骤 4，直到产生的结果在 0 - 11 之间。那么可以知道出现 12 - 15 的概率会平均分配到 0 - 11 上。这就是筛的过程。
  3. 因为步骤 5 的结果是等概率随机产生 0 - 11，所以用第 5 步的结果再进行 %6 操作，就会等概率随机产生 0 - 5
  4. 第 6 步的结果再加 1，就会等概率随机产生 1 - 6
1
2
3
4
5
6
7
public int rand1To6() {
		int num = 0;
		do {
				num = rand0To3() * 4 + rand0To3();
		} while(num > 11);
		return num % 6 + 1;
}

五、进阶问题

进阶问题：给定一个等概率随机产生 1 - M 的随机数 rand1ToM 如下：

1
2
3
public int rand1ToM(int m) {
		return (int)(Math.random() * m) + 1;
}

除此之外，不能使用任何额外的随机机制。有两个输入参数，分别是 m 和 n，请用 rand1ToM(m) 实现等概率随机产生 1 - n 的随机函数 rand1ToN

我们会发现，只要给定某一个区间上的等概率随机函数，就可以实现任意区间上的随机函数。所以：

  • 如果 M 大于等于 N，直接进入如上筛的过程
  • 如果 M 小于 N，先进行插空，直到产生比 N 的范围还大的随机范围后，再进入筛的过程。也就是调用 K 次 rand1ToM(m)，生成有 K 位的 M 进制数，并且产生的范围大于或等于 N。再把范围扩到大于或等于 N 的级别之后，如果真实生成的数大于或等于 N，就忽略，也就是筛的过程。只留下小于或等于 N 的数，那么在 0 - N-1 上就可以做到均匀分布。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public int rand1ToM(int m) {
		return (int)(Math.random() * m) + 1;
}
public int rand1ToN(int n, int m) {
		int[] nMSys = getMSysNum(n-1, m);
		int[] randNum = getRanMSysNumLessN(nMSys, m);
		return getNumFromMSysNum(randNum, m) + 1;
}
// 把 value 转成 m 进制数
public int[] getMSysNum(int value, int m) {
		int[] res = new int[32];
		int index = res.length - 1;
		while (value != 0) {
				res[index--] = value % m;
				value = value / m;
		}
		return res;
}
// 等概率随机产生一个 0-nMsys 范围的数，只不过是 m 进制表达的
public int[] getRanMSysNumLessN(int[] nMSys, int m) {
		int[] res = new int[nMSys.length];
		int start = 0;
		while (nMSys[start] == 0) {
				start++;
		}
		int index = start;
		boolean lastEqual = true;
		while (index != nMSys.length) {
				res[index] = rand1ToM(m) - 1;
				if (lastEqual) {
						if (res[index] > nMSys[index]) {
								index = start;
								lastEqual = true;
								continue;
						} else {
								lastEqual = res[index] == nMSys[index];
						}
				}
				index++;
		}
		return res;
}
// 把 m 进制数转成十进制数
public int getNumFromMSysNum(int[] mSysNum, int m) {
		int res = 0;
		for (int i = 0; i != mSysNum.length; i++) {
				res = res * m + mSysNum[i];
		}
		return res;
}