概率面试题
1. 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它产生0和1的概率均为1/2
由题目有：
0 : p
1 : 1-p
连续产生两个数，其组合以及概率如下：
00 : p2
01 : p*(1-p)
10 : (1-p)*p
11 : (1-p)2
可以发现 01 和 10 组合的概率是相等的，只需要将其分别映射到0和1即可。即每次随机产生两个数，如果组合为00或11则丢弃，若为01则映射到1，若为10则映射到0，这样一来产生0和1的概率均为 1/2 。
2.已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10
已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10()随机1~10。
【试题分析】
1）要保证rand10()在整数1-10的均匀分布，可以构造一个1-10*n的均匀分布的随机整数区间（n为任何正整数）。假设x是这个1-10*n区间上的一个随机整数，那么x%10+1就是均匀分布在1-10区间上的整数。
2）接下来利用(rand7()-1)*7+rand7()构造出均匀分布在1-49的随机数：
首先rand7()-1得到一个离散整数集合{0，1，2，3，4，5，6}，其中每个整数的出现概率都是1/7。那么(rand7()-1)*7得到一个离散整数集合A={0，7，14，21，28，35，42}，其中每个整数的出现概率也都是1/7。而rand7()得到的集合B={1，2，3，4，5，6，7}中每个整数出现的概率也是1/7。显然集合A和B中任何两个元素组合可以与1-49之间的一个整数一一对应，也就是说1-49之间的任何一个数，可以唯一确定A和B中两个元素的一种组合方式，反过来也成立。由于A和B中元素可以看成是独立事件，根据独立事件的概率公式P(AB)=P(A)P(B)，得到每个组合的概率是1/7*1/7=1/49。因此(rand7()-1)*7+rand7()生成的整数均匀分布在1-49之间，每个数的概率都是1/49。
3）由于出现的每个数的出现都是相对独立的，所以剔除41-49后剩下1-40也应该是均匀分布。
def rand10(): while True: x=(rand7()-1)*7+rand7() if x<=40: break return x%10+1
3.题目：给定一个函数rand5()，该函数可以随机生成1-5的整数，且生成概率一样。现要求使用该函数构造函数rand7()，使函数rand7()可以随机等概率的生成1-7的整数。
思路：
很多人的第一反应是利用rand5() + rand()%3来实现rand7()函数，这个方法确实可以产生1-7之间的随机数，但是仔细想想可以发现数字生成的概率是不相等的。rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。
正确的方法是利用rand5()函数生成1-25之间的数字，然后将其中的1-21映射成1-7，丢弃22-25。
def rand7(): while True: x=(rand5()-1)*5+rand5() if x<=21: break return x%7+1
4. 已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。
使用该随机发生器产生随机数a，b，有以下3种情况：(1)a<b, (2) a == b, (3) a>b，其中情况（1）和（3）是对称的，发生的概率相等，只需要将这两种情况分别映射到0和1即可，其中遇到a==b时忽略。
5. 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，构造一个发生器，使得它构造1、2、3的概率均为1/3。
我们可以产生一个由0和1组成的序列，序列中0和1的个数相等，即各出现一半的情况下每种排列出现的概率都是相等的。
例如，产生100,010,001的概率都是p*p*(1-p)，概率相等，其它情况都丢弃，这三种情况分别映射到1,2,3即可，同类问题均此解法。