随机函数是平时刷题练习时验证正确性的比较灵魂的方法。
java中提供了Math.random()函数：返回一个[0~1)等概率的一个double类型的值。
1、验证代码
package com.yubin.algorithms;
/**
* 介绍随机函数的使用
* @author YUBIN
* @create 2021-03-13
*/
public class Code0007_RandToRand {
public static void main(String[] args) {
// 验证Math.random()函数[0,1)是等概率的
int testTimes = 10000000;
int count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() < 0.75) { // 其概率应该约等于0.75
count++;
}
}
System.out.println((double)count / (double)testTimes);
System.out.println("===========================");
// [0,1)*8 => [0,8)
count = 0;
for (int i = 0; i < testTimes; i++) {
if (Math.random() * 8 < 5) { // 其概率应该约等于 5/8=0.625
count++;
}
}
System.out.println((double)count / (double)testTimes);
System.out.println("===========================");
int k = 9;
// [0,k) 相当于 [0,l-1]
int[] counts = new int[k];
for (int i = 0; i < testTimes; i++) {
int ans = (int) (Math.random() * k);
counts[ans]++;
}
for (int i = 0; i < k; i++) {
System.out.println(i + "这个数,出现了" + counts[i] + "次");
}
System.out.println("===========================");
}
}
2、题目一：如何利用Math.random()函数，把得到[0,x)范围上的数的概率从x调整成x2
题目分析：经过上面的验证Math.random()随机函数[0,1)范围上概率是相等的，对应的0 ~ x范围的概率就是x，那么如何让0 ~ x的概率变成x2呢？
利用Math.max(Math.random(), Math.random())
Math.max(a1,a2); 只有当a1和a2两个值都在0 ~ x范围内的时候值才会在0 ~ x范围内，这样[0,x)的概率就变成x2了。
private static double xToPower2() {
return Math.max(Math.random(), Math.random());
}
注意：如果这里改成Math.min()函数的话，概率就变成 1-(1-x)2
3、题目二：从1 ~ 5随机到1 ~ 7随机
题目分析：程序中已提供一种1 ~ 5的随机是等概率的方法，如何利用该函数实现1 ~ 7的随机是等概率的。
其实这个题目有一个限制就是1~7的等概率随机数不能使用 (int)(Math.random()*7)+1的方式，只能使用现成的方法。
思路：
已知函数是等概率返回[1,5]的整数
那么1,2,3,4,5的概率分别是20%， 如果我使用1和2 表示0; 4和5表示1 当遇到3的时候再次随机即将得到3的概率分摊到其它4个数上面,此时得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%。
通过[1,5]等概率函数可以得到一个0,1等概率函数，然后再利用二进制的方式可以拿到一个0 ~ 7的等概率函数
000,001,010,011,100,101,110,111。 因为7这个数至少需要3位来表示。
代码实现：
/**
* 返回[1,5]的等概率随机数
* 假设该方法是lib里面,不能修改
* @return
*/
private static int f1() {
return (int) (Math.random() * 5) + 1;
}
/**
* 随机机制,等概率返回0和1 只能使用f1函数
* 分析 f1函数是等概率返回[1,5]的整数
* 那么1,2,3,4,5的概率分别是20%， 如果我使用1和2 表示0; 4和5表示1 当遇到3的时候再次随机即将得到3的概率分摊到其它4个数上面,
* 此时得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%
*
* @return
*/
private static int f2() {
int ans = 0;
do {
ans = f1();
} while (ans == 3);
return ans < 3 ? 0 : 1;
}
// 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个 每一个数的概率是1/8
private static int f3() {
return (f2() << 2) + (f2() << 1) + (f2() << 0);
}
// 0 ~ 6等概率返回一个
private static int f4() {
int ans = 0;
do {
ans = f3();
} while (ans == 7);
return ans;
}
// 1 ~ 7等概率返回一个
private static int g() {
return f4() + 1;
}
同理：从a ~ b随机到c ~ d随机这个题目也可以使用上面这个方法来实现。
将a ~ b变成01等概率发生器 ，将c ~ d变成0 ~ (d-c) 这时再看d-c需要几个二进制位, 同时如果超过d-c部分的重做即可
4、题目三：01不等概率随机到01等概率随机
分析：01不等概论，但是可以知道0和1是固定概率的，这样的话我们使用两位来表示
00，01，10，11
这每个数出现的概率都是第一位的概率 * 第二位的概率， 而已知的函数0和1虽然概率不一样但是0的概率*1的概率是一样的，这样01,10就是等概率的了， 使用01表示0，10表示1，其它情况重做即可，这样最后就能得到一个01的等概率随机。
代码实现：
// 已知的01不等概论函数，但是0和1的概率是固定的
private static int x() {
return Math.random() > 0.84 ? 0 : 1;
}
// 通过x函数得到01的等概率随机
private static int y() {
int ans = 0;
do {
// 第一次调用x函数
ans = x();
} while (ans == x()); // 第二次调用x函数 两次返回的结果不一样则说明要么是01 要么是10
return ans;
}
