共计 1911 个字符，预计需要花费 5 分钟才能阅读完成。
之前群里探讨过一道根底算法题，提到过不止一次了，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 的倍数。