- 我们都知道java中有个随机函数Math.random(), 其实看似平平无奇的一个随机函数, 演变出来的面试题随时都可能难到一大片。本人也是最近才开始专心研究算法，下面左几个小测试解释一下Math.random()等概率随机函数
package code_01; public class RandomTest { public static void main(String[] args) { //demo1, 测试random函数返回的是等概率 int testTimes = 10000000; int count = 0; for (int i = 0; i < testTimes; i++) { if (Math.random() < 0.75) { count++; } } System.out.println((double) count / (double) testTimes); //demo2, 已知random()是等概率函数。给定x值，返回的y值必定基本相等. //现在给定任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方 //设计自己的算法函数 System.out.println("===============demo2========================="); double x = 0.5; int count2=0; for (int i = 0; i < testTimes; i++) { //统计连续两次出现的概率值小于x的次数。 //一次出现的概率为x,连续两次出现的概率就位x*x了，不懂的话看demo1 if (xSquared() < x) { count2++; } } //等概率并不代码一定相等，接近即可 System.out.println(Math.pow(x, 2)); System.out.println("测试自己写的函数 " + (double) count2 / (double) testTimes); //demo3, 现在给定任意的m，m属于[0,1)，[0,x)范围上的数出现概率由原来的m调整成m的三次方 //设计自己的算法函数 System.out.println("===============demo3========================="); double m = 0.5; int count3=0; for (int i = 0; i < testTimes; i++) { if (xToPower3() < m) { count3++; } } //等概率并不代码一定相等，接近即可 System.out.println(Math.pow(m, 3)); System.out.println("测试自己写的函数 " + (double) count3 / (double) testTimes); } public static double xSquared () { //为什么2次randon()和max()就能得到平方。其实，就是连续 //统计连续两次随机数的范围。一次出现的概率为x,连续两次出现的概率就位x*x了 return Math.max(Math.random(), Math.random()); } public static double xToPower3 () { //按照demo2类推得到 return Math.max(Math.max(Math.random(), Math.random()), Math.random()); } } - 有了上面的例子做铺垫，下面分享一下经典面试题：“已知函数fx（）等概率返回1,2,3,4,5. 设计一种算法g()等概率返回1,2,3,4,5,6,7 要求不能修改函数fx(),也不能引入其他的等概率函数
”。 算法实现思路来源于马士兵教育的左程云大神，利用位运算、二进制的知识实现。 此随笔只是自己弄通后的一点心得，方便以后复习使用。package code_01; /** * 已知函数fx（）等概率返回1,2,3,4,5. 设计一种算法g()等概率返回1,2,3,4,5,6,7 * 要求不能修改函数fx(),也不能引入其他的等概率函数 */ public class RandomTester01 { // 此函数不能改，只能被调用 public static int fx() { return (int) (Math.random() * 5) + 1; } // 随机机制，只能用fx()函数，且不能修改函数，也不能再引入其他的等概率函数 // 等概率返回0和1 // 1,2,3,4,5 每个数出现的概率都为20%。如果将3排除，那么1和2,3和4出现的概率都为50% // 非此即比，因此返回0和1并且结合位运算和二进制的知识解决 public static int f1() { int ans = 0; do { ans = fx(); } while (ans == 3); return ans < 3 ? 0 : 1; } // 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个 // 二进制的知识，3位二进制站位符号可以确认[0,7]范围内的数字 public static int f2() { return (f1() << 2) + (f1() << 1) + f1(); } public static int f3() { int ans = 0; do { ans = f2(); } while (ans == 7); //此处的ans == 0 即可直接得到[1,7]等概率数字。 但是作为通用方法，一般是从0开始，所以此处把7排除 return ans; } // 0 ~ 6等概率返回一个 public static int g() { return f3() + 1; //通用方法，以后无论需要返回什么范围的等概率数字, 修改后面的常量即可 } public static void main(String[] args) { int testTimes = 10000000; int[] counts = new int[8]; for (int i = 0; i < testTimes; i++) { int num = g(); counts[num]++; } for (int j = 0; j < 8; j++) { System.out.println(j + "这个数，出现了 " + counts[j] + " 次， 占比约为 " + (double) counts[j]/ (double) testTimes); } } } - 上面的例子凑巧都是从1开始，如果我们拓展一下，目标函数随意给定范围，那么该如何去设计算法呢？ 比如，目标函数为等概率返回19,20,21,22,23,24,25,26,27
package code_01; /** * 已知函数fx（）等概率返回1,2,3,4,5. 设计一种算法g()等概率返回19,20,21,22,23,24,25,26,27 * 要求不能修改函数fx(),也不能引入其他的等概率函数 */ public class RandomTester01_extension { // 此函数不能改，只能被调用 public static int fx() { return (int) (Math.random() * 5) + 1; } //思路相同，依旧使用二进制的思想返回0和1 public static int f1() { int ans = 0; do { ans = fx(); } while(ans == 3); //如果为3继续循环，把3的20%概率分摊给1,2 4,5, 此时他们每个概率为25% return ans < 3 ? 1 : 0; } public static int f2() { /** * 19,20,21,22,23,24,25,26,27为9个数. 我们依旧想办法从0开始 * 也就是得到0,1,2,3,4,5,6,7,8等概率函数。最后加19即可 * 因为数值范围是[0,8]. 二进制需要4位, 即[0,15] * * 此处，f1()调用多少次, 左移多少位，完全由目标函数的取值范围决定 */ int ans = (f1() << 3) + (f1() << 2) + (f1() << 1) + f1(); return ans; } public static int f3() { int ans = 0; do { ans = f2(); } while (ans > 8); //因为我们只关心[0,8]范围的数字,此处的8由目标数字最大值27-19得到 return ans; } public static int g() { int ans = f3() + 19; //通用方法，以后无论需要返回什么范围的等概率数字, 修改后面的常量即可 return ans; } public static void main(String[] args) { int testTimes = 1000000; int[] counts = new int[9]; for (int i = 0; i < testTimes; i++) { int ans = g(); counts[ans-19]++; } for (int i = 0; i < counts.length -1; i++) { System.out.println(i + 19 + " 这个数出现了 " + counts[i] + " 次， 占比约为 " + (double) counts[i]/ (double) testTimes); } } } - 继续延伸一下概率算法问题。新的题目为：“已知函数fx（）以固定概率返回0和1.且0和1为不等概率。要求设计自己的算法函数等概率返回0和1”
package code_01; /** * 已知函数fx（）以固定概率返回0和1.且0和1为不等概率 * 要求设计自己的算法函数等概率返回0和1 */ public class RandomTester01_extension2 { // 此函数不能改，只能被调用. 此处，可以明显看出返回0的概率要大于返回1的概率 public static int fx() { return Math.random() < 0.84 ? 0 : 1; } //设计思路, 如果两次都为0，或者两次都为1, 那排除掉. //既然是设计为等概率返回0和1，那么我们只关心0和1。 这和我们上面一个例子中ans>8的道理是一样的 public static int g() { int ans; do { ans = fx(); } while (ans == fx()); //也就是说如果两次调用结果相同，我们就继续循环，直到找到我们想要的数字组合为止 return ans; } public static void main(String[] args) { int testTimes = 1000000; int[] counts = new int[2]; for (int i = 0; i < testTimes; i++) { int ans = g(); counts[ans]++; } for (int i = 0; i < counts.length -1; i++) { System.out.println(i + " 这个数出现了 " + counts[i] + " 次， 占比约为 " + (double) counts[i] / (double) testTimes); } } }开胃菜，其实就难死一大片人了，包括我自己。算法千千万，需要学习的东西实在太多了。以后每周会更新几道算法题，作为笔记为自己复习做准备, 也为了更多算法小白一同参考