【算法100天 | 1】随机数多种玩法

一、随机数概率变平方、三次方

在Java中可以使用Math.random()函数随机返回[0,1)之间的一个小数，对于任意的x（x属于[0,1)），[0,x)范围上的数出现概率是x；如果想让[0,x)范围上的数出现概率是 x^2、x^3呢？

1、平方概率

思路：

既然对于任意[0, 1)范围的数x 使用Math.random()函数获取到的概率是x，我想概率变x^2，是不是可以调用两次Math.random()，只要有一次出现数x就可以，因为强调的是只要有一次出现即可，所以使用Math.max()函数对两个结果取一个“并集”。

代码：

/**
 * 返回[0,1)的一个小数
 * 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方；
 */
private static double xToXPower2() {
    return Math.max(Math.random(), Math.random());
}
1
2
3
4
5
6
7

验证：

private static final int testTimes = 100_0000;

public static void main(String[] args) {
    int count = 0;

    // 1. 验证随机数的x^2概率
    System.out.println("=========随机数的x^2概率============");
    count = 0;
    double x = 0.61;
    for (int i = 0; i < testTimes; i++) {
        if (xToXPower2() < x) {
            count++;
        }
    }
    System.out.println((double) count / (double) testTimes);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求0.61的平方（0.371），取样数量为100万，测试结果为：0.372608；随着取样数量的变大，测试结果会无限接近于0.371。

2、三次方概率

思路：

既然对于任意[0, 1)范围的数x 使用Math.random()函数获取到的概率是x，我想概率变x^3，是不是可以调用三次Math.random()，只要有一次出现数x就可以，因为强调的是只要有一次出现即可，所以使用Math.max()函数对Math.max(Math.random(), Math.random()) 和 Math.random()取一个“并集”。

代码：

/**
 * 返回[0,1)的一个小数
 * 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x三次方；
 */
private static double xToXPower3() {
    return Math.max(Math.random(), Math.max(Math.random(), Math.random()));
}
1
2
3
4
5
6
7

验证：

private static final int testTimes = 100_0000;

public static void main(String[] args) {
    int count = 0;

    // 1. 验证随机数的x^3概率
    System.out.println("=========随机数的x^3概率============");
    count = 0;
    double x = 0.61;
    for (int i = 0; i < testTimes; i++) {
        if (xToXPower3() < x) {
            count++;
        }
    }
    System.out.println((double) count / (double) testTimes);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求0.61的平方（0.226981），取样数量为100万，测试结果为：0.227164；随着取样数量的变大，测试结果会无限接近于0.226981。

以此类推，想获取x的多少次方，就可以嵌套Math.max(Math.random(), xxx)函数多少次方。

二、根据已知随机函数得到特定概率函数

下面针对两道题目展开讨论：

1）给定一个函数f1()生成范围1-5内的随机值，根据f1()做一个1-7的等概率随机函数；

2）根据一个固定概率（具体多少不知道）返回0和1的函数x()，做一个等概率返回0和1的函数；

1、根据特定范围随机函数 生成其他范围的随机函数

已知一个函数f1()（假设这个函数是lib里的，不能修改）生成范围1-5内的随机值：

public static int f1() {
    return (int) (Math.random() * 5) + 1;
}
1
2
3

现在我想根据f1()做一个1-7 或者 其他范围的等概率随机函数；

思路：

首先要明确f1()函数中的范围 和 我们要求的没有任何关系可言，以我们平时使用Math.random()函数而言，我们相求某个范围[y, y + x)可以使用：x * Math.random() + y。就f1()函数而言是一样的道理，我们先把它变成0、1的等概率随机的函数f2()，然后再基于f2()函数生成任意范围的概率随机；

代码

1）0、1等概率随机函数f2()

// 1、随机机制，只能用f1()函数，等概率返回0和1
public static int f2() {
    int ans = 0;
    do {
        ans = f1();
    } while (ans == 3);
    return ans < 3 ? 0 : 1;
}
1
2
3
4
5
6
7
8

2）根据位运算得到 [0,7)等概率随机函数f3()

// 2、得到000 ~ 111 做到等概率 0 ~ 7等概率随机
public static int f3() {
    return (f2() << 2) + (f2() << 1) + f2();
}
1
2
3
4

3）[0,6)等概率随机函数f4()

// 3、0 ~ 6等概率返回一个，遇到7就重做，把7的概率平均分给0 ~ 6
public static int f4() {
    int ans = 0;
    do {
        ans = f3();
    } while (ans == 7);
    return ans;
}
1
2
3
4
5
6
7
8

4）1 ~ 7等概率随机函数func

public static int func() {
    return f4() + 1;
}
1
2
3

以此类推，如果想得到其他范围的随机函数，都可以基于0/1等概率函数f2()做为位运算、再重写某个范围的概率、最后概率起始范围做调整。

2、根据固定概率返回0和1的函数 生成0/1等概率函数

x()函数以固定概率返回0和1，但是x()函数的内容不知道、固定概率是多少也不知道；

public static int x() {
    return Math.random() < 0.67 ? 0 : 1;
}
1
2
3

现在要根据x()函数，等概率的返回0或1；

代码

既然x()函数会返回0和1，只需要确保调用两次x()函数返回的都是0 或 1即可；

public static int y() {
    int ans;
    do {
        ans = x();
    } while (ans == x());
    // 只有当x()的两次结果分别是0 和 1时才返回
    return ans;
}
1
2
3
4
5
6
7
8

验证

private static final int testTimes = 100_0000;

public static void main(String[] args) {
    int count = 0;

    count = 0;
    double x = 0.61;
    for (int i = 0; i < testTimes; i++) {
        if (y() < x) {
            count++;
        }
    }
    System.out.println((double) count / (double) testTimes);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

取样数量为100万，测试结果为：0.499959；随着取样数量的变大，测试结果会无限接近于0.5。