一个长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执行停在该断点处的时候。
对学习编程者的忠告:
眼过千遍不如手过一遍!
书看千行不如手敲一行!
手敲千行不如单步一行!
单步源代码千行不如单步对应汇编一行!
单步类的实例“构造”或“复制”或“作为函数参数”或“作为函数返回值返回”或“参加各种运算”或“退出作用域”的语句对应的汇编代码几步后,就会来到该类的“构造函数”或“复制构造函数”或“运算符重载”或“析构函数”对应的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 的概率
倒推后面问题也出来,不好处理了! 一时没查资料还真不好想啊!
不晓得暴力穷举能不能解决了,但是感觉有简单的
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
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。
循环10000次(或者更多)
每次产生N个0-100的随机数,相加,和3000比较,结果是大于的计数。
10000次的计数结果累加 /10000
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。
#7
该使用 独立同分布的中心极限定理
#8
大牛 求解释
#9
另外这个是求出近似值 还是精确值?
#10
感觉这个不是算法题,是概率题,在概率论中应该会有公式解决的!
#11
高数
#12
确实应该是概率论的题
#13
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n" 小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
#14
看看算法导论第5章
#15
这么高端
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n" 小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
#16
这么高端应该是近似值,如截图所示,我们假设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
这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个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
大概还有捷径、、、需要大家发挥聪明才智了
这么高端应该是近似值,如截图所示,我们假设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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4
#24
数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值, 总共有5000中取法。
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4
总共有 101的50次方种取法。。。。
#25
大概还有捷径、、、需要大家发挥聪明才智了
这么高端应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n" 小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。
#26
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?
。。。整数。。。必须是整数
#31
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
我觉得的这题少给了一个重要条件,这些 [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;
这就是状态方程
那么dp【i+1】【j+k】(0<=k<=100) += dp【i】【j】 * 1 / 101;
这就是状态方程
#34
最后求得前3000的概率之和x,用1 - x即为大于3000的概率
#35
算法导论里有过这个导论.好像是
#36
最后求得前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
这题不是应该考虑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);
}
然后就用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))。
而这个多项式乘法可以用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执行停在该断点处的时候。
对学习编程者的忠告:
眼过千遍不如手过一遍!
书看千行不如手敲一行!
手敲千行不如单步一行!
单步源代码千行不如单步对应汇编一行!
单步类的实例“构造”或“复制”或“作为函数参数”或“作为函数返回值返回”或“参加各种运算”或“退出作用域”的语句对应的汇编代码几步后,就会来到该类的“构造函数”或“复制构造函数”或“运算符重载”或“析构函数”对应的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 的概率
倒推后面问题也出来,不好处理了! 一时没查资料还真不好想啊!
不晓得暴力穷举能不能解决了,但是感觉有简单的
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
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。
循环10000次(或者更多)
每次产生N个0-100的随机数,相加,和3000比较,结果是大于的计数。
10000次的计数结果累加 /10000
得到近似的概率。
如果要精确的概率要好好想想算法。概率论都忘记光了。
#7
该使用 独立同分布的中心极限定理
#8
该使用 独立同分布的中心极限定理
大牛 求解释
#9
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
#10
感觉这个不是算法题,是概率题,在概率论中应该会有公式解决的!
#11
高数
#12
高数
确实应该是概率论的题
#13
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
#14
看看算法导论第5章
#15
这么高端
应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n" 小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
#16
这么高端应该是近似值,如截图所示,我们假设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
这道题不是要求程序开发者给出精确的值,而是让你用一个程序去模拟,如何验证理论上给出的结果,所以要实现的东西包括,如何概率均等地产生一个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
大概还有捷径、、、需要大家发挥聪明才智了
这么高端应该是近似值,如截图所示,我们假设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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4
#24
数组有50个数,每个数有100中取值,且等概率,而且每个数的取值不会影响其他数取值, 总共有5000中取法。
这50个数的和的范围为50-5000,就是说有一部分的取值他们的值是相同的,3000将(50,5000)分成两个区间2950和2000,由于每个数取值的概率都相同,所以这两个区间和相同的取法的数目也相同,因此大于3000的概率为2000/5000=0.4
总共有 101的50次方种取法。。。。
#25
大概还有捷径、、、需要大家发挥聪明才智了
这么高端应该是近似值,如截图所示,我们假设N=50已经足够大,实际上也确实够了、、欲求西格玛Xk大于3000的概率,可以先算西格玛Xk小于3000的概率,即"(西格玛Xk-nu)/o根号n" 小于等于 "(3000-nu)/o根号n" 的概率.后者可以算出,然后查表可以得到这个概率,最后用1减去这个概率就可以了
该使用 独立同分布的中心极限定理
另外这个是求出近似值 还是精确值?
如果觉得 N=50 不够大,就只能用类似线性规划的方法了,在50维的空间中求出分量和大于3000的子空间的体积。蛋疼的是,这时又觉得 N=50 太大了。
碰到这种题,我觉得还是用蒙特卡洛法吧,这样连续和离散的情况都能处理。
#26
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
我觉得的这题少给了一个重要条件,这些 [0,100] 的数字,是实数还是整数?
。。。整数。。。必须是整数
#31
如果用蒙特卡洛法,基于对称性可将子空间分量之和划为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
我觉得的这题少给了一个重要条件,这些 [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;
这就是状态方程
那么dp【i+1】【j+k】(0<=k<=100) += dp【i】【j】 * 1 / 101;
这就是状态方程
#34
最后求得前3000的概率之和x,用1 - x即为大于3000的概率
#35
算法导论里有过这个导论.好像是
#36
最后求得前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
这题不是应该考虑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);
}
然后就用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))。
而这个多项式乘法可以用FFT做。假设一次试验的取值范围有n,总共m次试验。动态规划的方法等价于f(x)自乘乘m-1次,复杂度O((nm)^2),而FFT的话只要O(nm*log(nm))。