初级--02---前缀和数组、Math.random()、对数器和随机行为

文章目录前缀和数组1. 什么是前缀和数组某项可以表示为相邻前缀和之差A[i]preSum[i]−preSum[i−1]代码实现随机函数 Math.random()介绍Math.random()是令系统随机选取大于等于 0.0 且小于 1.0的伪随机 double值公式总结产生一个[01)之间的随机数。Math.random()返回大于等于0小于n之间的随机数int num(int)(Math.random()*n);返回指定范围的随机数(m-n之间)的公式:Math.random()*(n-m)m //包括m ,不包括nMath.random()*(n1-m)m //包括m ,也包括n案例 1:需求: **返回0-5之前的随机数**(int) (Math.random() * 6)案例2: 我们需要取222之间的偶数(int)2(int)(Math.random()*(22-2));案例 3:需求:**Math.max(Math.random(), Math.random());**经典题---- 随机函数题目1:需求:思路:题目 2:分析:那么我们调用 2次会有4中情况 ,假设出现0的概率为p,那么出现1的概率就为(1-p)等概率返回0和1:对数器用于校对数据正确与否的模拟器验证选择排序对数器结果:前缀和数组1. 什么是前缀和前面的所有再包括自己数组 第 0 项 到 当前项 的 总和如果用一个数组 preSum 表示preSum[0]数组A 第 0 项 到 第 0 项 的总和preSum[1]数组A 第 0 项 到 第 1 项 的总和preSum[2]数组A 第 0 项 到 第 2 项 的总和preSum[3]数组A 第 0 项 到 第 3 项 的总和…… 于是有preSum[i]A[0]A[1]…A[i]数组某项可以表示为相邻前缀和之差A[i]preSum[i]−preSum[i−1]代码实现publicstaticclassRangeSum2{privateint[]preSum;publicRangeSum2(int[]array){intNarray.length;preSumnewint[N];preSum[0]array[0];for(inti1;iN;i){preSum[i]preSum[i-1]array[i];}}publicintrangeSum(intL,intR){returnL0?preSum[R]:preSum[R]-preSum[L-1];}}随机函数 Math.random()介绍Math.random()是令系统随机选取大于等于 0.0 且小于 1.0的伪随机double值公式总结产生一个[01)之间的随机数。Math.random()返回大于等于0小于n之间的随机数int num(int)(Math.random()*n);返回指定范围的随机数(m-n之间)的公式:Math.random()*(n-m)m //包括m ,不包括n或者Math.random()*(n1-m)m //包括m ,也包括n案例 1:需求:返回0-5之前的随机数(int) (Math.random() * 6)publicclassTest2{publicstaticvoidmain(String[]args){inttestTimes10000000;intK6;int[]countsnewint[6];for(inti0;itestTimes;i){intans(int)(Math.random()*K);// [0,K-1]counts[ans];}for(inti0;iK;i){System.out.println(i这个数出现了 counts[i] 次);}}}案例2: 我们需要取222之间的偶数(int)2(int)(Math.random()*(22-2));publicclassTest03{publicstaticintGetevenNum(doublenum1,doublenum2){ints(int)num1(int)(Math.random()*(num2-num1));if(s%20){returns;}else{returns1;}}publicstaticvoidmain(String[]args){System.out.println(任意一个num1_num2之间的偶数GetevenNum(2,22));}}案例 3:需求:任意的xx属于[0,1)[0,x)范围上的数出现概率由原来的x调整成x平方Math.max(Math.random(), Math.random());经典题---- 随机函数题目1:需求:随机机制只能用f1思路:f1函数----实现1 ~5随机获取f2函数----等概率返回0和1f3函数----得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个f4函数----0 ~ 6等概率返回一个g函数----实现1~7随机返回// 随机机制只能用f1publicstaticintf1(){return(int)(Math.random()*5)1;}// 等概率返回0和1publicstaticintf2(){intans0;do{ansf1();}while(ans3);returnans3?0:1;}// 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个publicstaticintf3(){return(f2()2)(f2()1)f2();}// 0 ~ 6等概率返回一个publicstaticintf4(){intans0;do{ansf3();}while(ans7);returnans;}publicstaticintg(){returnf4()1;}题目 2:分析:你只能知道x会以固定概率返回0和1但是x的内容你看不到publicstaticintx(){returnMath.random()0.84?0:1;}那么我们调用 2次会有4中情况 ,假设出现0的概率为p,那么出现1的概率就为(1-p)0,0 -----p * p0,1 -----p * (1-p)1,0 -----(1-p) * p1,1-----(1-p) * (1-p)由此可知,出现(0,1) 和 (1,0)的概率 为一样等概率返回0和1:// 你只能知道x会以固定概率返回0和1但是x的内容你看不到publicstaticintx(){returnMath.random()0.84?0:1;}// 等概率返回0和1publicstaticinty(){intans0;do{ansx();}while(ansx());returnans;}对数器用于校对数据正确与否的模拟器验证选择排序publicstaticvoidselectionSort(int[]arr){if(arrnull||arr.length2){return;}for(inti0;iarr.length-1;i){intminIndexi;for(intji1;jarr.length;j){if(arr[j]arr[minIndex]){minIndexj;}}swap(arr,i,minIndex);}}publicstaticvoidswap(int[]arr,inti,intj){inttmparr[i];arr[i]arr[j];arr[j]tmp;}对数器// 返回一个数组arrarr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]publicstaticint[]lenRandomValueRandom(intmaxLen,intmaxValue){intlen(int)(Math.random()*maxLen);int[]ansnewint[len];for(inti0;ilen;i){ans[i](int)(Math.random()*maxValue);}returnans;}publicstaticint[]copyArray(int[]arr){returnArrays.copyOf(arr,arr.length);}// arr1和arr2一定等长publicstaticbooleanisSorted(int[]arr){if(arr.length2){returntrue;}intmaxarr[0];for(inti1;iarr.length;i){if(maxarr[i]){returnfalse;}maxMath.max(max,arr[i]);}returntrue;}publicstaticvoidmain(String[]args){intmaxLen5;intmaxValue1000;inttestTime2;for(inti0;itestTime;i){int[]arr1lenRandomValueRandom(maxLen,maxValue);int[]tmpcopyArray(arr1);selectionSort(arr1);if(!isSorted(arr1)){for(intj0;jtmp.length;j){System.out.print(tmp[j] );}System.out.println();System.out.println(选择排序错了);break;}Arrays.stream(arr1).forEach((s)-System.out.print(s ));System.out.println(排序正确);}}结果:正确错误