面试问题：关于概率

面试问题：

给定一个函数f（x），1/4返回0，3/4返回1.用f（x）写1/2函数g（x）返回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) } } } 

我对吗？ 你的解决scheme是什么？（你可以使用任何语言）

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）。

Answer 2

你的解决scheme是正确的，如果效率低下，并有更多的重复逻辑。 这是一个清洁的forms相同的algorithm的Python实现。

 def g (): while True: a = f() if a != f(): return a 

如果f（）是昂贵的，你会希望得到更复杂的使用匹配/不匹配信息来尝试返回与更less的调用。 这是最有效的解决scheme。

 def g (): lower = 0.0 upper = 1.0 while True: if 0.5 < lower: return 1 elif upper < 0.5: return 0 else: middle = 0.25 * lower + 0.75 * upper if 0 == f(): lower = middle else: upper = middle 

这平均需要大约2.6个电话给g() 。

它的工作方式是这样的。 我们试图从0到1中select一个随机数，但是一旦我们知道数字是0还是1，我们就会停下来。我们开始知道这个数字是在区间（0,1）中。 数字的3/4位于间隔的底部3/4，而1/4位于间隔的顶部1/4。 我们根据对f(x)的调用来决定。 这意味着我们现在处于一个较小的区间。

如果我们清洗，冲洗，并重复足够的时间，我们可以尽可能精确地确定我们的有限数量，并将在原始区间的任何区域有绝对相等的清盘概率。 特别是，我们甚至有大于或小于0.5的收盘概率。

如果你想要的话，你可以重复这个想法，逐一产生无尽的比特stream。 事实上，这是产生这种stream的最有效方式，也是信息论中熵的概念的来源。

Answer 3

你的algorithm的问题是它重复自己的概率很高。 我的代码：

 function g(x) = { var s = f(x) + f(x) + f(x); // s = 0, probability: 1/64 // s = 1, probability: 9/64 // s = 2, probability: 27/64 // s = 3, probability: 27/64 if (s == 2) return 0; if (s == 3) return 1; return g(x); // probability to go into recursion = 10/64, with only 1 additional f(x) calculation } 

我测量了algorithm和我的algorithm的平均次数f(x) 。 对于你的f(x)计算约为每g(x)计算5.3次。 用我的algorithm，这个数字减less到3.5左右。 到目前为止，其他答案也是如此，因为它们实际上与您所说的algorithm相同。

PS：你的定义目前没有提到“随机”，但可能是假定的。 看到我的其他答案。

Answer 4

 Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1 

从字面上看，f（x）如果调用四次，将总是返回零一次和三次。 这与说f（x）是一个概率函数不同，在许多迭代中，0到1的比例将接近1到3（1/4 vs 3/4）。 如果第一种解释是有效的，那么f（x）的唯一有效函数将满足条件，而不pipe序列中从何处开始的顺序是0111重复。 （或1011或1101或1110，它们是从不同起点开始的相同序列）。 鉴于这种限制，

  g()= (f() == f()) 

应该足够了。

Answer 5

如前所述，您的定义在概率方面不太好。 通常意味着不仅可能性好，而且distribution也是。 否则，你可以简单地写g（x），这将返回1,0,1,0,1,0,1,0 – 它将返回他们50/50，但数字不会是随机的。

另一个作弊手段可能是：

 var invert = false; function g(x) { invert = !invert; if (invert) return 1-f(x); return f(x); } 

这个解决scheme比其他所有方法都要好，因为它只调用一次f(x) 。 但结果不会很随意。

Answer 6

对于每g()结果达到平均约1.85的调用f()下面logging的进一步改进实现了〜1.75，tbilly's〜2.6，Jim Lewis的被接受的答案~5.33）。 代码在答案中显得较低。

基本上，我产生0到3范围内的随机整数，甚至有可能：调用者然后可以testing第一个50/50的值为0，第一个为第一个。 原因：1/4和3/4的f()概率比两半更干净地映射到宿舍。

---

algorithm描述

只是解释了algorithm，但我也会用我自己的方式来做…

该algorithm基本上生成0到1之间的随机实数x ，然后根据数字落在哪个“结果桶”中返回结果：

 result bucket result x < 0.25 0 0.25 <= x < 0.5 1 0.5 <= x < 0.75 2 0.75 <= x 3 

但是，给定一个只有f()的随机实数是很困难的。 我们必须从我们的x值应该在0..1范围内的知识入手，我们将这个范围称为我们的初始“可能的x”空间。 然后，我们磨合x的实际值：

• 每次我们调用f() ：
  • 如果f()返回0（4中的概率为1），我们认为x处于“可能的x”空间的较低的四分之一，并且从该空间中消除了前三个四分之三
  • 如果f()返回1（4中的概率为3），我们认为x在“可能的x”空间的上部四分之三中，并且从该空间中消除了较低的四分之一
  • 当“可能的x”空间完全被单个结果桶包含时，这意味着我们已经缩小了x直到我们知道应该映射哪个结果值，并且不需要为x获得更具体的值。

它可能会或可能不会帮助考虑这个图:-)：

  "result bucket" cut-offs 0,.25,.5,.75,1 0=========0.25=========0.5==========0.75=========1 "possible x" 0..1 | | . . | f() chooses x < vs >= 0.25 | result 0 |------0.4375-------------+----------| "possible x" .25..1 | | result 1| . . | f() chooses x < vs >= 0.4375 | | | . ~0.58 . | "possible x" .4375..1 | | | . | . | f() chooses < vs >= ~.58 | | ||. | | . | 4 distinct "possible x" ranges 

---

码

 int g() // return 0, 1, 2, or 3 { if (f() == 0) return 0; if (f() == 0) return 1; double low = 0.25 + 0.25 * (1.0 - 0.25); double high = 1.0; while (true) { double cutoff = low + 0.25 * (high - low); if (f() == 0) high = cutoff; else low = cutoff; if (high < 0.50) return 1; if (low >= 0.75) return 3; if (low >= 0.50 && high < 0.75) return 2; } } 

如果有帮助的话，一个中间人一次只能输出50/50的结果：

 int h() { static int i; if (!i) { int x = g(); i = x | 4; return x & 1; } else { int x = i & 2; i = 0; return x ? 1 : 0; } } 

注意：这个algorithm可以进一步调整，从考虑一个f（）== 0的结果转换到下一个季度的磨合，而不是在上一个季度进行磨合，根据这个结果平均解决一个结果桶更快。 从表面上看，这在第三次调用f（）时很有用，当上四分之一的结果表示立即结果为3，而下四分之一的结果仍然跨越概率点0.5，因此结果为1和2.当我尝试它时，结果实际上更糟。 为了看到实际的好处，需要更复杂的调整，最后我写了g（）的第二个到第十一个调用的低级和高级截断的powershell比较。 我发现最好的结果是平均值为1.75，这是由于g（）寻求低（即设置low = cutoff ）的第1,2,5和8次。

Answer 7

这是一个基于中心极限定理的解决scheme，最初是由于我的一个朋友：

 /* 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. */ #include <iostream> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; int f() { if (rand() % 4 == 0) return 0; return 1; } int main() { srand(time(0)); int cc = 0; for (int k = 0; k < 1000; k++) { //number of different runs int c = 0; int limit = 10000; //the bigger the limit, the more we will approach %50 percent for (int i=0; i<limit; ++i) c+= f(); cc += c < limit*0.75 ? 0 : 1; // c will be 0, with probability %50 } printf("%d\n",cc); //cc is gonna be around 500 return 0; } 

Answer 8

由于f（）的每个返回代表了3/4的TRUE可能性，所以有一些代数我们可以恰当地平衡可能性。 我们想要的是另一个函数x（），它返回TRUE的平衡概率

 function g() { return f() && x(); } 

50％的时间返回真实。

那么让我们findx（p（x））的概率，给定p（f）和我们想要的总概率（1/2）：

 p(f) * p(x) = 1/2 3/4 * p(x) = 1/2 p(x) = (1/2) / 3/4 p(x) = 2/3 

所以x（）应该以2/3的概率返回TRUE，因为2/3 * 3/4 = 6/12 = 1/2;

因此，以下应该适用于g（）：

 function g() { return f() && (rand() < 2/3); } 

Answer 9

假设

 P(f[x] == 0) = 1/4 P(f[x] == 1) = 3/4 

并要求具有下列假设的函数g[x]

 P(g[x] == 0) = 1/2 P(g[x] == 1) = 1/2 

我相信g[x]的下面的定义是足够的（Mathematica）

 g[x_] := If[f[x] + f[x + 1] == 1, 1, 0] 

或者可选地在C中

 int g(int x) { return f(x) + f(x+1) == 1 ? 1 : 0; } 

这是基于{f[x], f[x+1]}调用会产生以下结果的想法

 { {0, 0}, {0, 1}, {1, 0}, {1, 1} } 

总结我们有的每个结果

 { 0, 1, 1, 2 } 

其中1的总和表示可能的总和结果的1/2，而另一个总和则构成另一半的总和。

编辑。 由于bdk表示 – {0,0}比{1,1}更不可能，因为

 1/4 * 1/4 < 3/4 * 3/4 

然而，我自己感到困惑，因为给定f[x] （Mathematica）的下列定义，

 f[x_] := Mod[x, 4] > 0 /. {False -> 0, True -> 1} 

或者在C中

 int f(int x) { return (x % 4) > 0 ? 1 : 0; } 

那么从执行f[x]和g[x]得到的结果似乎具有预期的分布。

 Table[f[x], {x, 0, 20}] {0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0} Table[g[x], {x, 0, 20}] {1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1} 

Answer 10

这很像蒙蒂霍尔悖论。

一般来说。

 Public Class Form1 'the general case ' 'twiceThis = 2 is 1 in four chance of 0 'twiceThis = 3 is 1 in six chance of 0 ' 'twiceThis = x is 1 in 2x chance of 0 Const twiceThis As Integer = 7 Const numOf As Integer = twiceThis * 2 Private Sub Button1_Click(ByVal sender As System.Object, _ ByVal e As System.EventArgs) Handles Button1.Click Const tries As Integer = 1000 y = New List(Of Integer) Dim ct0 As Integer = 0 Dim ct1 As Integer = 0 Debug.WriteLine("") ''show all possible values of fx 'For x As Integer = 1 To numOf ' Debug.WriteLine(fx) 'Next 'test that gx returns 50% 0's and 50% 1's Dim stpw As New Stopwatch stpw.Start() For x As Integer = 1 To tries Dim g_x As Integer = gx() 'Debug.WriteLine(g_x.ToString) 'used to verify that gx returns 0 or 1 randomly If g_x = 0 Then ct0 += 1 Else ct1 += 1 Next stpw.Stop() 'the results Debug.WriteLine((ct0 / tries).ToString("p1")) Debug.WriteLine((ct1 / tries).ToString("p1")) Debug.WriteLine((stpw.ElapsedTicks / tries).ToString("n0")) End Sub Dim prng As New Random Dim y As New List(Of Integer) Private Function fx() As Integer '1 in numOf chance of zero being returned If y.Count = 0 Then 'reload y y.Add(0) 'fx has only one zero value Do y.Add(1) 'the rest are ones Loop While y.Count < numOf End If 'return a random value Dim idx As Integer = prng.Next(y.Count) Dim rv As Integer = y(idx) y.RemoveAt(idx) 'remove the value selected Return rv End Function Private Function gx() As Integer 'a function g(x) using f(x) that 50% of the time returns 0 ' that 50% of the time returns 1 Dim rv As Integer = 0 For x As Integer = 1 To twiceThis fx() Next For x As Integer = 1 To twiceThis rv += fx() Next If rv = twiceThis Then Return 1 Else Return 0 End Function End Class