算法题：将生成1-5随机数函数转换为1-7随机数函数

题目

将生成1-5随机数函数转换为1-7随机数函数。

解法

方法一

简单的说, 把 1-5 的随机数发生器用两次, 拼成一个5进制的数, 就是1-25. 将这 1-25 平均分配的25种情况映射到7种情况上, 问题就解决了. 因为21是7的倍数, 我们可以每三个映射到一个, 即1-3 映射到1, …, 19-21 映射到7. 可见, 这些情况之间的概率是一样的. 那么, 要是拼成的数字正好是 22-25 这四个呢? 有两种方法, 第一种是丢弃这个数字, 从头再来, 直到拼成的数字在1-21之间. 因为这个是个概率算法, 不能保证每次都能落在1-21, 所以采样的密度不高. 还有一种方法, 是说, 假如落到了 22-25, 那这次的采样结果就用上次的. 可以证明, 这看上去两个互相矛盾的算法, 结果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是数学物理模拟里面常用的方法)

256.7 ms

237.7 ms

273.1 ms

292.8 ms

282.5 ms

public static int random5() {
        return RandomUtil.randomInt(1, 6);
    }

    public static int random7() {
        int i = random5();
        int i1 = random5();
        int res = i * 10 + i1;
        if (res == 11 || res == 12 || res == 13) {
            return 1;
        } else if (res == 14 || res == 15 || res == 21) {
            return 2;
        } else if (res == 22 || res == 23 || res == 24) {
            return 3;
        } else if (res == 25 || res == 31 || res == 32) {
            return 4;
        } else if (res == 33 || res == 34 || res == 35) {
            return 5;
        } else if (res == 41 || res == 42 || res == 43) {
            return 6;
        } else if (res == 44 || res == 45 || res == 51) {
            return 7;
        } else {
            // 拒绝采样
            return random7();
        }
    }

方法二

生成三个（1,5）的随机数，分别表示一个二进制位，其中1和2映射为0，3跳过，4和5映射为1。这样产生的三位二进制数，即0-7这8个数字都是等概率的。如果产生的是0，那么丢弃即可。

433.5 ms

422.8 ms

442.1 ms

607.8 ms

434.8 ms

public static int random5() {
        return RandomUtil.randomInt(1, 6);
    }

    public static int random7() {
        int i = getBinary();
        int i2 = getBinary();
        int i3 = getBinary();
        if (i == 0 && i2 == 0 && i3 == 0) {
            return random7();
        }
        return i * 4 + i2 * 2 + i3;
    }

    public static int getBinary() {
        int random5 = random5();
        if (random5 == 5) {
            return getBinary();
        }
        return random5 % 2;
    }

方法三

生成两个（1,5）的随机数，产生一个两位的五进制数，5 * (random5() – 1) + random5()。这个公式能够等概率产生1-25，即第一个随机数代表：0,5,10,15,20，地位代表1,2,3,4,5。这样对这个数字（1-25的数字），采用方法一的方法，只用1-21，分7分，代表1-7,22-25这4个数字扔掉。

271.3 ms

307.4 ms

302.0 ms

275.5 ms

267.7 ms

public static int random5() {
        return RandomUtil.randomInt(1, 6);
    }

    public static int random7() {
        // 1~25
        int result = 5 * (random5() - 1) + random5();
        if (result > 21) {
            return random7();
        }
        return result % 7 + 1;
    }