面试问题：关于概率

作者: 喜欢一个人丶
发布时间: 2025-02-05 04:39:32 (2小时前)
转自：

5 条回复

0#
回复此人
回忆氵独奏♪ | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这很像蒙蒂霍尔悖论。 </p> <P> 一般来说。 </p> <pre> <code> 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 </code> </pre> </DIV>

编辑
1#
回复此人
v-star*위위 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 如前所述，您的定义在概率上并不是那么好。通常这意味着不仅概率好，而且 <code> distribution </code> 也。否则你可以简单地写g（x）将返回1,0,1,0,1,0,1,0 - 它将返回50/50，但数字不会是随机的。 </p> <P> 另一种欺骗方法可能是： </p> <pre> <code> var invert = false; function g(x) { invert = !invert; if (invert) return 1-f(x); return f(x); } </code> </pre> <P> 这个解决方案比其他所有解决方案更好 <code> f(x) </code> 只有一次。但结果不会很随意。 </p> </DIV>

编辑
2#
回复此人
甲基蓝 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <pre> <code> Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1 </code> </pre> <P> 从字面上看这个陈述，f（x）如果被调用四次将总是返回零一次和1次3次。这与说f（x）是概率函数不同，并且0到1的比率在许多次迭代中将接近1到3（1/4对3/4）。如果第一种解释是有效的，那么满足条件的f（x）的唯一有效函数，无论您从哪个序列开始，都是序列0111重复。（或1011或1101或1110，它们是来自不同起点的相同序列）。鉴于这种约束， </p> <pre> <code> g()= (f() == f()) </code> </pre> <P> 应该足够了。 </p> </DIV>

编辑
3#
回复此人
哇。 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这是一个基于中心极限定理的解决方案，最初是由于我的一位朋友： </p> <pre> <code> /* 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; } </code> </pre> </DIV>

编辑

登录后才能参与评论