1.验证Math.random()的等概率性
我们知道Math.random()是等概率返回[0,1)随机数，来一起验证下。
public static void getRandom(){
/**
* todo 测试random方法是不是等概率随机的
* 结果测定，是等概率的
*/
int testTimes = 10000000;
int count = 0;
double ans;
for(int i = 0; i < testTimes; i++){
//[0,1)
ans = Math.random();
if(ans < 0.5){
count ++;
}
}
System.out.println(count);
System.out.println("测试随机数是不是等概率出现的，测一下小于0.5得数出现的概率是多少: " + (double)count / (double)testTimes);
}
//输出结果
5000803
测试随机数是不是等概率出现的，测一下小于0.5得数出现的概率是多少: 0.5000803
我们可以看到大量测试后，发现[0,0.5)的概率大约是0.5，当然这个数值可以随便修改进行测试，都是一样的。
2. 随机数Math.random()的进阶
我们都知道Math.random()可以返回[0,1)中的任意数，那我想随机返回[0,10)的数据呢？没错，乘以10。
int result = Math.random()*10;
那我们如何验证[0,10)之间的等概率性呢，我们验证一下[0,10) 的int类型的数据是不是等概率返回的。
/**
* todo 测定修改为任意随机数，暂定修改为[0,10)
*
*/
int[] counts = new int[10];
int ans1;
for(int i = 0; i < testTimes; i++){
//[0,10)
ans1 = (int)(Math.random() * 10);
counts[ans1] ++;
}
for(int i = 0; i< 10; i++){
System.out.println("测试数据ans1 "+ i + " 出现了: " + counts[i] + " 次");
}
//输出结果
测试数据ans1 0 出现了: 999458 次
测试数据ans1 1 出现了: 999601 次
测试数据ans1 2 出现了: 999948 次
测试数据ans1 3 出现了: 1000671 次
测试数据ans1 4 出现了: 1001815 次
测试数据ans1 5 出现了: 998365 次
测试数据ans1 6 出现了: 999731 次
测试数据ans1 7 出现了: 999684 次
测试数据ans1 8 出现了: 999788 次
测试数据ans1 9 出现了: 1000939 次
可以看出来各个数字出现的次数相差无几，还是等概率的。
[0,10)是 Math.random()*10得到的，举一反三，加一个数还可得，[1, 11),[2,12)等等。
假如我在[0,1)上有一个x,我想得到x平方该怎么做呢？
思路：我们可以有两次随机取值，这两次随机取值都是x, 是不是就是x平方
//任意的x,x属于[0,1),概率由原来的x 得到x平方
public static double getXToTwo(){
/**
* @ 只有max才能求得x方
*/
return Math.max(Math.random(), Math.random());
//求得不是x方，而是最大落在[0,x)的概率，并不是x方
// return Math.min(Math.random(), Math.random());
}
第一次的Math.random()得到x, 第二次Math.random()得到x，取最大值，是不是就是x平方呢。我们可以验证一下。
count = 0;
double x = 0.4;
for(int i = 0; i < testTimes; i++){
double xToTwo = getXToTwo();
if(xToTwo < x){
count ++;
}
}
System.out.println((double) count/ (double) testTimes);
System.out.println("测试随机数是不是等概率出现的，测一下小于0.4的平方的数出现的概率是多少: " + Math.pow(x, 2));
//输出结果
0.1600108
测试随机数是不是等概率出现的，测一下小于0.4的平方的数出现的概率是多少: 0.16000000000000003
可以看到，当我调用了上述的求x平方的函数时，我假设x是0.4，求得x的平方大约是0.16多，和我们调用函数Math.pow(x,2)求平方是差不多的。以此类推，我想求得x的3次方，调用三次Math.random()方法，求得最大值小于x，即可得到x的3次方。
return Math.max(Math.random(), Math.max(Math.random(),Math.random()));
3.关于随机函数的经典面试题
A. 函数f()等概率返回1～5，在不改变f()函数内部的前提下，如何获得1～7的等概率返回函数g()？
大致思路：
- 1～5等概率返回，那可以利用f()函数改造一个等概率返回0和1的函数f0();
- f0()函数等概率返回0和1，利用二进制转换的逻辑，使f0()函数完成一个等概率返回000～111的函数f1()；
- 二进制转换000～111即0～7，f1()函数等概率返回0～7，要想获得等概率返回1～7的函数g()，此时有两种思路均可;
- 直接获得，f1()等概率返回0～7时，如果是0，就重新返回，即可得到等概率返回1～7的函数g();
- 间接获得，f1()等概率返回0～7时，如果是7，就重新返回，即可得到等概率返回的0～6的函数f2(); 对f2()函数进行加1 的操作就可得到g()函数。
以上就是等概率获取1～7的所有思路，接下来，详细解释和代码编写。
第一步
- 利用f()函数改造一个等概率返回0和1的函数f0();
f()函数等概率返回1，2，3，4，5；假定
f()函数返回1,2 => f0()函数返回0
f()函数返回3 => 重来
f()函数返回4,5 => f0()函数返回1
这样的话，fo()函数可等概率的返回0和1。看看代码：
//f函数，表示等概率的返回1～5
public static int f(){
return (int)(Math.random()* 5 + 1);
}
//使用f进行封装处理，得一个等概率获取0，1的函数f0
public static int f0(){
int ans;
do{
ans = f();
}while (ans == 3);
//方法是1,2-> 0, 4,5-> 1, 3重新进入循环，那么该方法就会等概率得到0，1
return ans < 3 ? 0 : 1;
}
第二步
- f0()函数等概率返回0和1，利用二进制转换的逻辑，使f0()函数完成一个等概率返回000～111的函数f1()；
(f0()<< 2) + (f0() << 1) + (f0() << 0) 可等概率返回000～111之间的数，代码如下：
//使用f0方法得到等概率返回0～7的方法f1
//使用的是二进制表示，000～111 表示0～7
public static int f1(){
int ans = (f0() << 2) + (f0() << 1) + f0();
return ans;
}
第三步
- 二进制转换000～111即0～7，f1()函数等概率返回0～7，要想获得等概率返回1～7的函数g()，此时有两种思路均可;
1. 直接获得，f1()等概率返回0～7时，如果是0，就重新返回，即可得到等概率返回1～7的函数g();
//使用f1方法得到等概率返回1～7的方法g()
//f1等概率返回0～7 ，那么遇到0重来，就会得到1～7
public static int g(){
int ans;
do {
ans = f1();
}while(ans == 0);
return ans;
}
- 间接获得，f1()等概率返回0～7时，如果是7，就重新返回，即可得到等概率返回的0～6的函数f2(); 对f2()函数进行加1 的操作就可得到g()函数。
//第二种方法，先根据f1方法得到等概率0～6的方法f2()
//f1等概率返回0～7，那么遇到7重来，就可以得到0～6
public static int f2(){
int ans;
do{
ans = f1();
}while (ans == 7);
return ans;
}
//基于f2()方法得到1～7 的方法g()
public static int g(){
return f2() + 1;
}
至此，这道题已经解决了，我们测试一下g()方法。
//测试第一个g()方法是否会等概率返回1~7
int[] count4 = new int[8];
for(int i = 0; i < testTimes; i++){
int ans2 = g();
count4[ans2] ++;
}
for(int i = 1; i< 8; i++){
System.out.println("测试数据ans1 "+ i + " 出现了: " + count4[i] + " 次");
}
//输出结果
测试数据ans1 1 出现了: 1428448 次
测试数据ans1 2 出现了: 1427468 次
测试数据ans1 3 出现了: 1427696 次
测试数据ans1 4 出现了: 1429870 次
测试数据ans1 5 出现了: 1426945 次
测试数据ans1 6 出现了: 1429856 次
测试数据ans1 7 出现了: 1429717 次
第一个g()方法测试结果可以看出来1~7是等概率返回的。
现在调第二个g()方法测试一下结果是否等概率返回1～7
//测试g是否会等概率返回1~7
int[] count6 = new int[8];
for(int i = 0; i < testTimes; i++){
int ans2 = g();
count6[ans2] ++;
}
for(int i = 1; i< 8; i++){
System.out.println("测试数据ans1 第二个方法 "+ i + " 出现了: " + count6[i] + " 次");
}
//输出结果
测试数据ans1 第二个方法 1 出现了: 1427601 次
测试数据ans1 第二个方法 2 出现了: 1429933 次
测试数据ans1 第二个方法 3 出现了: 1428051 次
测试数据ans1 第二个方法 4 出现了: 1428761 次
测试数据ans1 第二个方法 5 出现了: 1430342 次
测试数据ans1 第二个方法 6 出现了: 1428077 次
测试数据ans1 第二个方法 7 出现了: 1427235 次
测试结果与预期结果相同，两种获取等概率1～7的方法g()都没有问题。
B.f()函数等概率返回3～19，如何等概率返回20～56
这个题目是A题目的进阶版，不过通过A题目可能总结不出来这套题目的规律，B题目做完就可以掌握这套题目的规律变化。
大致思路同A题目相差不大。
- f()函数等概率返回3～19，通过使用f()函数得到一个等概率返回0和1的函数f0() 做法是：[3, 10] 返回0；11 重来；[12,19]返回1；
- f0()函数等概率返回0和1，我们粗略估计一下20～56需要6个二进制位，000000～111111 即 0～63；
- 使用f1()函数表示等概率返回0～63，我们用f2()函数表示等概率返回0～36，做法：当f1() > 36时，重来，我们只需要f1返回0～36；
- f2()函数等概率返回0～36，那f2() + 20就可以等概率返回20～56.
因为思路同A题目，所以不详细解释了，此处列出代码：
//f等概率返回3～19
public static int f(){
return (int)(Math.random() * 17 + 3);
}
//根据f函数得到等概率返回0，1的函数f0
public static int f0(){
int ans;
do{
ans = f();
}while(ans == 11);
return ans < 11 ? 0 : 1;
}
//根据f0函数得到0～63等概率发生的函数 f1()
public static int f1(){
return (f0() << 5) + (f0() << 4) + (f0() << 3) + (f0() << 2) + (f0() << 1) + f0();
}
//根据f1函数得到0～36等概率发生的函数f2()
public static int f2(){
int ans;
do{
ans = f1();
}while (ans > 36);
return ans;
}
//根据f2函数得到20～56等概率发生的函数g()
public static int g(){
return f2() + 20;
}
到这里呢，这类题目已经完结了，B题目大致思路就是这类题目的规律，万变不离其宗，不管数据怎么变化，思路就是先等概率返回0和1，然后利用二进制表示需要等概率返回的数值范围，先获得0～b-a ，然后加上a，就可以获得了a~b等概率返回的函数了。
C. 假如函数f()不等概率返回0和1，那如何等概率返回0，1随机呢？
题目大致表示的是：f()函数只返回0和1，且不等，假如0返回概率为P，那么1返回的概率就是1-P，如何能让0,1 等概率随机。
解题思路：
- f()函数 {0:P 1: 1-P}，用两位二进制表示{00，01，10，11} 分别概率为{P2, P(1-P), (1-P)P, (1-P)2}，可以看出来01和10是等概率的，两外两种不等概率；
- 那我们可以调两次f()函数，两次不等即可得到01和10，其余的抛弃重来即可。
代码如下：
//这里的0.8只是假设0和1不等概率返回
public static int f(){
return Math.random() > 0.8 ? 0 : 1;
}
//根据二进制得到随机到0，1的等概率
public static int g(){
int ans;
do {
ans = f();
}while(ans == f());
return ans;
}
代码f()假设0的概率是0.8，1的概率是0.2，当我调用g()方法时，如果相等则重来，那就排除了00和11两种可能，如果不等则返回，01 或者10概率均为P(1-P)。
4.总结
随机函数Math.random()等概率返回[0,1)，对Math.random()进行相关运算可变化的得一些随机数，这些随机数的用处是非常大的。A，B，C题目中就是对这些随机函数的广泛应用。而随机函数最大的用处就是对数器，我们在做大部分题时都需要做校验，而测试的数据为了避免没考虑到边界值，随机数就是最好的校验数据。
给一个简单的对数器的代码看看即可。
//生成一个随机大小，随机数据的数组
public static int[] generateArray(int maxlen, int maxValue){
int len = (int)(Math.random()* maxlen + 1);
int [] array = new int[len];
for (int i = 0; i< len; i ++){
array[i] =(int) (Math.random() * maxValue);
}
return array;
}
这段代码生成一个随机大小（小于maxlen）的随机数据的数组，这个随机数组可用于校验排序后的数组是否是正确的，也可以校验各个排序方法是否一致，亦可成为前缀和数组的输入，或者数组上某段和的输入，用处可见一斑。
