rand 函数的一些妙用
2022-09-10 17:11:38 # algorithm # algorithm # 数学

最近看到一些有趣的rand()函数，在这里记录一下。

由rand5()返回rand7()

rand5()函数表示等概率返回1~5之间的整数，要求我们在不使用其他函数的前提下，使用rand5()函数生成rand7()函数。

我们可以发现rand5()可以等概率返回1、2、3、4、5中的数，那么我们试图通过rand5()函数构造一个等概率返回0、1的函数bit()。

再由bit()函数即可等概率构造任意一个[0, x]区间内的等概率返回函数。

因为每一次bit()调用都为独立事件，再令res > x的再重试即可。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Rand7 {

    /**
     * @return 返回1~5之间的某个整数
     * @description 等概率返回1~5之间的所有整数
     */
    public static int rand5() {
        // Math.random()函数将等概率返回[0, 1)的浮点数
        return (int) (Math.random() * 5) + 1;
    }

    /**
     * @return 返回0或1
     * @description 等概率返回0、1
     */
    public static int bit() {
        int res = 0;
        do {
            res = rand5();
        } while (res == 3);
        return res < 3 ? 0 : 1;
    }

    /**
     * 等概率返回0~2^bits-1之间的所有数
     *
     * @param bits 二进制位数
     * @return 返回0~2^bits-1之间的某个数
     */
    public static int generate(int bits) {
        int res = 0;
        for (int i = 0; i < bits; i++) {
            res += bit() << i;
        }
        return res;
    }


    /**
     * @return 返回1~7之间的某个整数
     * @description 等概率返回1~7之间的所有整数
     */
    public static int rand7() {
        // 可以发现[1, 7]可以由[0, 6] + 1构成,于是考虑如何等概率返回[0, 6]
        int res = 0;
        do {
            res = generate(3);
        } while (res == 7);
        return res + 1;
    }


    public static void main(String[] args) {
        int[] counts = new int[10];
        int N = 1000000;
        for (int i = 0; i < N; i++) {
            counts[rand7()]++;
        }
        for (int i = 1; i <= 7; i++) {
            System.out.printf("%d出现%d次\n", i, counts[i]);
        }
    }
}

测试\(1000000\)次的结果：

image-20220910173239248

由rand(a, b)返回rand(c, d)

其中rand(a, b)函数可以等概率返回[a, b]之间的所有数，需要使用rand(a, b)生成rand(c, d)其中d - c != b - a。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class RandRange {
    public static int randAB(int a, int b) {
        int diff = b - a + 1;
        return (int) (Math.random() * diff) + a;
    }

    public static int bit(int a, int b) {
        // 使用randAB(a, b)等概率返回0、1
        int res = 0;
        // 注意如果[a, b]中有奇数个数字则舍弃中间数字
        // 如果[a, b]中有偶数个数字则直接划分即可
        int count = b - a + 1;
        int mid = a + (b - a) / 2;
        if (count % 2 == 1) {
            do {
                res = randAB(a, b);
            } while (res == mid);
            return res < mid ? 0 : 1;
        } else {
            res = randAB(a, b);
            return res <= mid ? 0 : 1;
        }
    }


    public static int randCD(int a, int b, int c, int d) {
        // 和rand7()思路一致, 先生成[0, x], 而后 + c即可
        int x = d - c;
        int bits = 0;
        // 先求得x的二进制位数
        int tmp = x;
        do {
            tmp >>= 1;
            bits++;
        } while (tmp != 0);
        int res = 0;
        do {
            res = 0;
            for (int i = 0; i < bits; i++) {
                res += (bit(a, b) << i);
            }
        } while (res > x);
        return res + c;
    }


    public static void main(String[] args) {
        int N = 1000000;
        int a = 10, b = 20;
        int c = 40, d = 100;
        int[] counts = new int[b + 1];
        for (int i = 0; i < N; i++) {
            counts[randAB(a, b)]++;
        }
        for (int i = a; i <= b; i++) {
            System.out.printf("%d出现%d次\n", i, counts[i]);
        }
        counts = new int[d + 1];
        for (int i = 0; i < N; i++) {
            counts[randCD(a, b, c, d)]++;
        }
        for (int i = c; i <= d; i++) {
            System.out.printf("%d出现%d次\n", i, counts[i]);
        }
    }
}
image-20220910180448410

可以发现总体上是满足等概率出现的。

由不等概率(0, 1)返回等概率(0, 1)

已知有f()函数将以\(p\)概率返回\(0\)，\(1-p\)概率返回\(1\)，且满足\(p \ne 1- p\)。

那么我们进行两次独立事件，若两次都返回\(0\)，显然概率为\(p^2\)，若两次都返回\(1\)，显然概率为\((1-p)^2\)，那么我们舍弃这两种情况，若一次\(0\)一次\(1\)且不区分先后，那么概率就为\(p\times(1-p)\)，记先\(0\)后\(1\)则返回\(0\)，先\(1\)后\(0\)则返回\(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
public class DifferentPossibility {

    public static int f() {
        // 假定以3/4概率返回0, 1/4概率返回1
        int res = 0;
        res = (int) (Math.random() * 4) + 1;
        return res <= 3 ? 0 : 1;
    }


    public static int g() {
        int res = 0;
        do {
            res = f();
        } while (res == f());
        return res;
    }

    public static void main(String[] args) {
        int N = 100000;
        int[] counts = new int[2];
        for (int i = 0; i < N; i++) {
            counts[g()]++;
        }
        for (int i = 0; i <= 1; i++) {
            System.out.printf("%d出现了%d次\n", i, counts[i]);
        }
    }
}
image-20220910181557263
上一页
2022-09-10 17:11:38 # algorithm # algorithm # 数学
下一页