随机数的生成(C++)

1、第一章随机数生成方法一、引言在C+中常用的随机数生成方法是首先使用rand函数生成一个随机数，然后将生成的随机数映射到所需要的区间。但是在使用rand函数之前需要使用srand设置初始“种子”以保证每次生成的随机数都不相同。在实际应用中，通常使用系统当前时间作为“种子” 这样生成的随机数更接近于实际意义的随机数。程序1为生成指定区间的随机数的代码。程序1生成start到end之间的一个随机数template<type name T>T ran dom(T start, T en d)return start+(e nd-start)*ra nd()/(RAND_MAX + 1.0)

2、;int mai n()srand(un sig ned(time(O);int r = ran dom(0,10);cout<<"ge nerate a ran dom data in 0, 10:'匕<r<< en dl; return 0;但是以上的生成算法有两个问题:1.rand生成的最大随机数为32767,有时无法达到我们的要求；2每个生成的随机数的概率未必相等，例如要生成0,30000之间的随机数，这种做法就会导致后面生成的随机数的概率偏小。在唐纳德克努特(Donald Ervin Knuth)的经典巨著计算机程序设计的艺术中，有一

3、章专门介绍了生成随机数的方法。程序2为来自crafty19.3的源码，它是对计算机程序设计的艺术中2.2.2节的实现。程序2生成一个32位的随机数/*A 32 bit random number generator. An implementation in C of the algorithm given byKn uth, the art of computer program ming, vol. 2, pp. 26-27. We use e=32, sowe have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2A32, which is

4、 implicitly done by un sig ned arithmetic.*/un sig ned int Ran dom32(void) /*ran dom n umbers from Mathematica 2.0.SeedRa ndom = 1;TableRandomInteger, 0, 2人32 - 1*/static c on stu nsig nedl ong x55 = 1410651636UL, 3012776752UL, 3497475623UL, 2892145026UL, 1571949714UL, 3253082284UL, 3489895018UL, 38

5、7949491UL, 2597396737UL, 1981903553UL, 3160251843UL, 129444464UL, 1851443344UL, 4156445905UL, 224604922UL,1455067070UL, 3953493484UL, 1460937157UL, 2528362617UL, 317430674UL, 3229354360UL, 117491133UL, 832845075UL, 1961600170UL, 1321557429UL, 747750121UL, 545747446UL, 810476036UL, 503334515UL, 40881

6、44633UL, 2824216555UL, 3738252341UL, 3493754131UL, 3672533954UL, 29494241UL, 1180928407UL, 4213624418UL, 33062851UL, 3221315737UL, 1145213552UL, 2957984897UL, 4078668503UL, 2262661702UL, 65478801UL, 2527208841UL, 1960622036UL, 315685891UL, 1196037864UL, 804614524UL, 1421733266UL, 2017105031UL, 38823

7、25900UL, 810735053UL, 384606609UL, 2393861397UL ; static int init = 1;static u nsig nedl ong y55;static i nt j, k;un sig nedl ong ul;if (in it)int i;in it = 0;for (i = 0; i < 55; i+)yi = xi;j = 24 - 1;k = 55 - 1;ul = (yk += yj);if (-j < 0)j = 55 - 1;if (-k < 0)k = 55 - 1;retur n(un sig ned

8、in t)ul);二、生成大范围的随机数通常情况下可以使用将生成的多个随机数拼接在一起，以获得更大范围的随机数。人程序3拼接生成一个32位的随机数long r =(l on g)ra nd()<<16)|(lo ng)ra nd()<<8)&0X0000FF00L)|(lo ng)ra nd()&0X000000FFL);使用STL可以很方便的生成一个随机序列，其中主要是同gen erate算法直接生成，程序4展示生成的过程。程序3通过STL的gen erate生成随机序列#include <iostream>#include <cti

9、me>#include <cstdlib>#include <vector>#ineludealgorithmusing namespacestd ;classra nd_n umpublic :rand_n um(i nt m = 31)if( m<1 | m>31 )throw ran ge_error('ra nge out ,please in put in teger in 1,31");mask = (1<<m)-1 ;long operator()()重载()以方便 gen erate算 法的调用return

10、 (ra nd()& 3)<<30)+(ra nd()<<15)+ra nd()&mask;private :un sig nedlo ng mask ;用于获得相应位数的随机数的掩码;int mai n()vector< longarr(10);srand(un sig ned(time(0);rand_num r ;generate(arr.begin(), arr.end(), r);vectorvlong>:iterator it = arr.begin();while( it != arr.e nd()cout<v*it+v&

11、lt;e ndl ;return 0;J三、生成任意分布的随机数一般的情况可以利用rand函数均匀的生成每个数，然后将某一区间的随机数映射为一个数，但这种生成算法无法模拟符合某一分布的随机数。下面以正态分布为例来说明生成任意分布随机数的算法。如果一个随机数序列服从一维正态分布，那么它有如下的概率密度函数：1 _込 f(x)= e 2 v2(t其中卩，6为常数，它们分别为数学期望和均方差。图1为卩=0=0.2时的曲线。从图中可以看出，在卩附近的概率密度大，远离卩的地方概率密度小，我们要产生的随机数要服从这种分布，就是要使产生的随机数在卩附近的概率要大，远离卩处小。算法的主要思想是：在图1的大矩形

12、中随机产生点，这些点是平均分布的，如果产生的点落在概率密度曲线的下方，则认为产生的点是符合要求的，将它们保留，如果在概率密度曲线的上方， 则认为这些点不合格，将它们去除。如果随机产生了一大批在整个矩形中均匀分布的点，那么被保留下来的点的横坐标就服从了正态分布。可以设想，由于在卩处的f(x)的值比较大，理所当然的在附近的点个数要多， 远离处的少，这从面积上就可以看出来。 我们要产生 的随机数就是这里的横坐标。程序3为生成正态分布的程序。图1正态分布的概率密度函数曲线程序3生成正态分布随机数#define PI 3.14159265double Normal( double x,double mi

13、u,double sigma) / 概率密度函数return 1.0/sqrt(2*PI*sigma) * exp(-1*(x-miu)*(x-miu)/(2*sigma*sigma); double NormalRa ndom(double miu,double sigma,double mi n,double max) / 产生正态分布随机数double x;double dScope;double y;dox = AverageRa ndom (min, max);y = Normal(x, miu, sigma);dScope = AverageRa ndom(0, Normal(mi

14、u,miu,sigma); while ( dScope > y);return x;参数说明：doublemiu :卩，正态函数的数学期望doublesigma:，正态函数的均方差doublemin, max :表明产生的随机数的范围四、生成各不相同的随机数通常的生成随机数的做法是不考虑重复的，因为即使重复也属于概率意义上的正常情 况。要产生一定范围内不可重复的随机数，最朴素的想法是把曾经生成的随机数保存起来作为历史数据。将每一个新产生的随机数都与历史数据进行比较，如果不相同则认为产生了一个新的随机数，否则丢弃后重新进行搜索。程序5为这种思想的实现。程序5生成不重复的随机数在min,

15、max区间生成num个不相同的随机数int *ran dom (int num, int min, int max)if( num > max-min )throw ran ge_error('ra nge error");int *result = new i nt num; 用来保存随机生成的不重复的数int tmp = -1;bool repeat = false;for (int i = 0; i < n um; i+)repeat = false;tmp = ran dom (min, max);for (int j = 0; j < i; j+)

16、 if (tmp = resultj)repeat = true;break;if (!repeat) resulti = tmp; else i = i - 1; 循环变量-1retur n result ;对于生成数量较少的随机数,这种方法简单易行,但是如果给出的范围比较小,那么新 产生的随机数就会以极大的概率与已有的数据相同。为了达到较好的一种效果，通常使用额外的空间。其主要的思想是：生成一个有序的互不相同的数列，生成一个小于序列长度的随机数，并将序列中对应位置的元素作为结果，然后将序列最后一个元素复制到对应位置，序列长度减一，重复以上操作直到找到所有的数。程序6为以上算法的实现。程序6生成不重复的随机数生成num个不相同的随机数int *ran dom (int n um)int in dexRAND_MAX;for (int i = 0; i < RAND_MAX;