2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，
现在要你构造一个发生器，
使得它构造0和1的概率均为 1/2；
构造一个发生器，使得它构造1、2、3 的概率均为 1/3； ...，
构造一个发生器，使得它构造 1、2、3、...n 的概率均为1/n，要求复杂度最低。
/* 2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p， 现在要你构造一个发生器， 使得它构造0和1的概率均为 1/2； 构造一个发生器，使得它构造1、2、3 的概率均为 1/3； ...， 构造一个发生器，使得它构造 1、2、3、...n 的概率均为1/n，要求复杂度最低。 思路： 由于需要产生1/2，而用1位0，或1位1无法产生等概率， 因此，考虑将随机数扩展成2位： 00 p*p 01 p*(1-p) 10 (1-p)*p 11 (1-p)*(1-p) 有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。 于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。 对于n=2，一次性生成两个数字，认为01表示0，10表示1， 其它情况放弃，它们的概率都是p*(1-p)； 对于n=3，一次性生成三个数字，认为001表示0，010表示1，100表示2， 其它情况放弃，它们的概率都是p*p*(1-p)； 对于n=4，一次性生成是个数字，认为0001表示0，0010表示1，0100表示2，1000表示3， 其它情况放弃，它们的概率都是p*p*p*(1-p)； 5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x， 此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃， 这时候剩下六个:0011,0101,0110,1001,1010,1100， 取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5， 这时候他们的概率都是p*p*(1-p)*(1-p)相等了。 关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率。 因为C(n,i)最大是在i接近n/2的地方取得，此时我有更大比率的序列用于生成， 换句话说被抛掉的更少了，这样做是为了避免大量生成了丢弃序列而使得生成速率减慢， 实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等， 比如C(2x,x)的概率就是[p(1-p)]^x， 互等的样例空间内保证了对应的每个值取得的样例等概率。 */