algorithm - 一道面试题: About Probability

Question

一道面试题:

给定函数 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)
            }       
    }
}

我说的对吗？你的解决方案是什么？(你可以使用任何语言)

Answer 1

如果连续调用 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)。