已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...，构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低；
没啥思路。
首先是1/2的情况，我们一次性生成两个数值，如果是00或者11丢弃，否则留下，01为1，10为0，他们的概率都是p*(1-p)是相等的，所以等概率了
让这个发生器， 发生2 次数：
有以下可能结果 （ 0， 0） （ 0， 1）（ 1，0） （1，1）
如果 产生 （0， 1） 就算为0， 如果产生 （1，0） 就算为1。 如果产生的是其它的，就放弃，重新发生。
3， 。。。。。。n 的结果， 可以类似产生
假设 p>=0.5, 以三为例子。
发生3回， 我们只取 有一回 1， 2回 0的情形。 如果 1， 发生在第一回， 算1， 发生在第2回，算 2， 第三回，算3.
4-n 可以类推。
然后是1/n的情况了，我们以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这样能提升查找效率
就是每次调用你你都生成一个1到n之间的数值，使得你生成这些数值出现都等概率
这种，等价于 有 n个球， 其中 n/2 个是白球， n-n/2个是黑球。
要将 这n个球 排列起来， 问有几种不同的排列方式。
假设 有 k个 排列方式， 则可以用n产生出 〈=k的等概率随机发生器
那只是那个公式的一个解释，我之所以取C(2x,x)是为了让同样的序列长度下可用的资源尽量多，因为C(n,i)最大是在i接近n/2的地方取得，此时我有更大比率的序列用于生成，换句话说被抛掉的更少了，这样做是为了避免大量生成了丢弃序列而使得生成速率减慢，其它的没什么特别的意思。
实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等，比如C(2x,x)的概率就是[p(1-p)]^x，互等的样例空间内保证了对应的每个值取得的样例等概率
PS：我真不明白你提取球干啥………………:em06:
同样道理，我也可以生成n次得到的01序列，比如n=5我只留下10000，01000，00100，00010，00001五个，每个同样是等概率，但是你碰上每个的机会都只剩下p*(1-p)^4，这么低的概率生成器的效率就是非常低下的，虽然也是一种实现
这个要看 p的大小的。 不一定比 发4次的概率小。 需要精细的计算。
我理解你的想法， 我就是用排列球来形象化你的想法。
不过 ，具体的效率高低， 要根据 p的大小，才能计算出来， 比如 要等概率的 5， 调用随机四回，不一定比 5回效率高。
随p的大小，不同而不同。
整体趋势是小的很快，比如你出现1的概率是0.1，那么出0的就是0.9了，所有可用的序列就是5*0.1*0.9^4=0.328左右，也就是将近七成的被丢弃了，更何况这时候n还是很小，如果n一大，这个丢弃率就接近100%了
如果 p的大小是 10的 -10次方，情况就不一样了， 虽然例子比较极端， 但题目里没说 p的范围。
只是一般情况下保证序列尽量短而且尽量减少丢弃率，当然想构造出数据也很容易，但是对于一般数据来说，特别是p很接近0.5的情况下，由于序列更短，获得使用的概率就更高，不说了，吃饭去……
其实只要有获得“1/2”的方法之后，以此为基础，对一个数的n个Bit位进行设置，就可以得到一个0~M（M=2^N - 1)的平均概率随机数，再使用这个数的前P个数即可大大提高效率。
这个题目很变态，n的话按位取n个数的效率太低
