c語(yǔ)言中的隨機(jī)函數(shù)分析與生成m個(gè)不重復(fù)隨機(jī)數(shù)算法比較

1、c 語(yǔ)言中的隨機(jī)函數(shù)分析與生成 m 個(gè)不重復(fù)隨機(jī)數(shù)算法比較(轉(zhuǎn))C+&STL 2008-12-19 18:04:45 閱讀134 評(píng)論0字號(hào)：大中小訂閱一說(shuō)起隨機(jī)函數(shù)，恐怕又有人說(shuō)這是老生長(zhǎng)談了一般很多人都形成了自己的固定格式，因?yàn)殡S機(jī)數(shù)用處比較大，用的時(shí)候比較多，拿過(guò)來(lái)就用了。但是新手不這么干，他們總是抱有疑惑，我就是一個(gè)新手， 而且較菜為了讓跟我一樣的菜鳥(niǎo)看明白，我會(huì)盡量的說(shuō)得讓高手們不屑一顧（：由于可能內(nèi)容太多可能會(huì)分篇，大家見(jiàn)諒麻煩了比如所隨機(jī)數(shù)，因?yàn)楹瘮?shù)嘛，總會(huì)是確定的，確定的算法就會(huì)生成確定的結(jié)果。各種編程語(yǔ)言返回的隨機(jī)數(shù)（確切地說(shuō)是偽隨機(jī)數(shù)）實(shí)際上都是根據(jù)遞推公式計(jì)算的一組數(shù)值，

2、當(dāng)序列足夠長(zhǎng)，這組數(shù)c 的標(biāo)準(zhǔn)函數(shù)庫(kù)提供一隨機(jī)數(shù)生成器ran（stdlib.hRAND_MAX之間均勻分布的偽隨機(jī)整數(shù)（RAND_MAX 3276732767）。例如：#include #include void main()for(int i=0;i10;i+) printf(%dn,rand();0RAND_MAX之間的等概率隨機(jī)數(shù)列了。但是如果你第二次運(yùn)行的時(shí)候會(huì)發(fā)現(xiàn)輸出結(jié)果仍和第一次一樣。：（原來(lái)rand（）生成偽隨機(jī)數(shù) 時(shí)需要一個(gè)種子（計(jì)算偽隨機(jī)序列的初始數(shù)值）才行，如果種子相同就會(huì)得到相同的序列結(jié)果（這就是函數(shù)的好處 “優(yōu)點(diǎn)”列并對(duì)數(shù)據(jù)進(jìn)行處理；解密時(shí)，再利用種子數(shù)生成一個(gè)偽隨機(jī)序

3、列并對(duì)加密數(shù)據(jù)進(jìn)行還原。這樣，對(duì)于不知道種子數(shù)的人要想解密就需要多費(fèi)些事了。當(dāng)然，這種完全相同的序列對(duì)于你來(lái)說(shuō)是非常糟糕的。要解決這個(gè)問(wèn)題，需要在每次產(chǎn)生隨機(jī)序列前，先指定不同的種子，這樣計(jì)算出來(lái)的隨機(jī)序列就不會(huì)完全相同了。srand()用來(lái)設(shè)置rand()產(chǎn)生隨機(jī)數(shù)時(shí)的隨機(jī)數(shù)種子。在調(diào)用rand()函數(shù)產(chǎn)生隨機(jī)數(shù)前，必須先利用srand() 設(shè)好隨機(jī)數(shù)種子（seed）, rand()1（有人說(shuō)默認(rèn)是0，困惑中）1 ，進(jìn) rand()(C random，可是random 函數(shù)ANSI Crandomgcc,vcsrand的選擇是不是接近隨機(jī)（不存在 完全隨機(jī)Windows9x/NTFreeCe

4、ll就允許用戶(hù)指定種子數(shù)，這樣用戶(hù)如果一次游戲沒(méi)有成功，下次還可以以同樣的發(fā)牌結(jié)果再玩一次。但我們還是喜歡系統(tǒng)自動(dòng)生成最 簡(jiǎn)單的方法就是利用系統(tǒng)時(shí)間了（幾乎所有的人都這么做），因?yàn)闀r(shí)間的數(shù)值隨時(shí)間變化而變化，運(yùn)行兩 次，一般不會(huì)出現(xiàn)前一次和后一次相同的局面，time(NULL)會(huì)返回一個(gè)表示當(dāng)前系統(tǒng)時(shí)間的整數(shù)（它在time.htime()197011日到現(xiàn)在的秒數(shù)，有的說(shuō)是unix元年，不知道這 兩個(gè)是不是一天:（ ，另外有的嫌麻煩會(huì)寫(xiě)作time（0）。我們這么來(lái)寫(xiě)：srand(srand(unsigned)time(NULL);#include #include #includevoid m

5、ain()srand(int)time(0); for(int x=0;x10;x+)printf(%dn,(rand();據(jù)說(shuō)如果軟件一直開(kāi)兩天，種子會(huì)有 1/(60*60*24)個(gè)可能會(huì)重復(fù)，雖說(shuō)這對(duì)于一般人已經(jīng)絕對(duì)足夠了，但縱然人不舒服，于是我在網(wǎng)上開(kāi)到有這么寫(xiě)的：#include #include #include #includevoid main(void)int i; unsigned int seedVal; struct timeb timeBuf;ftime(&timeBuf); seedVal=(unsigned int)timeBuf.time&0 xFFFF)+(un

6、signed int)timeBlitm) (unsigned int)timeBlitm);srand(unsigned int)seedVal); for(i=0;i10;+i)printf(%6dn,rand();（下面是關(guān)于它的解釋?zhuān)乙膊皇翘靼祝眠^(guò)來(lái)大家分析一下）“ 上面的程序先是調(diào)用_ftime()來(lái)檢查當(dāng)前時(shí)間，并把它的值存入結(jié)構(gòu)成員timeBuf.time 197011_ftime()之后，在結(jié)構(gòu)timeBuf的成員millitm中還存入了當(dāng)前DOS中這個(gè)數(shù)字實(shí)際上是以百分之一秒來(lái)計(jì)算的。然后，把毫秒數(shù)和秒seedVal的取值范圍，并進(jìn)一步加強(qiáng)它

7、的隨機(jī)性，但上例用的邏輯運(yùn)算就已經(jīng)足夠了?！笨聪旅娲a：void main()for(int i=0;i100000;i+)printf（%dn,rand();為什么總是生成一個(gè)數(shù)？因?yàn)榇顺绦虍a(chǎn)生一個(gè)隨機(jī)數(shù)之前，都調(diào)用一次 srand，而由于計(jì)算機(jī)運(yùn)行很快，所以每用time 得到的時(shí)間都是一樣的（time 的時(shí)間精度較低，只有 55ms）。這樣相當(dāng)于使用同一個(gè)種子產(chǎn)生隨機(jī)序列，所以產(chǎn)生的隨機(jī)數(shù)總是相同的。把 srand 放在循環(huán)外看看：srand( (unsigned)time( NULL ) ); for(int i=0;i100000;i+)問(wèn)題解決了：）既然生成的是 0RAND_MAX

8、之間均勻分布的隨機(jī)整數(shù)（我們姑且把以上方法生成的是理想的隨機(jī)數(shù) 吧那么要生成0-x 之間(包括0 不包括的隨機(jī)數(shù)就把改成 rand()/(double)RAND_MAX*x 要生成x-y 之間（包括x 不包括y）的就是 rand()/(double)RAND_MAX*(y-x)+x了。但是如果要生0-10之間的整數(shù)很多人會(huì)這么寫(xiě)：#include #include #includevoid main()srand(int)time(0); for(int x=0;x10;x+) printf(%dn,(rand()%10);x-y 的就是 rand()%(y-x)+x?懂一點(diǎn)概率的就知道這樣寫(xiě)

9、，會(huì)使得到的數(shù)列分布不均的，但是大家確實(shí)都喜歡這么寫(xiě)x （一些游戲目標(biāo),rand(). 當(dāng)主角在地圖上走的時(shí)候動(dòng)不動(dòng)冒出三兩小兵挑釁兼找死.01，當(dāng)變量=隨機(jī)取得的數(shù)時(shí)，小兵出現(xiàn)），這樣寫(xiě)足夠了下面再討論生成 m 個(gè)小于n 的不重復(fù)隨機(jī)數(shù)的算法本人認(rèn)為算法結(jié)構(gòu)很重要，但語(yǔ)句結(jié)構(gòu)也很重要，所以我喜歡一個(gè)算法給出多個(gè)語(yǔ)句結(jié)構(gòu)最容易想到的傻瓜算法，逐個(gè)產(chǎn)生這些隨機(jī)數(shù)，每產(chǎn)生一個(gè)，都跟前面的隨機(jī)數(shù)比較，如果重復(fù)，就重新產(chǎn)生：算法一（1）for(j = 0; j m; j+) a:aj = rand() % n; for(i=0;ij;i+)if(ai=aj)goto a;goto goto 可以直接轉(zhuǎn)

10、譯，而且循環(huán)goto 可以break continue 語(yǔ)句使這些結(jié)構(gòu)實(shí)現(xiàn)成為可能，后來(lái)發(fā)現(xiàn)goto 的使用會(huì)造成維護(hù)和調(diào)試的許多麻煩，所以循環(huán)逐漸代替了goto 了，如果用 goto 還會(huì)被認(rèn)為編程修養(yǎng)不好言歸正題，把它的 goto 去掉： 算法一（2）srand(unsigned)time(NULL);j=0;while (jm)aj = rand() % n ; for(i=0;ij;i+)if(ai=aj) break; if(ij)continue;j+但是后來(lái)都建議用 for 循環(huán)，這樣可以使循環(huán)條件跟緊湊： 算法一（3）srand(unsigned)time(NULL); for

11、(j=0;jm;j+)aj=rand()%n; for(i=0;ij;i+)if(ai=aj)i=-1;aj=rand()%n;但這是個(gè)很笨的方法，且比較次數(shù)呈線(xiàn)性增長(zhǎng)，越往后次數(shù)越多另一個(gè)想法是生成一個(gè)就把它從中去掉，就可以實(shí)現(xiàn)不重復(fù)了：算法二（1）for (i=0;in;i+)ai=i+1;for(i=0;im;i+)j=rand()%(n-i);bi=aj;for (k=j;kn-i-2;k+) ak=ak+1;b是生成的隨機(jī)數(shù)列這樣做也太麻煩了，生成的直接做個(gè)標(biāo)記不就行了？ 算法三（1-1）i=rand()%m; ai=1;b0=i;for(j=1;jm;j+)for (i=rand(

12、)%m;ai=1;i=rand()%m); bj=i;ai=1;寫(xiě)緊湊一些吧，直接： 算 法 三 （1-2） for(j=0;jm;j+)for (i=rand()%m;ai=1;i=rand()%m); bj=i;ai=1;但是我看到了更簡(jiǎn)潔的：intn=某值； intan=0；for (i=1;i=n;i+)while(ax=rand()%n);ax=i;這個(gè)無(wú)循環(huán)體的 while 保證 am是初始化的 0 狀態(tài)。這生成了n 個(gè)，我們只取m 個(gè)，這太浪費(fèi)了，結(jié)合一下：int n=某值，m=int an=0,bmfor (i=1;i=n;i+)while(ax=rand()%n);bi=x;ax=1;但是總叫人不舒服，對(duì)這種算法誰(shuí)有更好的寫(xiě)法呢？這種算法越到后面，遇到已使用過(guò)的元素的可能性越高，重復(fù)次數(shù)就越多，但是當(dāng)m 較小時(shí)還是很好的：） 這都不太讓人滿(mǎn)意么？看看下面這個(gè)：算法四（1）for (i=0;i0;i-)w=rand()%i;t=ai; ai=aw; aw=t;0 n 0 n-2 個(gè)數(shù)組下標(biāo)，把這個(gè)下標(biāo)的元素值跟n-1 下標(biāo)的元素值交換，一直進(jìn)1 的元素。因此它只需要遍歷一次就能產(chǎn)生全部的隨機(jī)數(shù)。但這樣會(huì)生成 n 個(gè)小于n 的隨機(jī)數(shù)，我們只要m 個(gè)，再加兩句：for(i=0;im;i+) bi=ai;b是生成的隨機(jī)數(shù)列m 和n 算法四（2）f