1. 我们都知道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());
        }
    
    }

     

  2. 有了上面的例子做铺垫,下面分享一下经典面试题:“已知函数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);
            }
        }
    }

     

  3. 上面的例子凑巧都是从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);
            }
        }
    }

     

  4. 继续延伸一下概率算法问题。新的题目为:“已知函数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);
            }
        }
    }

    开胃菜,其实就难死一大片人了,包括我自己。算法千千万,需要学习的东西实在太多了。以后每周会更新几道算法题,作为笔记为自己复习做准备, 也为了更多算法小白一同参考

原文地址:http://www.cnblogs.com/chen1-kerr/p/16898071.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性