【算法学习系列】04 - 由01不等概率随机实现01等概率随机

约定条件说明

• 存在函数 unequalP_01() 不等概率返回 0 和 1。
• 只能通过函数 unequalP_01() 来实现 01 等概率随机函数 equalP_01()

解决方案

为了能够验证最后的等概率随机，这里先把函数 unequalP_01() 实现一下：

	// 不等概率返回 0 和 1
    private int unequalP_01(){
        return (Math.random() < 0.68 ? 0 : 1);
    }

思路说明

• 假设返回 0 的概率是 P ，返回 1 的概率是 1-P。
• 那么返回 01 和 10 的概率都是 P * (1-P)，所以可以转化为：做两次不等概率随机，将 00 和 11 的概率均分到 01 和 10 上即可，这样就能保证等概率返回 0 和 1，后面会进行验证。

实现代码

如下：

	// 等概率返回 0 和 1
    private int equalP_01(){
        int ran = 0;
        do {
            ran = unequalP_01();
        }while (ran == unequalP_01());
        // 0 0 或者 1 1 会继续循环
        // 0 1 或者 1 0 会跳出循环
        return ran;
    }

做两次不等概率随机，第一次和第二次返回值相同就继续循环，直到第一次和第二次返回值不一样就跳出循环。

那么 01 和 10 返回的概率是一样的，且 01 的情况返回 1 ，10 的情况返回 0 。故返回 0 和 1 也是等概率的。

验证方案

做一百万次样本测试，看下上面实现的等概率返回 0 和 1 的函数 equalP_01() 返回 0 出现的次数是不是很接近 50 万这个数字。

验证代码如下：

	private void verify01Equal(){
        int count = 0, testCount = 1000000;
        for (int i = 0;i < testCount;i++){
            if (equalP_01() == 0){
                count++;
            }
        }
        System.out.println(":> 0 出现的次数：" + count);
    }

结果如下：

这里可以看到 0 出现的次数跟预期的一致，基本等于五十万。故验证成功。

技术永不眠！下期有缘再见！