从一个不平均概率分布获得一个平均的概率分布

昨天百度二面有个题目是这样的，设一个随机函数p()返回0的概率是t，返回1的概率是1-t，问如何重新封装这个函数，得到一个新函数，使均匀输出0和1。

当时不及细想，脑子里面就蹦出个做两次p()然后抑或一下，是不是就好了呢，说了出来，然后立刻被我自己找到反例了。

然后想到的办法是，做两次p()，如果两次相同，则继续做两次，否则把第一次的结果返回。说了出来，显然这个是一个正确的方法，面试官也认可了，不过我也跟他说，这个是不考虑效率的办法，然后他问我，期望要做多少次才能返回……囧爆了，列了个多项式出来了，求了一会，告诉他，这个不好算诶……然后他也放弃问这个问题了。

刚刚躺在床上，灵机一动，让我想到一个更优美的办法。定义一个变量，这个变量每次调换都0、1调换。然后当这个变量是1的时候，原样返回p()，否则返回!p()。这样子就每次调用一次即可了：

#include <cstdio>
#include <ctime>
#include <cstdlib>
 
bool p(){
    return rand()%3==0;
}
 
bool f(){
//  return p()==p()?false:true;///Wrong Answer
//  while(true){///Right, but slow
//      bool a=p();
//      bool b=p();
//      if(a==b)continue;
//      return a;
//  }
    static bool x=false;
    x=!x;
    return x?p():!p();///Right, and fast
}
 
int main(){
    srand(time(NULL));
    int p1=0,f1=0;
    for(int i=0;i<1000;i++){
        if(p()){
            p1++;
            putchar('1');
        }else{
            putchar('0');
        }
    }
    puts("");
    for(int i=0;i<1000;i++){
        if(f()){
            f1++;
            putchar('1');
        }else{
            putchar('0');
        }
    }
    puts("");
    printf("%d %d\n",p1,f1);
    return 0;
}

上面是实验代码。实际上，这个新加入的变量，相当于我自己的随机数表，所以就调整成平均的了。