文章目录
1. 关于Math.random()函数
Java 中 Math.random() 函数是等概率返回区间 [0,1) 中的任意一个浮点数, 即 x < 1 情况下, 调用这个api, 得到 [0,x) 范围上的数的概率就是 x; 那么, 如果想要将 x < 1 情况下, 生成的[0,x) 范围上的数的概率调整成 x ^ 2, 应该怎么实现?
- 实现思路:
由于生成 [0,x) 的概率是 x , 那么调用两次 Math.random(), 得到的两个值中, 如果较大的那个值也在[0,x)区间内, 那么此时两次调用生成 [0,x) 范围上的数字的概率就为 x ^ 2了; 要注意这两次调用都必须在 [0,x) 区间内 (因为任意一次在 [x,1) 都会导致返回值不在 [0,x) 上).
- 代码实现:
/**
* rangom 函数生成的任意一个随机数都在 [0,1) 范围内,
* 这个函数让 [0, x) 范围上出现的数字概率由原来的 x 调整为 x^2
*/
public static double xToXPower2() {
// 调用两次,取到两次的的最大值,这样要想得到[0, x)范围内值就需要两次调用都在范围内
// 一次得到的概率是x, 那么两次都要得到范围内的值的概率就是 x^2;
return Math.max(Math.random(), Math.random());
}
- 测试代码:
public static void main(String[] args) {
// 测试次数
int testTimes = 10000000;
// random函数的测试
int count = 0;
double x = 0.27;
for (int i = 0; i < testTimes; i++) {
if (xToXPower2() < x) {
count++;
}
}
// 以下两个数值应该大小接近一致
System.out.println(count / (double) testTimes);
System.out.println(Math.pow(x, 2));
}
- 测试结果:
可以看到结果是相近的.
2. 用1 ~ 5的随机函数加工出1 ~ 7的随机函数
假设我们有一个随机函数 f(), 这个函数可以等概率返回 [1,5] 中的一个数, 请实现只利用 f() 函数而不引入其他随机函数, 得到一个等概率返回 [1,7] 中任意一个数的函数.
- 实现思路:
假设实现的目标函数为 c(), 由于目标是求 [1,7] 等概率返回一个, 如果我们能加工得到一个b()函数, 这个函数是等概率返回 [0,6] 范围内的任意一个数, 那么目标函数 c() 只需要调用这个 b() 函数再加上 1, 就可以等概率返回 [1,7] 中任意一个数, 即 c() 函数.
// 等概率返回 [1,7] 中任意一个数
public static int c() {
// b()函数是等概率返回 [0,6] 中的任意一个数
// 在获取b()的基础上再加1就是等概率返回1~7了
return b() + 1;
}
接下来问题就变成了 b() 这个函数的实现, 要实现 [0,6] 等概率返回一个数, 思路如下:
先得到一个 0 和 1 等概率返回的随机函数 a(),
可以通过题目中给的 f() 函数来加工得到 a(),
f() 是 [1,5] 等概率返回的一个数, 也就是说, 调用 f() 会等概率返回 1,2,3,4,5 中的一个数, 我们约定,
当调用 f(), 得到 1 或者 2 的时候, 返回 0;
当调用 f(), 得到 4 或者 5 的时候, 返回 1;
当调用 f(), 得到 3 的时候, 什么都不返回, 再次调用 f().
代码如下:
// 利用[1,5]随机函数f() 生产等概率返回 0 和 1 的函数 a()
public static int a() {
// 约定拿到1和2就代表0, 拿到4和5就代表1
// 拿到的是3就重新获取
int answer = 0;
do {
answer = f();
} while (answer == 3);
return answer < 3 ? 0 : 1;
}
这样就得到了 0 和 1 等概率返回的随机函数a(),
由于 6 的二进制表示是 110, 所以区间 [0,6] 的所有整数只需要 3 个二进制位就可以表示,
调用三次 a() 函数, 就可以等概率得到 [0,7] 范围内任意一个数 (因为区间[0,7]用二进制表示就是 000~111)，即 [0,1,2,3,4,5,6,7] 等概率返回一个，
在得到 7 的时候, 重试上述过程, 只有结果在 [0,6] 才返回, 这样就加工出了 b() 函数, 即等概率返回 [0,6].
// 再利用a()生产能等概率拿到0到6的函数
public static int b() {
// 三个二进制位就可以表示最大为6的数 (M N Y)
int ans = 0;
do { //
ans = (a() << 2) // 得到 M
+ (a() << 1) // 得到 N
+ a(); // 得到 Y
} while (ans == 7);
return ans;
}
最后, 目标函数 c() 通过如下方式得到:
// 在获取b()的基础上再加1就是等概率返回1~7了
public static int c() {
return b() + 1;
}
- 完整代码实现:
/**
* 使用1~5的随机函数加工出1~7的随机函数
*/
// 这个函数是等概率返回1~5的函数,只能使用,不能修改
public static int f() {
// (int)[0,5) -> [0,4] -> +1 -> [0,5]
return (int)(Math.random() * 5) + 1;
}
// 利用[1,5]随机函数f() 生产等概率返回 0 和 1 的函数 a()
public static int a() {
// 约定拿到1和2就代表0, 拿到4和5就代表1
// 拿到的是3就重新获取
int answer = 0;
do {
answer = f();
} while (answer == 3);
return answer < 3 ? 0 : 1;
}
// 再利用a()生产能等概率拿到0到6的函数
public static int b() {
// 三个二进制位就可以表示最大为6的数 (M N Y)
int ans = 0;
do { //
ans = (a() << 2) // 得到 M
+ (a() << 1) // 得到 N
+ a(); // 得到 Y
} while (ans == 7);
return ans;
}
// 在获取b()的基础上再加1就是等概率返回1~7了
public static int c() {
return b() + 1;
}
- 测试代码:
测试 10000000 次, 每次记录随机生成的数字, 得到每个数字出现的次数
public static void main(String[] args) {
// 测试次数
int testTimes = 10000000;
// random函数的测试
int count = 0;
int[] counts = new int[8];
for (int i = 0; i < testTimes; i++) {
int num = c();
counts[num]++;
}
System.out.println(Arrays.toString(counts));
}
- 执行结果:
可以看到 1 到 7 这些数字出现的次数都差不多, 接近等概率.
和问题一的思想一样, f() 函数是等概率函数, 那么将 f() 多次调用得到的结果一样是等概率的, 调用 7 次 f() 相加, 得到的结果 % 7以后, 最后得到的一定是等概率返回 0~6 中任意一个整数的, 再加1, 就变成等概率返回 1~7 任意一个.
public static int g2() {
return (f() + f() + f() + f() + f() + f() + f()) % 7 + 1;
}
3. LeetCode 470. 用 Rand7() 实现 Rand10()
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数, 试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数; 你只能调用 rand7() 且不能调用其他方法, 请不要使用系统的 Math.random() 方法.
在线OJ: LeetCode 470. 用 Rand7() 实现 Rand10()
- 实现思路:
思路上面基本一致, 核心都是要先实现一个等概率返回 0 和 1 的随机函数 f(), 然后看目标函数区间需要几个二进制位, 来决定调用几次 f() 函数.
- 代码实现:
/**
* 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 {
// 核心: 生成 0 和 1 等概率返回的随机函数
public int f() {
int val = rand7();
while (val == 7) {
val = rand7();
}
return (val <= 3) ? 0 : 1;
}
public int rand10() {
int num = 0;
do {
num = 0;
// 10 最多用4个二进制位表示即可
for (int i = 0; i < 4; i++) {
num += (f() << i);
}
} while (num < 1 || num > 10);
return num;
}
}
此外, 本题还有另外一种解法, 由 10 个 rand7() 之和得到的值 % 10 以后, 得到的一定是等概率返回 [0,9] 中的一个数, 再加 1, 就是等概率返回[1,10]了, 代码如下:
public int rand10() {
return (rand7() + rand7() + rand7() + rand7() + rand7() + rand7() +
rand7() + rand7() + rand7() + rand7()) % 10 + 1;
}
4. 把不等概率随机函数变成等概率随机函数
有一个函数 x(), 不等概率 (但是是固定概率) 返回 0 和 1, 如何只通过 f() 函数, 得到等概率返回 0 和 1 的随机函数?
- 实现思路:
调用两次 x() 函数, 可以得到如下情况
情况1：0 0
情况2：1 1
情况3：0 1
情况4：1 0
当两次都是 0, 或者两次都是 1 的时候, 即情况 1 和 情况 2, 就舍弃, 这样虽然 0 和 1 的概率不一样, 但是通过两次调用, 得到即情况 3 (0, 1)和 情况 4 (1, 0) 的概率一定是相同的, 所以我们可以约定,
所以, 我们可以约定, 两次调用得到的结果是 0 1 就返回 0, 得到的是 1 0就返回 1.
- 代码实现:
public class Code_0003_EqualProbabilityRandom {
// 不等概率函数，
// 内部内容不可见
public static int f() {
return Math.random() < 0.8 ? 0 : 1;
}
// 等概率返回0和1
public static int g() {
int first;
do {
first = f(); // 0 1
} while (first == f());
return first;
}
public static void main(String[] args) {
final int testTimes = 10000000;
// count[0] 统计0出现的次数
// count[1] 统计1出现的次数
int[] count = new int[2];
for (int i = 0; i < testTimes; i++) {
count[g()]++;
}
System.out.println("0 出现的次数:" + count[0]);
System.out.println("1 出现的次数:" + count[1]);
}
}
/**
* 提供当0和1以不同的概率返回, 设计函数让0和1以等概率返回
*/
public static int x() {
return Math.random() < 0.66 ? 0 : 1;
}
// 等概率返回0和1
public static int y() {
// 两次获取01或者10就是等概率的
// 两次获取到11或者是00就是不等概率的,舍弃
int ans = 0;
do {
ans = x();
} while (ans == x());
return ans;
}
- 测试代码:
调用 10000000 次, 记录 1 和 0 出现的次数.
public static void main(String[] args) {
// 测试次数
int testTimes = 10000000;
int[] arr = new int[2];
for (int i = 0; i < testTimes; i++) {
int num = y();
arr[num]++;
}
System.out.println(Arrays.toString(arr));
}
测试结果:
可以看到 1 和 0 实际出现的次数差不多, 是接近等概率的.
5. 用a ~ b的随机函数加工出c ~ d的随机函数
如何用一个生成区间 a ~ b 的随机函数加工生生产出成 c ~ d 的随机函数.
- 实现思路:
核心思路与前面的问题是一样的, 都是构造等概率生成 0 和 1 的 rand() 函数, 然后通过 rand()函数加工出随机生成 c ~ d 的函数.
假设生成区间 a ~ b 的随机函数是f(a,b),
如果 a ~ b 的区间元素个数是偶数, 那么将区间分两半, 如果得到的是前面一半的数, 则返回 0; 如果得到后面一半的数, 则返回 1；
如果 a ~ b 的区间元素个数是奇数, 那么把将区间分两半, 如果得到的是前面一半的数, 则返回 0; 如果得到后面一半的数, 则返回 1; 得到中间位置的数, 则舍弃, 然后继续调用；
这样一来, 就加工出一个等概率随机生成 0 或 1 的函数 rand(), 然后就要判断要表示 1 ~ d - c + 1 这个范围的的值需要几个二进制(让 1<<i - 1 到大于范围即可), 不过由于这里的 c,d 并不是确定的值, 无法计算得到准确所需需要的二进制位数, 不过并不影响结果, 得到结果后判断结果是不是在范围内, 不在的话接着重新调用获取即可, 这样就可以得到随机生成 c ~ d 的函数了.
- 代码实现:
// 构造一个等概率返回a~b的随机函数
public static int f(int a, int b) {
// Math.random() -> [0, 1)
// [a, b] -> a + [0,b-a] -> a + (int)(Math.random() * (b-a+1))
return a + (int) (Math.random() * (b - a + 1));
}
// 要根据f()加工出等概率返回0和1的随机函数
public static int rand(int a, int b) {
// a = 4, b = 8
// countNum = 5
int countNum = b - a + 1; // 可能出现的随机数的个数
// isOdd = true
// 是否为奇数个
boolean isOdd = countNum % 2 != 0;
int midNum = (a + b) / 2;
int ans;
do {
// 如果是奇数, 那么中点位置弃用, < 中点 位置 和 > 中点位置的数字返回概率一样, 一个定为0, 一个定为1
// 如果是偶数, 那么这里的中点是上中点, < 上中点 位置 和 >= 上中点位置的数字出现的概率一样, 一个定为0, 一个定为1即可
ans = f(a, b);
} while (isOdd && ans == midNum);
// 如果是偶数，ans可能会等于midNum
// 如果是奇数，ans必不等于midNum
return ans <= midNum ? 0 : 1;
}
// 加工出等概率返回c~d的随机函数
public static int g(int a, int b, int c, int d) {
int range = d - c; // 0～range + c~d -> c~d
int count = 1;
while ((1 << count) - 1 < range) { // 求0～range需要几个2进制位
count++;
}
int ans;
do {
ans = 0;
for (int i = 0; i < count; i++) {
ans += (rand(a, b) << i);
}
// 要注意这里的实现, 由于这里 c,d 是随机给出的, 也就不好准确计算出所需要的进制位
// 所以, 要判断最终的结果是不是在范围内, 不在的话要重新调用获取
} while (ans > range);
return ans + c;
}
- 测试代码:
public static void main(String[] args) {
// 测试次数
int testTimes = 10000000;
int[] array = new int[20];
for (int i = 0; i < testTimes; i++) {
int num = g(3, 19, 20, 39);
array[num-20]++;
}
System.out.println(Arrays.toString(array));
}
- 测试结果:
可以看到每个数实际出现的次数是差不多的, 接近等概率.