一路概率论的面试题求大牛解答

一道概率论的面试题求大牛解答
找不到算法区，就发在这了

一个长N的数组（比如长度是50）
每个数在0-100闭区间以均等的概率随机

求这个数组（50个数）之和大于某个值（比如3000）的概率是多少？
应该怎么算？
[解决办法]

然后是一些解释，为什么概率可以这么算。主要就是 a[i] 的不同取值是不相关事件，所以总概率等于各子事件概率的和。
一路概率论的面试题求大牛解答

再然后是，递归终止条件，当序列只剩一个数字的时候，概率就很好算了，就是最简单的均匀分布。
一路概率论的面试题求大牛解答

最后是两个边界条件，对于一些明显有问题的值，可以直接快速计算概率的。
一路概率论的面试题求大牛解答

下面是个简单的程序，实现了上面的公式。这个递归可以用动态规划做，这样当子问题重复的时候，直接查找上次计算结果即可。


#include &lt;cassert&gt;
#include &lt;cmath&gt;
#include &lt;map&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;

struct problem_t
{
 double operator () (size_t const i, int const n) const
 {
  return f(i,n);
 }

 double f (size_t const i, int const n) const
 {
  assert(i &lt; N);

  if (n &lt; 0) { return 1; }
  if (n &gt; int(K*(N-i))) { return 0; }

  if (i+1 == N) // single integr probability.
  {
   return (K-n)/(K+1.);
  }
  else
  {
   double p = 0;
   for (size_t k = 0; k &lt;= K; ++k)
   {
    p += pf(i+1,n-k);
   }
   return p/(K+1.);
  }
 }

 double pf (size_t const i, int const n) const
 {
  static std::vector&lt;std::map&lt;int,double&gt;&gt; probabilities(N);
  auto& probs = probabilities[i];

  auto it = probs.find(n);
  if (probs.end() == it)
  {
   auto const ans = probs.insert({n,f(i,n)}); assert(ans.second);
   it = ans.first;
  }
  assert(it-&gt;second &gt;= 0);
  return it-&gt;second;
 }

 size_t const N; // # of elements in sequence.
 size_t const K; // upper limit, element value in [0,K].
};

int main ()
{
 size_t const n_elements       = 50;
 size_t const upper_limit      = 100;
 size_t const starting_index   = 0;
 size_t const target_threshold = 3000;
 std::cout &lt;&lt; problem_t{n_elements,upper_limit}(starting_index,target_threshold) &lt;&lt; std::endl;
}

一路概率论的面试题 求大牛解答

热点推荐

一路概率论的面试题求大牛解答