关于算法:一道rand5生成rand7的算法题

之前群里探讨过一道根底算法题，提到过不止一次了，rand5()产生rand7()，看起来很简略，其实也有不少小心机，也算是一个很乏味且奇妙的题目了。尽管网上也有很多答案，但有的并不够循序渐进，所以写篇文章，理下思路。

原题是这样的，“Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.”

题目说的很简略，然而蕴含了一些尽管没说，然而大家都默认的一些根本束缚，即你只能使用rand5这个已知函数和一些简略的运算符，不能引入一些其它函数或封装非凡运算符。但如果你认为它真的简略，那可能你就要栽了。

我想，应该没有呆头呆脑的人会这样实现吧

int rand7(){
    return 2+rand5();
    }

为什么这样不对，因为很简略，这个函数无奈生成1，不符合条件。

那如果这样呢？

int rand7()
{
     int i;
     i = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
     return i%7 + 1;
 }

看起来如同没问题，利用5跟7的最小公倍数，7个5，再模7，每个数字概率是1/5，不正好就是1-7嘛。
实际上，这也是错的。

第4行代码中，将会产生5^7种可能的计算，最终这些可能映射到[7,35]的整数区间中，然而[7,35]区间内整数的产生的概率并不相等。看起来有点懵，咱们换个更简略的例子来阐明下，如果有一个rand3的()函数，3个rand3()能生成[3-9]这个区间的数字，然而[3-9]这个区间的数字是不平均的。

#多个rand函数
123
123
123
#生成组合
3,4,5,4,5,6,5,6,7
4,5,6,5,6,7,6,7,8
5,6,7,6,7,8,7,8,9
#每个数字概率
3=1
4=3
5=6
6=7
7=6
8=3
9=1

其实，略微对数字有点敏感的人也能立马判断进去，2+4=6，4+2=6，显然两头的数字有多种组合，呈现的概率就会更高。这就引申出一个高中数学的概率问题了，“一对夫妇生了两个孩子 ,其中一个是男孩,问另一个是女孩的概率是多少?”。这两个问题实质上是一样的。

那么正确的做法应该是怎么呢？
思路还是那个思路，rand7的要害不仅是生成1-7之间的数字，还要保障这个数字是随机的，也就是概率均等。做到概率均等，才算正确。
如果这么写呢？

int rand7()
{
    int vals[5][5] = {
        {1,2,3,4,5},
        {6,7,1,2,3},
        {4,5,6,7,1},
        {2,3,4,5,6},
        {7,0,0,0,0}
    };
    int result = 0;
    while(result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i - 1][j - 1];
    }
    return result;
}

当时构建一个方阵，外面平均地放着1-7这七个数，而后rand5只用来生成坐标，这样对否？
咱们来看是否满足以下两束缚：
1.生成1-7这七个数。
2.1-7呈现的概率均等

第一个条件，无疑满足。第二个条件，1-7这几个数字，每个数字呈现的概率是3/25，尽管这个矩阵里有0这个纯正用来填充的数字（是0还是10，都不重要），但不障碍1-7呈现的概率均等的束缚。

然而这样的写法毕竟太丑，也用了额定的空间，换种形式，其实方阵的做法，转换成更简略的代码，应该是

int rand7()
{
    int i;
    do{
        i = 5 * (rand5() - 1) + rand5();    //产生[1,25]的整数区间
    }while(i > 21);                            //将[1,25]整数区间管制于[1,21]
    return i%7 + 1;                            //将[1,21]映射到[1,7]
}

实际上，这个题是算法导论里的一道题，也是互联网大公司的八股文算法题，是有通用模板的。下面的5和7，能够替换成任意的a,b，只须要满足(a<b)即可。

即如果给你Randa， 你能够通过以下形式轻松结构Randb，生成1到b的随机数。

Randb = a * (Randa – 1) + Randa

如果已知rand7,要生成rand5呢？很简略，把6和7排除掉就是rand5了，也就是当随机到大于5的时候，就再随机一次，直到小于等于5。

int rand5(){
    Rint result = rand7()+1;
    while (result > 5){
        result = rand7()+1;
    }
    return result;

}

很简略，但也是正确的做法。其实跟下面说的rand5生成rand7的思路是一样的，先利用rand5把范畴放大，而后再排除掉超出的范畴，使这个范畴是7的倍数。