一道概率论的面试题 求大牛解答找不到算法区，就发在这了一个长N的数组（比如长度是50）每个数在0-100闭区间以均等的概率随机求这个数组（50个数）之和大于某个值（比如3000）的概率是多少？应该怎么算？ [解决办法]
#include <cassert>#include <cmath>#include <map>#include <iostream>#include <vector>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 < N); if (n < 0) { return 1; } if (n > 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 <= 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<std::map<int,double>> 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->second >= 0); return it->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 << problem_t{n_elements,upper_limit}(starting_index,target_threshold) << std::endl;}
