引入

给定一个方法f()，它可以等概率返回$[1,5]$范围内的整数。现在规定，方法f()是你唯一可以借助的随机机制（Math.random()之类的随机机制都不能用）。在此基础上编写相关方法，使得$[1,7]$范围内的整数等概率返回。

思路

这个题目还挺经典的，好像在面试题里出现过。想要一步到位解决肯定是不行的，我们要一步一步来。首先明确一下f()是条件函数，目标函数（姑且称之为g()）是$[1,7]$范围内的整数等概率返回。不能用Math.random()，但是我们可以写一个作用类似的函数，即等概率返回整数0和1的函数（01发生器）f1()，得到这个函数我们就算是迈出了第一步。怎么实现f1()其实逻辑很简单，就是调用f()的时候如果返回1或者2，就让f1()返回0；f()如果返回4或者5，就让f1()返回1；f()如果返回3，就重新调用一次。

做到这里有的同学会兴奋过头，觉得g()不就是f1()*6+1吗？当然不是啦，f1()*6+1的作用是等概率返回1和7，并没有什么用。其实，为了靠近g()，我们第二步要引入二进制和位运算了。对二进制而言，每一位有2种可能（即0或1），那两位就有$2^2$种可能，三位就有$2^3$种可能…思路开了，要实现$[1,7]$范围内的整数等概率返回，我们需要三位。所以每一位都调用一次f1()就可以实现$[0,7]$范围内的整数等概率返回，这里的“每一位都调用”显然是要用到左移运算符<<，实现的函数不妨称为f2()。

到这里已经很接近我们的目标函数g()了，区别只是多了个返回值0而已。回顾一下f1()的实现过程就可以发现，当f2()返回0时，让它再调用一次就行了。至此，我们就实现了目标函数g()。

代码实现

package com.test;

public class Test {
    /*
     只可借助，不可改动
     实现[1,5]范围内的整数等概率返回
     */
    public static int f(){
        return (int)(Math.random() * 5) + 1;
    }

    // 实现0和1等概率返回
    public static int f1(){
        int num;
        do{
            num = f();
        }while(num == 3);
        return (num < 3) ? 0 : 1;
    }

    // 实现[0,7]范围内的整数等概率返回
    public static int f2(){
        return (f1() << 2) + (f1() << 1) + f1();
    }

    // 实现[1,7]范围内的整数等概率返回
    public static int g(){
        int num;
        do{
            num = f2();
        }while(num == 0);
        return num;
    }

    public static void main(String[] args) {
        int[] count = new int[7];
        int testTime = 1000000;
        for(int i = 0; i < testTime; i++){
            count[g()-1]++;
        }
        for(int i = 0; i < 7; i++){
            System.out.println("数字"+(i+1)+"出现的概率为："+(double)count[i]/(double)testTime);
        }
    }
}

举一反三

如果f()函数可以等概率返回$[3,19]$范围内的整数，要实现g()函数等概率返回$[20,56]$范围内的整数。

依然是按照“三步走战略”，第一步先创建01发生器函数f1()：f()函数返回$[3,10]$时f1()返回0；f()函数返回$[12,19]$时f1()返回1；f()函数返回11时重来。第二步找到要返回$[20,56]$范围内的整数有37个，需要用到6个二进制位，即总共调用6次f1()函数，等概率返回$[0,63]$范围内的整数，实现f2()函数。第三步让f2()函数返回$[0,19]$或$[56,63]$范围内的整数时重新调用，其他情况正常返回，即可得到g()函数。