隨機(jī)數(shù)的生成(C++)

1、第一章隨機(jī)數(shù)生成方法一、引言在C+中常用的隨機(jī)數(shù)生成方法是首先使用rand函數(shù)生成一個(gè)隨機(jī)數(shù)，然后將生成的隨機(jī)數(shù)映射到所需要的區(qū)間。但是在使用rand函數(shù)之前需要使用srand設(shè)置初始“種子”以保證每次生成的隨機(jī)數(shù)都不相同。在實(shí)際應(yīng)用中，通常使用系統(tǒng)當(dāng)前時(shí)間作為“種子” 這樣生成的隨機(jī)數(shù)更接近于實(shí)際意義的隨機(jī)數(shù)。程序1為生成指定區(qū)間的隨機(jī)數(shù)的代碼。程序1生成start到end之間的一個(gè)隨機(jī)數(shù)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;但是以上的生成算法有兩個(gè)問(wèn)題:1.rand生成的最大隨機(jī)數(shù)為32767,有時(shí)無(wú)法達(dá)到我們的要求；2每個(gè)生成的隨機(jī)數(shù)的概率未必相等，例如要生成0,30000之間的隨機(jī)數(shù)，這種做法就會(huì)導(dǎo)致后面生成的隨機(jī)數(shù)的概率偏小。在唐納德克努特(Donald Ervin Knuth)的經(jīng)典巨著計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)中，有一

3、章專(zhuān)門(mén)介紹了生成隨機(jī)數(shù)的方法。程序2為來(lái)自crafty19.3的源碼，它是對(duì)計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)中2.2.2節(jié)的實(shí)現(xiàn)。程序2生成一個(gè)32位的隨機(jī)數(shù)/*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);二、生成大范圍的隨機(jī)數(shù)通常情況下可以使用將生成的多個(gè)隨機(jī)數(shù)拼接在一起，以獲得更大范圍的隨機(jī)數(shù)。人程序3拼接生成一個(gè)32位的隨機(jī)數(shù)long r =(l on g)ra nd()<<16)|(lo ng)ra nd()<<8)&0X0000FF00L)|(lo ng)ra nd()&0X000000FFL);使用STL可以很方便的生成一個(gè)隨機(jī)序列，其中主要是同gen erate算法直接生成，程序4展示生成的過(guò)程。程序3通過(guò)STL的gen erate生成隨機(jī)序列#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算 法的調(diào)用return

10、 (ra nd()& 3)<<30)+(ra nd()<<15)+ra nd()&mask;private :un sig nedlo ng mask ;用于獲得相應(yīng)位數(shù)的隨機(jī)數(shù)的掩碼;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三、生成任意分布的隨機(jī)數(shù)一般的情況可以利用rand函數(shù)均勻的生成每個(gè)數(shù)，然后將某一區(qū)間的隨機(jī)數(shù)映射為一個(gè)數(shù)，但這種生成算法無(wú)法模擬符合某一分布的隨機(jī)數(shù)。下面以正態(tài)分布為例來(lái)說(shuō)明生成任意分布隨機(jī)數(shù)的算法。如果一個(gè)隨機(jī)數(shù)序列服從一維正態(tài)分布，那么它有如下的概率密度函數(shù)：1 _込 f(x)= e 2 v2(t其中卩，6為常數(shù)，它們分別為數(shù)學(xué)期望和均方差。圖1為卩=0=0.2時(shí)的曲線。從圖中可以看出，在卩附近的概率密度大，遠(yuǎn)離卩的地方概率密度小，我們要產(chǎn)生的隨機(jī)數(shù)要服從這種分布，就是要使產(chǎn)生的隨機(jī)數(shù)在卩附近的概率要大，遠(yuǎn)離卩處小。算法的主要思想是：在圖1的大矩形

12、中隨機(jī)產(chǎn)生點(diǎn)，這些點(diǎn)是平均分布的，如果產(chǎn)生的點(diǎn)落在概率密度曲線的下方，則認(rèn)為產(chǎn)生的點(diǎn)是符合要求的，將它們保留，如果在概率密度曲線的上方， 則認(rèn)為這些點(diǎn)不合格，將它們?nèi)コ?。如果隨機(jī)產(chǎn)生了一大批在整個(gè)矩形中均勻分布的點(diǎn)，那么被保留下來(lái)的點(diǎn)的橫坐標(biāo)就服從了正態(tài)分布?？梢栽O(shè)想，由于在卩處的f(x)的值比較大，理所當(dāng)然的在附近的點(diǎn)個(gè)數(shù)要多， 遠(yuǎn)離處的少，這從面積上就可以看出來(lái)。 我們要產(chǎn)生 的隨機(jī)數(shù)就是這里的橫坐標(biāo)。程序3為生成正態(tài)分布的程序。圖1正態(tài)分布的概率密度函數(shù)曲線程序3生成正態(tài)分布隨機(jī)數(shù)#define PI 3.14159265double Normal( double x,double mi

13、u,double sigma) / 概率密度函數(shù)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) / 產(chǎn)生正態(tài)分布隨機(jī)數(shù)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;參數(shù)說(shuō)明：doublemiu :卩，正態(tài)函數(shù)的數(shù)學(xué)期望doublesigma:，正態(tài)函數(shù)的均方差doublemin, max :表明產(chǎn)生的隨機(jī)數(shù)的范圍四、生成各不相同的隨機(jī)數(shù)通常的生成隨機(jī)數(shù)的做法是不考慮重復(fù)的，因?yàn)榧词怪貜?fù)也屬于概率意義上的正常情 況。要產(chǎn)生一定范圍內(nèi)不可重復(fù)的隨機(jī)數(shù)，最樸素的想法是把曾經(jīng)生成的隨機(jī)數(shù)保存起來(lái)作為歷史數(shù)據(jù)。將每一個(gè)新產(chǎn)生的隨機(jī)數(shù)都與歷史數(shù)據(jù)進(jìn)行比較，如果不相同則認(rèn)為產(chǎn)生了一個(gè)新的隨機(jī)數(shù)，否則丟棄后重新進(jìn)行搜索。程序5為這種思想的實(shí)現(xiàn)。程序5生成不重復(fù)的隨機(jī)數(shù)在min,

15、max區(qū)間生成num個(gè)不相同的隨機(jī)數(shù)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; 用來(lái)保存隨機(jī)生成的不重復(fù)的數(shù)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; 循環(huán)變量-1retur n result ;對(duì)于生成數(shù)量較少的隨機(jī)數(shù),這種方法簡(jiǎn)單易行,但是如果給出的范圍比較小,那么新 產(chǎn)生的隨機(jī)數(shù)就會(huì)以極大的概率與已有的數(shù)據(jù)相同。為了達(dá)到較好的一種效果，通常使用額外的空間。其主要的思想是：生成一個(gè)有序的互不相同的數(shù)列，生成一個(gè)小于序列長(zhǎng)度的隨機(jī)數(shù)，并將序列中對(duì)應(yīng)位置的元素作為結(jié)果，然后將序列最后一個(gè)元素復(fù)制到對(duì)應(yīng)位置，序列長(zhǎng)度減一，重復(fù)以上操作直到找到所有的數(shù)。程序6為以上算法的實(shí)現(xiàn)。程序6生成不重復(fù)的隨機(jī)數(shù)生成num個(gè)不相同的隨機(jī)數(shù)int *ran dom (int n um)int in dexRAND_MAX;for (int i = 0; i < RAND_MAX;