algorithm - 面试问题:关于概率

面试题:

给定一个函数f(x)1/4倍返回0，3/4倍返回1。
使用f(x)编写一个函数g(x)，其中1/2倍返回0,1 / 2倍返回1。

我的实现是:

function g(x) = {
    if (f(x) == 0){ // 1/4
        var s = f(x)
        if( s == 1) {// 3/4 * 1/4
            return s  //   3/16
        } else {
            g(x)
        }
    } else { // 3/4
            var k = f(x)
            if( k == 0) {// 1/4 * 3/4
                return k // 3/16
            }  else {
                g(x)
            }
    }
}

我对吗？您有什么解决方案？(可以使用任何语言)

最佳答案

如果您连续两次调用f(x)，则可能会出现以下结果(假设
连续调用f(x)是独立的，分布均匀的试验):

00 (probability 1/4 * 1/4)
01 (probability 1/4 * 3/4)
10 (probability 3/4 * 1/4)
11 (probability 3/4 * 3/4)

01和10发生的可能性相等。如此反复，直到得到其中之一
情况，然后适当地返回0或1:

do
  a=f(x); b=f(x);
while (a == b);

return a;

诱使每次迭代仅调用f(x)并跟踪两者
最新的值，但这行不通。假设第一卷为1，
概率为3/4。您将循环直到第一个0，然后返回1(概率为3/4)。