一个面试问题：关于概率 [英] An interview question: About Probability

问题描述

这是面试问题：

给定一个函数f（x），该1/4倍返回0，3/4倍返回1。 写使用F一函数g（x）（X）的1/2倍返回0，1.5倍返回1。

Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1. Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 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)
            }       
    }
}

我说得对不对？你对此有何解决方案？（你可以用任何语言）

Am I right? What's your solution?(you can use any language)

推荐答案

如果您在一行中调用函数f（x）的两倍，下面的结果是可能的（假设 连续调用函数f（x）是独立，同分布的试验）：

If you call f(x) twice in a row, the following outcomes are possible (assuming that successive calls to f(x) are independent, identically distributed trials):

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适当地：

01 and 10 occur with equal probability. So iterate until you get one of those cases, then return 0 or 1 appropriately:

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

return a;

这可能是很有诱惑力的调用函数f（x）只有每次迭代一次，并保持两者的轨道 最新的值，但将无法正常工作。假设的第一辊是1， 以概率3/4。你最好循环，直到第一个0，则返回1（概率为3/4）。

It might be tempting to call f(x) only once per iteration and keep track of the two most recent values, but that won't work. Suppose the very first roll is 1, with probability 3/4. You'd loop until the first 0, then return 1 (with probability 3/4).

这篇关于一个面试问题：关于概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！