rand 函数的一些妙用

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

由rand5()返回rand7()

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

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

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

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

JAVA 复制

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$次的结果：

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

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

JAVA 复制

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]);
        }
    }
}

---

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

由不等概率(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$。

JAVA 复制

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]);
        }
    }
}

---