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

时间:2022-08-22 19:06:19
找不到算法区,就发在这了


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

求这个数组(50个数)之和大于某个值(比如3000)的概率是多少?
应该怎么算?

40 个解决方案

#1


计算机组成原理→DOS命令→汇编语言→C语言(不包括C++)、代码书写规范→数据结构、编译原理、操作系统→计算机网络、数据库原理、正则表达式→其它语言(包括C++)、架构……

对学习编程者的忠告:
眼过千遍不如手过一遍!
书看千行不如手敲一行!
手敲千行不如单步一行!
单步源代码千行不如单步对应汇编一行!

单步类的实例“构造”或“复制”或“作为函数参数”或“作为函数返回值返回”或“参加各种运算”或“退出作用域”的语句对应的汇编代码几步后,就会来到该类的“构造函数”或“复制构造函数”或“运算符重载”或“析构函数”对应的C/C++源代码处。

VC调试时按Alt+8、Alt+7、Alt+6和Alt+5,打开汇编窗口、堆栈窗口、内存窗口和寄存器窗口看每句C对应的汇编、单步执行并观察相应堆栈、内存和寄存器变化,这样过一遍不就啥都明白了吗。
对VC来说,所谓‘调试时’就是编译连接通过以后,按F10或F11键单步执行一步以后的时候,或者在某行按F9设了断点后按F5执行停在该断点处的时候。

#2


自己顶~~~

#3


复习《概率论与数理统计》

#4


直接让面试官给算法。。。这题除了暴力穷举应该没其他好办法,这数据量还要考虑大数,根本不是面试时能做出来的

#5


假设有M个数组成的数据, 在[0,100]等概率选数,;

M个数之和大于N的概率

思路:逆向推断

一个数组为a[101] = {0,1,2,...,100};

每个数出现一个一次的概率是1/101;

a[0] + a[1] + a[2] + .... +a[M-1]  之和大于N
也就是a[i] 的平均值大于 N/M 的概率

倒推后面问题也出来,不好处理了! 一时没查资料还真不好想啊!

不晓得暴力穷举能不能解决了,但是感觉有简单的

#6


最简单淳朴的想法是:
循环10000次(或者更多)
每次产生N个0-100的随机数,相加,和3000比较,结果是大于的计数。
10000次的计数结果累加 /10000
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。 一道概率论的面试题 求大牛解答

#7


该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答

#8


引用 7 楼 zhctj159 的回复:
该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


大牛 求解释

#9


引用 7 楼 zhctj159 的回复:
该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?

#10


感觉这个不是算法题,是概率题,在概率论中应该会有公式解决的!

#11


高数 一道概率论的面试题 求大牛解答

#12


引用 11 楼 defonds 的回复:
高数 一道概率论的面试题 求大牛解答

确实应该是概率论的题

#13


引用 9 楼 zilaishuichina 的回复:
Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了

#14


看看算法导论第5章

#15


一道概率论的面试题 求大牛解答这么高端

引用 13 楼 zhctj159 的回复:
Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了

#16


引用 15 楼 gpshq 的回复:
一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

#17


这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个0到100的随机数,然后根据给定的数组长度n去产生n个随机数,求和后判断是否大于3000,如果满足则j++,j初始化0,重复m次试验,将模拟得到的概率j/m,输出。理论上的概率是当n<30的时候,概率为0;当n>=30时,这个嘛,不会了!!!

#18


引用 17 楼 zhaowech 的回复:
这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个0到100的随机数,然后根据给定的数组长度n去产生n个随机数,求和后判断是否大于3000,如果满足则j++,j初始化0,重复m次试验,将模拟得到的概率j/m,输出。理论上的概率是当n<30的时候,概率为0;当n>=30时,这个嘛,不会了!!!


。。。

#19


说到均等的随机,参考洗牌算法:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
            for (i=n;i>0;i--) {/* 打乱0~n-1 */
                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
    printf("shuffle 1..n demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=1;i<=n;i++) d[i]=i;/* 填写1~n */
            for (i=n;i>1;i--) {/* 打乱1~n */
                a=i;b=rand()%i+1;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=1;i<=n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
}

#20


引用 16 楼 zhctj159 的回复:
Quote: 引用 15 楼 gpshq 的回复:

一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。

#21


如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。

#22


引用 21 楼 lpcads 的回复:
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

#23


数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值,总共有5000中取法。
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4

#24


引用 23 楼 congya001 的回复:
数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值, 总共有5000中取法
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4


总共有 101的50次方种取法。。。。

#25


引用 20 楼 lpcads 的回复:
Quote: 引用 16 楼 zhctj159 的回复:

Quote: 引用 15 楼 gpshq 的回复:

一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。
50够大了,,以前算的时候独立同分布大多是几十个就可以近似成正态了

#26


引用 22 楼 zilaishuichina 的回复:
Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。

#27


引用 26 楼 lpcads 的回复:
Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答

#28


引用 27 楼 ananluowei 的回复:
Quote: 引用 26 楼 lpcads 的回复:

Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答

不是和你6楼的做法一样嘛,只不过如果只记大于3000的次数,样本数量可能太少。反正都是一趟,干脆把小于3000的情况也分分清楚,利用对称性使蒙特卡洛结果更准确一点

#29


我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?

#30


引用 29 楼 ri_aje 的回复:
我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?


。。。整数。。。必须是整数

#31


引用 27 楼 ananluowei 的回复:
Quote: 引用 26 楼 lpcads 的回复:

Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答


显然靠的数学 我觉得 

数学老师死的早啊

#32


引用 30 楼 zilaishuichina 的回复:
Quote: 引用 29 楼 ri_aje 的回复:

我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?


。。。整数。。。必须是整数

那就好办多了。下面先上数学,然后再上代码,顺便吐槽一下 csdn 的编辑器不支持 latex,写点儿公式真费劲,只好抓图了。
最重要的就是这个 (1) 号公式,显示了递归结构。
一道概率论的面试题 求大牛解答
然后是一些解释,为什么概率可以这么算。主要就是 a[i] 的不同取值是不相关事件,所以总概率等于各子事件概率的和。
一道概率论的面试题 求大牛解答
再然后是,递归终止条件,当序列只剩一个数字的时候,概率就很好算了,就是最简单的均匀分布。
一道概率论的面试题 求大牛解答
最后是两个边界条件,对于一些明显有问题的值,可以直接快速计算概率的。
一道概率论的面试题 求大牛解答
下面是个简单的程序,实现了上面的公式。这个递归可以用动态规划做,这样当子问题重复的时候,直接查找上次计算结果即可。

#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;
}

#33


简单的动态规划,dp【51】【3000】,dp【i】【j】表示前i个数和为j的概率
那么dp【i+1】【j+k】(0<=k<=100) += dp【i】【j】 * 1 / 101;
这就是状态方程

#34


最后求得前3000的概率之和x,用1 - x即为大于3000的概率

#35


算法导论里有过这个导论.好像是

#36


引用 34 楼 HH_YT 的回复:
最后求得前3000的概率之和x,用1 - x即为大于3000的概率

求得前2000的概率之和x,用x即为大于3000的概率 

#37


这题不是应该考虑dp么?应该是个非常简单的背包问题吧?dp[i][j]表示已经用了i个数,组和出的和为j的概率,j的范围0-5000,i从1到50。递推算完之后,将3001到5000的值累加起来不就可以了?

#38


引用 37 楼 No__stop 的回复:
这题不是应该考虑dp么?应该是个非常简单的背包问题吧?dp[i][j]表示已经用了i个数,组和出的和为j的概率,j的范围0-5000,i从1到50。递推算完之后,将3001到5000的值累加起来不就可以了?

j的范围2000-2500就行了

#39


从0-100 取 50个数而这50个数又可以重复出现 这个组合是 101^50 (第一个数有101个可能,第二个也有101个可能,。。。第50个也有101个可能)是非常大的 
然后就用for loop 由50个0。。。0开始 loop 到 50 个100 如果大于3000 的就 count++ 就可以了 
概率就是 count/(101^50)

a[N]={0,0,....,0}
float fun(int N, int sum) //N=50,sum=3000
{
int aSum=0;
int count=0;
int position = 0;
while(a[0]<=100 && a[N-1]<=100 && position<N)
{
aSum=0;
for(int i=0;i<N;i++)
{
aSum+=a[i];
}
if(aSum>sum) count++;

if(a[position]<100) a[positon]++;
else position++;
}
return count/(101.0^N);
}

#40


还有比动态规划更快的办法。用生成函数。一次试验的生成函数就是f(x)=(1+x+...+x^100)/101。50次试验就是f(x)^50,这个函数的x^k系数就是总和为k的概率。
而这个多项式乘法可以用FFT做。假设一次试验的取值范围有n,总共m次试验。动态规划的方法等价于f(x)自乘乘m-1次,复杂度O((nm)^2),而FFT的话只要O(nm*log(nm))。

#1


计算机组成原理→DOS命令→汇编语言→C语言(不包括C++)、代码书写规范→数据结构、编译原理、操作系统→计算机网络、数据库原理、正则表达式→其它语言(包括C++)、架构……

对学习编程者的忠告:
眼过千遍不如手过一遍!
书看千行不如手敲一行!
手敲千行不如单步一行!
单步源代码千行不如单步对应汇编一行!

单步类的实例“构造”或“复制”或“作为函数参数”或“作为函数返回值返回”或“参加各种运算”或“退出作用域”的语句对应的汇编代码几步后,就会来到该类的“构造函数”或“复制构造函数”或“运算符重载”或“析构函数”对应的C/C++源代码处。

VC调试时按Alt+8、Alt+7、Alt+6和Alt+5,打开汇编窗口、堆栈窗口、内存窗口和寄存器窗口看每句C对应的汇编、单步执行并观察相应堆栈、内存和寄存器变化,这样过一遍不就啥都明白了吗。
对VC来说,所谓‘调试时’就是编译连接通过以后,按F10或F11键单步执行一步以后的时候,或者在某行按F9设了断点后按F5执行停在该断点处的时候。

#2


自己顶~~~

#3


复习《概率论与数理统计》

#4


直接让面试官给算法。。。这题除了暴力穷举应该没其他好办法,这数据量还要考虑大数,根本不是面试时能做出来的

#5


假设有M个数组成的数据, 在[0,100]等概率选数,;

M个数之和大于N的概率

思路:逆向推断

一个数组为a[101] = {0,1,2,...,100};

每个数出现一个一次的概率是1/101;

a[0] + a[1] + a[2] + .... +a[M-1]  之和大于N
也就是a[i] 的平均值大于 N/M 的概率

倒推后面问题也出来,不好处理了! 一时没查资料还真不好想啊!

不晓得暴力穷举能不能解决了,但是感觉有简单的

#6


最简单淳朴的想法是:
循环10000次(或者更多)
每次产生N个0-100的随机数,相加,和3000比较,结果是大于的计数。
10000次的计数结果累加 /10000
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。 一道概率论的面试题 求大牛解答

#7


该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答

#8


引用 7 楼 zhctj159 的回复:
该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


大牛 求解释

#9


引用 7 楼 zhctj159 的回复:
该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?

#10


感觉这个不是算法题,是概率题,在概率论中应该会有公式解决的!

#11


高数 一道概率论的面试题 求大牛解答

#12


引用 11 楼 defonds 的回复:
高数 一道概率论的面试题 求大牛解答

确实应该是概率论的题

#13


引用 9 楼 zilaishuichina 的回复:
Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了

#14


看看算法导论第5章

#15


一道概率论的面试题 求大牛解答这么高端

引用 13 楼 zhctj159 的回复:
Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了

#16


引用 15 楼 gpshq 的回复:
一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

#17


这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个0到100的随机数,然后根据给定的数组长度n去产生n个随机数,求和后判断是否大于3000,如果满足则j++,j初始化0,重复m次试验,将模拟得到的概率j/m,输出。理论上的概率是当n<30的时候,概率为0;当n>=30时,这个嘛,不会了!!!

#18


引用 17 楼 zhaowech 的回复:
这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个0到100的随机数,然后根据给定的数组长度n去产生n个随机数,求和后判断是否大于3000,如果满足则j++,j初始化0,重复m次试验,将模拟得到的概率j/m,输出。理论上的概率是当n<30的时候,概率为0;当n>=30时,这个嘛,不会了!!!


。。。

#19


说到均等的随机,参考洗牌算法:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
            for (i=n;i>0;i--) {/* 打乱0~n-1 */
                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
    printf("shuffle 1..n demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=1;i<=n;i++) d[i]=i;/* 填写1~n */
            for (i=n;i>1;i--) {/* 打乱1~n */
                a=i;b=rand()%i+1;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=1;i<=n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
}

#20


引用 16 楼 zhctj159 的回复:
Quote: 引用 15 楼 gpshq 的回复:

一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。

#21


如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。

#22


引用 21 楼 lpcads 的回复:
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

#23


数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值,总共有5000中取法。
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4

#24


引用 23 楼 congya001 的回复:
数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值, 总共有5000中取法
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4


总共有 101的50次方种取法。。。。

#25


引用 20 楼 lpcads 的回复:
Quote: 引用 16 楼 zhctj159 的回复:

Quote: 引用 15 楼 gpshq 的回复:

一道概率论的面试题 求大牛解答这么高端

Quote: 引用 13 楼 zhctj159 的回复:

Quote: 引用 9 楼 zilaishuichina 的回复:

Quote: 引用 7 楼 zhctj159 的回复:

该使用 独立同分布的中心极限定理 一道概率论的面试题 求大牛解答


另外这个是求出近似值 还是精确值?
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n"  小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
大概还有捷径、、、需要大家发挥聪明才智了

如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。
50够大了,,以前算的时候独立同分布大多是几十个就可以近似成正态了

#26


引用 22 楼 zilaishuichina 的回复:
Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。

#27


引用 26 楼 lpcads 的回复:
Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答

#28


引用 27 楼 ananluowei 的回复:
Quote: 引用 26 楼 lpcads 的回复:

Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答

不是和你6楼的做法一样嘛,只不过如果只记大于3000的次数,样本数量可能太少。反正都是一趟,干脆把小于3000的情况也分分清楚,利用对称性使蒙特卡洛结果更准确一点

#29


我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?

#30


引用 29 楼 ri_aje 的回复:
我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?


。。。整数。。。必须是整数

#31


引用 27 楼 ananluowei 的回复:
Quote: 引用 26 楼 lpcads 的回复:

Quote: 引用 22 楼 zilaishuichina 的回复:

Quote: 引用 21 楼 lpcads 的回复:

如果用蒙特卡洛法,基于对称性可将子空间分量之和划为0-2000,2000-2500,2500-3000,3000-5000 四个范围,这样可以提高效率和准确度。


好高端的样子 求解释

其实一点都不高端。这里说的是0到100取数连续的情况,50个数值和(记为Z)最大为5000,最小为0,显然Z=0和Z=5000处的概率密度是一样的,不仅如此,事实上Z的概率密度函数f关于Z=2500对称(更精确的,f趋近高斯函数,前面的中心极限定理)。
如果模拟次数少,蒙特卡洛法的结果可能不太准确。可以在每次模拟时对四个区间计数(而不是仅对3000-5000)。设模拟结束后,计数值分别为n1,n2,n3,n4,记 m=n1+n2+n3+n4, 则所求概率为 n1/m , n4/m ,0.5-n2/m 或 0.5-n3/m ,可求平均值,或是求方差看看模拟误差有多大。


完全不懂 一道概率论的面试题 求大牛解答
话说,这面试题是考编程还是考数学啊。 一道概率论的面试题 求大牛解答


显然靠的数学 我觉得 

数学老师死的早啊

#32


引用 30 楼 zilaishuichina 的回复:
Quote: 引用 29 楼 ri_aje 的回复:

我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?


。。。整数。。。必须是整数

那就好办多了。下面先上数学,然后再上代码,顺便吐槽一下 csdn 的编辑器不支持 latex,写点儿公式真费劲,只好抓图了。
最重要的就是这个 (1) 号公式,显示了递归结构。
一道概率论的面试题 求大牛解答
然后是一些解释,为什么概率可以这么算。主要就是 a[i] 的不同取值是不相关事件,所以总概率等于各子事件概率的和。
一道概率论的面试题 求大牛解答
再然后是,递归终止条件,当序列只剩一个数字的时候,概率就很好算了,就是最简单的均匀分布。
一道概率论的面试题 求大牛解答
最后是两个边界条件,对于一些明显有问题的值,可以直接快速计算概率的。
一道概率论的面试题 求大牛解答
下面是个简单的程序,实现了上面的公式。这个递归可以用动态规划做,这样当子问题重复的时候,直接查找上次计算结果即可。

#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;
}

#33


简单的动态规划,dp【51】【3000】,dp【i】【j】表示前i个数和为j的概率
那么dp【i+1】【j+k】(0<=k<=100) += dp【i】【j】 * 1 / 101;
这就是状态方程

#34


最后求得前3000的概率之和x,用1 - x即为大于3000的概率

#35


算法导论里有过这个导论.好像是

#36


引用 34 楼 HH_YT 的回复:
最后求得前3000的概率之和x,用1 - x即为大于3000的概率

求得前2000的概率之和x,用x即为大于3000的概率 

#37


这题不是应该考虑dp么?应该是个非常简单的背包问题吧?dp[i][j]表示已经用了i个数,组和出的和为j的概率,j的范围0-5000,i从1到50。递推算完之后,将3001到5000的值累加起来不就可以了?

#38


引用 37 楼 No__stop 的回复:
这题不是应该考虑dp么?应该是个非常简单的背包问题吧?dp[i][j]表示已经用了i个数,组和出的和为j的概率,j的范围0-5000,i从1到50。递推算完之后,将3001到5000的值累加起来不就可以了?

j的范围2000-2500就行了

#39


从0-100 取 50个数而这50个数又可以重复出现 这个组合是 101^50 (第一个数有101个可能,第二个也有101个可能,。。。第50个也有101个可能)是非常大的 
然后就用for loop 由50个0。。。0开始 loop 到 50 个100 如果大于3000 的就 count++ 就可以了 
概率就是 count/(101^50)

a[N]={0,0,....,0}
float fun(int N, int sum) //N=50,sum=3000
{
int aSum=0;
int count=0;
int position = 0;
while(a[0]<=100 && a[N-1]<=100 && position<N)
{
aSum=0;
for(int i=0;i<N;i++)
{
aSum+=a[i];
}
if(aSum>sum) count++;

if(a[position]<100) a[positon]++;
else position++;
}
return count/(101.0^N);
}

#40


还有比动态规划更快的办法。用生成函数。一次试验的生成函数就是f(x)=(1+x+...+x^100)/101。50次试验就是f(x)^50,这个函数的x^k系数就是总和为k的概率。
而这个多项式乘法可以用FFT做。假设一次试验的取值范围有n,总共m次试验。动态规划的方法等价于f(x)自乘乘m-1次,复杂度O((nm)^2),而FFT的话只要O(nm*log(nm))。