Math.Random 返回范围[0,1) 等概率返回 计算机中所有的小数都是有精度的 有精度的代表是有穷尽的 可以等概率返回

    等概率返回整数 转型成int类型
    image.png
    出现的次数都差不多 等概率
    image.png

    要求[0,x)范围 返回的x 的概率为x^2
    连续调用两次 只有两次都落在0-x范围 返回的值才在0-x范围 所以概率为x^2
    image.png

    1. count = 0;
    2.         double x = 0.17;
    3.         for (int i = 0; i < testTimes; i++) {
    4.             if (xToXPower2() < x) {
    5.                 count++;
    6.             }
    7.         }
    8.         System.out.println((double) count / (double) testTimes);
    9.         System.out.println((double) 1 - Math.pow((double) 1 - x, 2));
    10.            // 是Math.max System.out.println(Math.pow(x, 2));
    12.       // 返回[0,1)的一个小数
    13.     // 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方
    14.     public static double xToXPower2() {
    15.         return Math.min(Math.random(), Math.random());
    16.     }

    经典面试题
    image.png
    f函数 可以等概率的得到随机 1-5
    image.png
    在只使用f的情况下 等概率的返回随机 1-7
    将f函数 改造为 0 1 发生器 1,2返回0 4,5返回1 返回1,0等比 3重新调用f函数
    image.png

    1. // lib里的，不能改！
    2.     public static int f1() {
    3.         return (int) (Math.random() * 5) + 1;
    4.     }
    6.     // 随机机制，只能用f1，
    7.     // 等概率返回0和1
    8.     public static int f2() {
    9.         int ans = 0;
    10.         do {
    11.             ans = f1();
    12.         } while (ans == 3);
    13.         return ans < 3 ? 0 : 1;
    14.     }

    要等比返回随机 1-7 将上一步等比返回1,0的函数 拼成2进制 二进制7为 1 1 1 三位二进制数 可以得到0-7范围的等概率随机数
    每个二进制位 调用一下函数f2 每一位都是独立调用的 所以返回的数最后也是等概率的

    1. // 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个
    2.     public static int f3() {
    3.         return (f2() << 2) + (f2() << 1) + f2();
    4.     }
    6.     // 0 ~ 6等概率返回一个
    7.     public static int f4() {
    8.         int ans = 0;
    9.         do {
    10.             ans = f3();
    11.         } while (ans == 7);
    12.         return ans;
    13.     }
    15.     public static int g() {
    16.         return f4() + 1;
    17.     }
    1. counts = new int[8];
    2.         for (int i = 0; i < testTimes; i++) {
    3.             int num = g();
    4.             counts[num]++;
    5.         }
    6.         for (int i = 0; i < 8; i++) {
    7.             System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
    8.         }

    image.png

    一个函数 以p概率返回0 以1-p概率返回1
    调用f函数2次 返回0,0 1,1直接舍弃， 返回0,1得0 1,0得1 则 1 0 等概率
    image.png

    1. // 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
    2.     public static int x() {
    3.         return Math.random() < 0.84 ? 0 : 1;
    4.     }
    6.     // 等概率返回0和1
    7.     public static int y() {
    8.         int ans = 0;
    9.         do {
    10.             ans = x();
    11.         } while (ans == x());//判断第二次调用x函数是否与第一次相等 不等才结束返回
    12.         return ans; //返回的1或0 必等概率 
    13.     }

    对数器
    主要利用随机函数 生成大样本 对自己写的排序函数 进行测试 防止排序函数只对特定的数值有效
    使用方法

    1.     // 返回一个数组arr，arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]
    2.     //构建一个随机数组 测试用
    3.     public static int[] lenRandomValueRandom(int maxLen, int maxValue) {
    4.         int len = (int) (Math.random() * maxLen);
    5.         int[] ans = new int[len];
    6.         for (int i = 0; i < len; i++) {
    7.             ans[i] = (int) (Math.random() * maxValue);
    8.         }
    9.         return ans;
    10.     }
    12.     public static int[] copyArray(int[] arr) {
    13.         int[] ans = new int[arr.length];
    14.         for (int i = 0; i < arr.length; i++) {
    15.             ans[i] = arr[i];
    16.         }
    17.         return ans;
    18.     }

    具体使用

    1.     // arr1和arr2一定等长
    2.     public static boolean isSorted(int[] arr) {
    3.         if (arr.length < 2) {
    4.             return true;
    5.         }
    6.         int max = arr[0];
    7.         for (int i = 1; i < arr.length; i++) {
    8.             if (max > arr[i]) {
    9.                 return false;
    10.             }
    11.             max = Math.max(max, arr[i]);
    12.         }
    13.         return true;
    14.     }
    16.     public static void main(String[] args) {
    17.         int maxLen = 5;
    18.         int maxValue = 1000;
    19.         int testTime = 10000;
    20.         for (int i = 0; i < testTime; i++) {
    21.             int[] arr1 = lenRandomValueRandom(maxLen, maxValue);
    22.             int[] tmp = copyArray(arr1);
    23.             selectionSort(arr1);
    24.             if (!isSorted(arr1)) {
    25.                 for (int j = 0; j < tmp.length; j++) {
    26.                     System.out.print(tmp[j] + " ");
    27.                 }
    28.                 System.out.println();
    29.                 System.out.println("选择排序错了！");
    30.                 break;
    31.             }
    32.         }
    34.     }