之前群里探讨过一道根底算法题，提到过不止一次了，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函数123123123#生成组合3,4,5,4,5,6,5,6,74,5,6,5,6,7,6,7,85,6,7,6,7,8,7,8,9#每个数字概率3=14=35=66=77=68=39=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的倍数。