《2022年随机数的算法分析 .pdf》由会员分享，可在线阅读，更多相关《2022年随机数的算法分析 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、随机数的算法分析1-0：Microsoft VC+产生随机数的原理：Srand()和 Rand()函数。它本质上是利用线性同余法，y=ax+b(mod m)。其中 a，b，m都是常数。因此rand 的产生决定于x，x 被称为 Seed。Seed 需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是032767（int），即双字节（16 位数），若用unsigned int 双字节是65535，四字节是4294967295，一般可以满足要求。1-1：线性同余法：?/P其中 M 是模数，A 是乘数，C 是增量，为初始值，当C=0 时，称此算法为乘同余法；若C0，
2、则称算法为混合同余法，当C 取不为零的适当数值时，有一些优点，但优点并不突出，故常取 C=0。模 M 大小是发生器周期长短的主要标志，常见有 M 为素数，取 A 为 M 的原根，则周期 T=M-1。例如：a=1220703125 a=32719 （程序中用此组数）a=16807 代码：void main()名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -const int n=100;double a=32719,m=1,fn+1,gn,seed;m=pow(2,31);cout设置 m 值为m-1endl;cout输入种子 seed;f0=seed;for(int i
3、=1;i=n;i+)/线性同余法生成随机数fi=fmod(a*fi-1),(m-1);gi-1=fi/(m-1);cout.setf(ios:fixed);cout.precision(6);/设置输出精度couti tgi-1就是有名的混沌映射中的“人字映射”或称“帐篷映射”，它的非周期轨道点的分布密度函数：人字映射与线性同余法结合，可产生统计性质优良的均匀随机数。for(int i=1;i=n;i+)/线性同余法生成随机数fi=fmod(a*fi-1),m);if(fi=m/2)/与人字映射结合生成随机数fi=2*fi;elsefi=2*(m-fi)+1;名师资料总结-精品资料欢迎下载-名
4、师精心整理-第 3 页，共 7 页 -1-3：平方取中法 冯 诺伊曼1946 年前后，由冯 诺伊曼提出，他的办法是去前面的随机数的平方，并抽取中部的数字。例如要生成10 位数字，而且先前的值是5772156649，平方后得到33317792380594909201，所以下一个数是7923805949。for(j=1;j=n;j+)ij=ij-1*ij-1;ij=ij/pow(10,5);ij=fmod(ij,pow(10,10);gj=ij/pow(10,10);cout.setf(ios:fixed);cout.precision(6);/设置输出精度coutjtgjendl;二：任意分布随
5、机数的生成利用(0，1)均匀分布的随机数可以产生任意分布的随机数。主要的方法有反函数法，舍选法，离散逼近法，极限近似法和随机变量函数法等。这里主要讨论了反函数法，当然对于具体分布函数可以采用不同的方法。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -设随机变量X 具有分布函数F(X)，则对一个给定的分布函数值，X 的值为其中 inv 表示反函数。现假设r 是(0，1)均匀分布的随机变量R 的一个值，已知R 的分布函数为因此，如果r 是 R 的一个值，则X 具有概率也就是说如果(r1,r2,.,rn)是 R 的一组值，则相应可得到的一组值具有分布。从而，如果我们已知分布函
6、数的反函数，我们就可以从(0，1)分布的均匀分布随机数得到所需分布的随机数了。1-4：指数分布：指数分布的分布函数为:x0 时,F(x)=0 ；,F(x)=1-exp利用上面所述反函数法，可以求得:x=ln(1-y)，这里不妨取常数为 1.for(int j=0;jn;j+)i=rand()%100;/产生从 0-32767 的任意一个值名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -aj=double(i)/double(100);aj=-log(aj);/常数大于 0，这里取 1、1-5：正态分布：正态分布的概率密度是：正态分布的分布函数是：对于正态分布，利用反函数
7、的方法来获取正态分布序列显然是很麻烦的，牵涉到很复杂的积分微分运算，同时为了方便，我们取，即标准正态分布。因此这里介绍了两种算法：第一种：Box 和 Muller 在 1958 年给出了由均匀分布的随机变量生成正态分布的随机变量的算法。设U1,U2 是区间(0,1)上均匀分布的随机变量，且相互独立。令X1=sqrt(-2*log(U1)*cos(2*PI*U2);X2=sqrt(-2*log(U1)*sin(2*PI*U2);那么 X1,X2 服从 N(0,1)分布，且相互独立。p=rand()%100;/产生从 0-32767 的任意一个值bj=double(p)/double(100);aj=sqrt(-2*log(aj)*cos(2*3.1415926*bj);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -第二种：近似生成标准正态分布，独立同分布的多个随机变量和的分布趋近于正态分布,取 k 个均匀分布的(0,1)随机变量，则它们的和近似服从正态分布。实践中,取 k=12,(因为 D()=1/12),则新的随机变量y=x1+x2+.+x12-6，可以求出数学期望 E(y)=0,方差 D(y)=12*1/12=1，因此可以近似描述标准正态分布。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -