问题：一个API，以概率p输出1，以概率1-p输出0，请你设计以算法，call这个API，以概率1/2输出1，以概率1/2输出0

 

答案：连续call 2次这个api, 如果输出序列是01，那么就输出0，如果是10，那么就输出1，是其它情况（00，11），重做一遍前面的步骤

 

算法的证明：

第一轮call 2次这个api，产生的序列的概率是01 (1-p)*p, 10 p*(1-p), 00 (1-p)^2, 11 p^2，按照我们的算法（答案），以 (1-p)*p的概率输出0，以p*(1-p)的概率输出1，以(1-p)^2+p^2的概率重新执行我们的算法，此时输出0的概率是(1-p)*p + ((1-p)^2+p^2)*(1-p)*p， 输出1的概率是p*(1-p) + ((1-p)^2+p^2)*p*(1-p)，再以((1-p)^2+p^2)^2的概率重现执行我们的算法。。。可以看出，按照我们的算法，产生1的概率是一个级数，并且是收敛的，因为0<(1-p)^2+p^2<1，很容易计算它等于0.5，同理产生0的概率也是0.5。

 

类似的问题：

一个API，能等概率地产生1-5的整数，如果call这个api，等概率地产生1-7的整数