随机函数与对数器

1. Math.Random()

Math.Random是java提供的一层api，其结果是返回(0,1]范围内的任意一个小数，其任意一个小数出现的范围都是等概率的

@Test
public void test(){
    //Math.random是等概率的
    int testTimes = 10000;
    int count =0;
    for(int i = 0;i<testTimes;i++){
        if(Math.random() < 0.3){
            count++;
        }
    }
    System.out.println((double) count/(double) testTimes);
}

2. 实现x^n的概率取值

• 使用max的实现:每一次Random的调用都是一次独立随机实验，只要有一次没有落到这个范围，就不成立，所以是概率*概率，三次方同理

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

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

• 实现min的实现

private static double xToXPowerMin(){
    return Math.min(Math.random(),Math.random());
}

这个0~x间出现的数的概率是啥?

由于min的特点，只要其中有一个数<x,那么整个结果都会<x，也就是一个||的效果，我们可以通过1-这个概率，来得到这个数没有落到这个区间上的概率，再用1-它，就是落到这个区间上的概率，正难则反

最终得到的概率是(1-x)^2

3. 1-5随机到1 -7随机

现在有一个函数f(),调用它可以等概率地得到[1,2,3,4,5]上的数，现在要求你只使用f()，要求使用该f()实现1-7的数等概率返回

思路：改造f()为01发生器，我们在内部函数中取值，取到1,2的时候，我们认为得到了0，取到4,5的时候，我们认为得到了1，当取到3的时候，我们让f()在来一次

public static int f(){
    return (int)(Math.random()*5)+1;
}

//随机机制,只能用f1(),等概率返回0和1
public static int f1(){
    int ans = 0;
    do {
        ans = f();
    }while (ans == 3);
    return ans<3?0:1;
}

//得到000-111做到等概率
public static int f3(){
    return (f1()<<2) + (f1()<<1) + (f1()<<0);
}

public static int f4(){//目标函数
    int ans = 0;
    do {
        ans = f3();
    }while (ans == 7);
    return ans;
}

4.从ab随机到cd

   //实战,有一个3~19的等概率发生器,让你实现17~56的等概率发生器
   //3~19,可以简化为0~16,那么取值就是[0,17)
   public static int g1(){
       return (int)(Math.random()*17)+3;
   }

   public static int g2(){
       //3~19,3+8-1=10(3~10) (11) 12+8-1 =19(11~19)
       int ans = 0;
       do {
           ans = g1();
       }while (ans == 11);
       return ans;
   }
//实现17~56,56<64 (0~1 1~3 3~8 9~15 15~31 31~64)
//56-17=39(0~39合法)
   public static int g3(){
       //需要五位
       int ans =  0
       do {
           ans = (g2()<<5)+(g2()<<4) +(g2()<<3) +(g2()<<2)+(g2()<<1)+(g2()<<0);
       }while (ans >39);
       return ans;
   }

5. 从01不等概率到01等概率

f()会返回一个0(概率为p),会返回一个1(概率为1-p)，其中p不等于0.5

public int x(){
    return Math.random() < 0.84? 0:1;
}

//固定概率返回0和1
public int y(){
    int ans = 0;
    do {
        ans = x();
    }while (ans == x());
    return ans;
}

6. 对数器

//返回一个数组arr,arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]
public static int[] lenRandomValueRandom(int maxLen,int maxValue){
    int len = (int)(Math.random()*maxLen);//长度随机
    int[] ans = new int[len];
    for(int i = 0;i<len;i++){
        ans[i] = (int)(Math.random()*maxValue);
    }
    return ans;
}

public static boolean sorted(int[] arr){
    if(arr.length == 0){
        return true;
    }
    int max = arr[0];
    for (int i =1;i<arr.length;i++){
        if(max > arr[i]){
            return false;
        }
        max = Math.max(max,arr[i]);
    }
    return true;
}

public static int[] copyArray(int[] arr){
    int[] ans = new int[arr.length];
    for (int i = 0;i<arr.length;i++){
        ans[i] = arr[i];
    }
    return ans;
}

@Test
public void test2(){
    int maxLen = 50;
    int maxValue = 1000;
    int testTime = 10000;
    for(int i = 0;i< testTime;i++){
        int[] arr1 = lenRandomValueRandom(maxLen,maxValue);
        int[] arr2 =  copyArray(arr1);
        int[] tmp1 =  copyArray(arr1);
        int[] tmp2 =  copyArray(arr2);
        BubbleSort.bubbleSort(arr1);
        InsertSort.insertSort(arr2);
        if(!sorted(arr1)){
            System.out.println("冒泡错了:"+ Arrays.toString(tmp1));
        }
        if(!sorted(arr2)){
            System.out.println("插入错了:"+Arrays.toString(tmp2));
        }
    }
}