随机数生成原理实现方法不同编程语言的随机数函数.docx
- 文档编号:16637524
- 上传时间:2023-07-15
- 格式:DOCX
- 页数:39
- 大小:28.35KB
随机数生成原理实现方法不同编程语言的随机数函数.docx
《随机数生成原理实现方法不同编程语言的随机数函数.docx》由会员分享,可在线阅读,更多相关《随机数生成原理实现方法不同编程语言的随机数函数.docx(39页珍藏版)》请在冰点文库上搜索。
随机数生成原理实现方法不同编程语言的随机数函数
1-0:
MicrosoftVC++产生随机数的原理:
Srand()和Rand()函数。
它本质上是利用线性同余法,y=ax+b(modm)。
其中a,b,m都是常数。
因此rand的产生决定于x,x被称为Seed。
Seed需要程序中设定,一般情况下取系统时间作为种子。
它产生的随机数之间的相关性很小,取值范围是0—32767〔int〕,即双字节〔16位数〕,假设用unsignedint双字节是65535,四字节是4294967295,一般可以满足要求。
1-1:
线性同余法:
其中M是模数,A是乘数,C是增量,为初始值,当C=0时,称此算法为乘同余法;假设C≠0,那么称算法为混合同余法,当C取不为零的适当数值时,有一些优点,但优点并不突出,故常取C=0。
模M大小是发生器周期长短的主要标志,常见有M为素数,取A为M的原根,那么周期T=M-1。
例如:
a=1220703125
a=32719〔程序中用此组数〕
a=16807
代码:
voidmain()
{
constintn=100;
doublea=32719,m=1,f[n+1],g[n],seed;
m=pow(2,31);
cout<<"设置m值为"< cout<<"输入种子"< cin>>seed; f[0]=seed; for(inti=1;i<=n;i++)//线性同余法生成随机数 { f[i]=fmod((a*f[i-1]),(m-1)); g[i-1]=f[i]/(m-1); cout.setf(ios: : fixed);cout.precision(6);//设置输出精度 cout< } } 1-2: 人字映射 递推公式 就是有名的混沌映射中的“人字映射〞或称“帐篷映射〞,它的非周期轨道点的分布密度函数: 人字映射与线性同余法结合,可产生统计性质优良的均匀随机数。 for(inti=1;i<=n;i++)//线性同余法生成随机数 { f[i]=fmod((a*f[i-1]),m); if(f[i]<=m/2)//与人字映射结合生成随机数 { f[i]=2*f[i]; } else { f[i]=2*(m-f[i])+1; } 1-3: 平方取中法——冯•诺伊曼 1946年前后,由冯• for(j=1;j<=n;j++) { i[j]=i[j-1]*i[j-1]; i[j]=i[j]/pow(10,5); i[j]=fmod(i[j],pow(10,10)); g[j]=i[j]/pow(10,10); cout.setf(ios: : fixed);cout.precision(6);//设置输出精度 cout< } 二: 任意分布随机数的生成 利用(0,1)均匀分布的随机数可以产生任意分布的随机数。 主要的方法有反函数法,舍选法,离散逼近法,极限近似法和随机变量函数法等。 这里主要讨论了反函数法,当然对于详细分布函数可以采用不同的方法。 设随机变量X具有分布函数F(X),那么对一个给定的分布函数值,X的值为 其中inv表示反函数。 现假设r是(0,1)均匀分布的随机变量R的一个值,R的分布函数为 因此,假设r是R的一个值,那么X具有概率 也就是说假设(r1,r2,...,rn)是R的一组值,那么相应可得到的一组值 具有分布。 从而,假设我们分布函数的反函数,我们就可以从(0,1)分布的均匀分布随机数得到所需分布的随机数了。 1-4: 指数分布: 指数分布的分布函数为: x<0时,F(x)=0;,F(x)=1-exp 利用上面所述反函数法,可以求得: x=ln(1-y),这里不妨取常数为1. for(intj=0;j { i=rand()%100;//产生从0-32767的任意一个值 a[j]=double(i)/double(100); a[j]=-log(a[j]);//常数大于0,这里取1 、、、、、、、 1-5: 正态分布: 正态分布的概率密度是: 正态分布的分布函数是: 对于正态分布,利用反函数的方法来获取正态分布序列显然是很费事的,牵涉到很复杂的积分微分运算,同时为了方便,我们取,即标准正态分布。 因此这里介绍了两种算法: 第一种: 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的任意一个值 b[j]=double(p)/double(100); a[j]=sqrt(-2*log(a[j]))*cos(2*3.1415926*b[j]); 第二种: 近似生成标准正态分布,独立同分布的多个随机变量和的分布趋近于正态分布,取k个均匀分布的(0,1)随机变量,,……,那么它们的和近似服从正态分布。 理论中,取k=12,(因为D()=1/12),那么新的随机变量y=x1+x2+...+x12-6,可以求出数学期望E(y)=0,方差D(y)=12*1/12=1,因此可以近似描绘标准正态分布 这几天再看数据构造和算法,中间遇到了生成不重复的随机数的问题 我先想到的一个算法是这样的: Generator(vector { srand(time(NULL)); vector intsize=num; for(inti=1;i<=num;++i) { v.push_back(i); } for(inti=0;i { vector : iteratorit=v.begin(); intn=rand()%(size--); it+=n; vec.push_back(*it); v.erase(it); } } 但是由于vector删除效率很低,所以这个算法在10W的时候已经不可承受了,需要17秒左右,后来在网上看到有朋友提出了另一种算法,感觉不错,于是又测试了一下 voidGen(vector { srand(time(NULL)); for(inti=0;i vec.push_back(i+1); for(inti=0;i swap(vec.at(i),vec.at(rand()%num)); } 这个算法是线性的,在10W的时候还可以,需要1.7秒左右,可是100W的时候就要17秒左右了。 想问一下,有没有更高效的生成算法? ________________________________________ 回复: 问一个关于随机数生成算法的问题 lz应该把要求说的详细点 一定要vector? ________________________________________ 回复: 问一个关于随机数生成算法的问题 同意楼上的。 要生成不重复的随机数,楼主可以自己写一个随机数生成程序啊,为什么一定要用rand()函数? 楼主假设真的对随机数感兴趣,建议楼主看一看Knuth的? 计算机程序设计艺术? 第二卷。 可以用线性同余法: A(n+1)=(a*A(n)+c)%M生成取遍1至M-1的所有整数,前提是参数a,c,M选取适宜。 ________________________________________ 回复: 问一个关于随机数生成算法的问题 STL主要目的是提供一个通用高速的算法,假设对一个专用的功能而且追求很高的效率,最好使用最原始数据类型和直接手写的算法。 下面给出我刚刚写好的一个程序,在VC6下编译通过,当n=100万时,仅需0.78秒。 //csdn_5398401.cpp: Definestheentrypointfortheconsoleapplication. #include"stdafx.h" #include"memory.h" #include"stdlib.h" #include"windows.h" typedefunsignedcharBYTE; typedefunsignedlongDWORD; voidtest(intn) { inti,c; DWORDidx; DWORD*pBuff; BYTE*pMask; BYTEmaskArr[]={1,2,4,8,16,32,64,128}; //---------- c=(n+7)/8; pMask=newBYTE[c]; pBuff=newDWORD[n]; memset(pMask,0,sizeof(BYTE)*c); memset(pBuff,0,sizeof(DWORD)*n); for(i=1;i { idx=(rand()<<15)+rand(); idx%=n;//随机得到一个0ton之间地址,n>x>=0, if((pMask[idx/8]&maskArr[idx%8])==0)//pBuff[x]没有存储过任何数 { pMask[idx/8]|=maskArr[idx%8];//置1 pBuff[idx]=i; i++; } } //--------- delete[]pMask; delete[]pBuff; } intmain(intargc,char*argv[]) { DWORDt=GetTickCount(); test(1000000); t=GetTickCount()-t; printf("Ittake%dms\n",t); return0; } Java中随机数生成的几种方法 java产生随机数的几种方式 ⏹在j2se里我们可以使用Math.random()方法来产生一个随机数,这个产生的随机数是0-1之间的一个double,我们可以把他乘以一定的数,比方说乘以100,他就是个100以内的随机,这个在j2me中没有。 ⏹在java.util这个包里面提供了一个Random的类,我们可以新建一个Random的对象来产生随机数,他可以产生随机整数、随机float、随机double,随机long,这个也是我们在j2me的程序里经常用的一个取随机数的方法。 ⏹在我们的System类中有一个currentTimeMillis()方法,这个方法返回一个从1970年1月1号0点0分0秒到目前的一个毫秒数,返回类型是long,我们可以拿他作为一个随机数,我们可以拿他对一些数取模,就可以把他限制在一个范围之内啦 其实在Random的默认构造方法里也是使用上面第三种方法进展随机数的产生的 对于方法二中的Random类有以下说明: 不带种子: 此种方式将会返回随机的数字,每次运行结果不一样 publicclassRandomTest{ publicstaticvoidmain(String[]args){ for(inti=0;i<10;i++){ } } 带种子: 此种方式,无论程序运行多少次,返回结果都是一样的 publicstaticvoidmain(String[]args){ for(inti=0;i<10;i++){ } } 两种方式的差异在于 (1)首先请翻开JavaDoc,我们会看到Random类的说明: 此类的实例用于生成伪随机数流,此类使用48位的种子,该种子可以使用线性同余公式对其进展修改〔请参阅DonaldKnuth的? TheArtofComputerProgramming,Volume2? ,第节〕。 假设用一样的种子创立两个Random实例,那么对每个实例进展一样的方法调用序列,它们将生成并返回一样的数字序列。 为了保证实现这种特性,我们为类Random指定了特定的算法。 为了Java代码的完全可移植性,Java实现必须让类Random使用此处所示的所有算法。 但是允许Random类的子类使用其他算法,只要其符合所有方法的常规协定即可。 JavaDoc对Random类已经解释得非常明白,我们的测试也验证了这一点。 (2)假设没有提供种子数,Random实例的种子数将是当前时间的毫秒数,可以通过System.currentTimeMillis()来获得当前时间的毫秒数。 翻开JDK的源代码,我们可以非常明确地看到这一点。 /** *Createsanewrandomnumbergenerator.Itsseedisinitializedto *avaluebasedonthecurrenttime: */ publicRandom(){this(System.currentTimeMillis());} 另外: random对象的nextInt(),nextInt(intn)方法的说明: intnextInt() 返回下一个伪随机数,它是此随机数生成器的序列中均匀分布的int值。 intnextInt(intn) 返回一个伪随机数,它是从此随机数生成器的序列中取出的、在0〔包括〕和指定值〔不包括〕之间均匀分布的int值。 C++中随机数生成方法 标准库 函数一: intrand(void); 从srand(seed)中指定的seed开始,返回一个[seed,RAND_MAX〔0x7fff〕)间的随机整数。 函数二: voidsrand(unsignedseed); 参数seed是rand()的种子,用来初始化rand()的起始值。 可以认为rand()在每次被调用的时候,它会查看: 1〕假设用户在此之前调用过srand(seed),给seed指定了一个值,那么它会自动调用 srand(seed)一次来初始化它的起始值。 2〕假设用户在此之前没有调用过srand(seed),它会自动调用srand (1)一次。 根据上面的第一点我们可以得出: 1〕假设希望rand〔〕在每次程序运行时产生的值都不一样,必须给srand(seed)中的seed一个变值,这个变值必须在每次程序运行时都不一样〔比方到目前为止流逝的时间〕。 2〕否那么,假设给seed指定的是一个定值,那么每次程序运行时rand〔〕产生的值都会一样,虽然这个值会是[seed,RAND_MAX〔0x7fff〕)之间的一个随机获得的值。 3〕假设在调用rand()之前没有调用过srand(seed),效果将和调用了srand (1)再调用rand()一样〔1也是一个定值〕。 举几个例子,假设我们要获得0~6之间的随机整数〔不含6本身〕: 例一,不指定seed: for(inti=0;i<10;i++){ ran_num=rand()%6; cout< } 每次运行都将输出: 5544540042 例二,指定seed为定值1: srand (1); for(inti=0;i<10;i++){ ran_num=rand()%6; cout< } 每次运行都将输出: 5544540042 跟例子一的结果完全一样。 例三,指定seed为定值6: srand(6); for(inti=0;i<10;i++){ ran_num=rand()%6; cout< } 每次运行都将输出: 4151434422 随机值也是在[0,6〕之间,随得的值跟srand (1)不同,但是每次运行的结果都一样。 例四,指定seed为当前系统流逝了的时间〔单位为秒〕: time_ttime(0): #include //… srand((unsigned)time(0)); for(inti=0;i<10;i++){ ran_num=rand()%6; cout< } 第一次运行时输出: 0154502342 第二次: 3230355223 总之,每次运行结果将不一样,因为每次启动程序的时刻都不同〔间隔须大于1秒? 见下〕。 关于time_ttime(0): time_t被定义为长整型,它返回从1970年1月1日零时零分零秒到目前为止所经过的时间,单位为秒。 比方假设输出: cout<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 随机数 生成 原理 实现 方法 不同 编程 语言 函数