02、介绍随机函数

随机函数是平时刷题练习时验证正确性的比较灵魂的方法。
java中提供了Math.random()函数：返回一个[0~1)等概率的一个double类型的值。

1、验证代码

    package com.yubin.algorithms;
    
    /**
     * 介绍随机函数的使用
     * @author YUBIN
     * @create 2021-03-13
     */
    public class Code0007_RandToRand {
    
        public static void main(String[] args) {
            // 验证Math.random()函数[0,1)是等概率的
            int testTimes = 10000000;
            int count = 0;
    
            for (int i = 0; i < testTimes; i++) {
                if (Math.random() < 0.75) { // 其概率应该约等于0.75
                    count++;
                }
            }
            System.out.println((double)count / (double)testTimes);
    
            System.out.println("===========================");
    
            // [0,1)*8 => [0,8)
            count = 0;
            for (int i = 0; i < testTimes; i++) {
                if (Math.random() * 8 < 5) { // 其概率应该约等于 5/8=0.625
                    count++;
                }
            }
            System.out.println((double)count / (double)testTimes);
    
            System.out.println("===========================");
    
            int k = 9;
            // [0,k) 相当于 [0,l-1]
            int[] counts = new int[k];
            for (int i = 0; i < testTimes; i++) {
                int ans = (int) (Math.random() * k);
                counts[ans]++;
            }
            for (int i = 0; i < k; i++) {
                System.out.println(i + "这个数,出现了" + counts[i] + "次");
            }
            System.out.println("===========================");
        }
    }

2、题目一：如何利用Math.random()函数，把得到[0,x)范围上的数的概率从x调整成x²

题目分析：经过上面的验证Math.random()随机函数[0,1)范围上概率是相等的，对应的0 ~ x范围的概率就是x，那么如何让0 ~ x的概率变成x²呢？
利用Math.max(Math.random(), Math.random())
Math.max(a1,a2); 只有当a1和a2两个值都在0 ~ x范围内的时候值才会在0 ~ x范围内，这样[0,x)的概率就变成x²了。

    private static double xToPower2() {
      return Math.max(Math.random(), Math.random());
    }

注意：如果这里改成Math.min()函数的话，概率就变成 1-(1-x)²

3、题目二：从1 ~ 5随机到1 ~ 7随机

题目分析：程序中已提供一种1 ~ 5的随机是等概率的方法，如何利用该函数实现1 ~ 7的随机是等概率的。
其实这个题目有一个限制就是1~7的等概率随机数不能使用 (int)(Math.random()*7)+1的方式，只能使用现成的方法。
思路：
已知函数是等概率返回[1,5]的整数
那么1,2,3,4,5的概率分别是20%， 如果我使用1和2 表示0; 4和5表示1 当遇到3的时候再次随机即将得到3的概率分摊到其它4个数上面,此时得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%。
通过[1,5]等概率函数可以得到一个0,1等概率函数，然后再利用二进制的方式可以拿到一个0 ~ 7的等概率函数
000,001,010,011,100,101,110,111。 因为7这个数至少需要3位来表示。
代码实现：

    /**
     * 返回[1,5]的等概率随机数
     * 假设该方法是lib里面,不能修改
     * @return
     */
    private static int f1() {
        return (int) (Math.random() * 5) + 1;
    }
    
    /**
     * 随机机制,等概率返回0和1 只能使用f1函数
     * 分析 f1函数是等概率返回[1,5]的整数
     * 那么1,2,3,4,5的概率分别是20%， 如果我使用1和2 表示0; 4和5表示1 当遇到3的时候再次随机即将得到3的概率分摊到其它4个数上面,
     * 此时得到1、2、4、5的概率都是25%，因此得到0的概率就是50%，得到1的概率也是50%
     *
     * @return
     */
    private static int f2() {
        int ans = 0;
        do {
            ans = f1();
        } while (ans == 3);
    
        return ans < 3 ? 0 : 1;
    }
    
    // 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个 每一个数的概率是1/8
    private static int f3() {
        return (f2() << 2) + (f2() << 1) + (f2() << 0);
    }
    
    // 0 ~ 6等概率返回一个
    private static int f4() {
        int ans = 0;
        do {
            ans = f3();
        } while (ans == 7);
    
        return ans;
    }
    
    // 1 ~ 7等概率返回一个
    private static int g() {
        return f4() + 1;
    }

同理：从a ~ b随机到c ~ d随机这个题目也可以使用上面这个方法来实现。
将a ~ b变成01等概率发生器 ，将c ~ d变成0 ~ (d-c) 这时再看d-c需要几个二进制位, 同时如果超过d-c部分的重做即可

4、题目三：01不等概率随机到01等概率随机

分析：01不等概论，但是可以知道0和1是固定概率的，这样的话我们使用两位来表示
00，01，10，11
这每个数出现的概率都是第一位的概率 * 第二位的概率， 而已知的函数0和1虽然概率不一样但是0的概率*1的概率是一样的，这样01,10就是等概率的了， 使用01表示0，10表示1，其它情况重做即可，这样最后就能得到一个01的等概率随机。
代码实现：

    // 已知的01不等概论函数，但是0和1的概率是固定的
    private static int x() {
        return Math.random() > 0.84 ? 0 : 1;
    }
    
    // 通过x函数得到01的等概率随机
    private static int y() {
        int ans = 0;
        do {
            // 第一次调用x函数
            ans = x();
        } while (ans == x()); // 第二次调用x函数 两次返回的结果不一样则说明要么是01 要么是10
    
        return ans;
    }