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

1、c語言中的隨機函數(shù)分析與生成m個不重復(fù)隨機數(shù)算法比較（轉(zhuǎn)）C+&STL2008-12-1918:04:45閱讀134評論0字號：大中小訂閱一說起隨機函數(shù)，恐怕又有人說這是老生長談了一般很多人都形成了自己的固定格式，因為隨機數(shù)用處比較大，用的時候比較多，拿過來就用了。但是新手不這么干，他們總是抱有疑惑，我就是一個新手，而且較菜為了讓跟我一樣的菜鳥看明白，我會盡量的說得讓高手們不屑一顧（：由于可能內(nèi)容太多可能會分篇，大家見諒人計算機的好處是精確，所以它不擅長模擬信號，但它的缺點也是如此。于是在一些模擬問題上計算機遇到麻煩了比如所隨機數(shù)，因為函數(shù)嘛，總會是確定的，確定的算法就會生成確定的結(jié)果。各種編

2、程語言返回的隨機數(shù)（確切地說是偽隨機數(shù)）實際上都是根據(jù)遞推公式計算的一組數(shù)值，當(dāng)序列足夠長，這組數(shù)值近似滿足均勻分布。c的標(biāo)準(zhǔn)函數(shù)庫提供一隨機數(shù)生成器rand（定義在stdlib.h）,能返回0RAND_MAX之間均勻分布的偽隨機整數(shù)（RAND_MAX至少為32767,一般都默認(rèn)為32767）。例如：#include#includevoidmain（）for（inti=0;i10;i+）printf（%dn,rand（）;如果我們是第一次運行，而且對其不太清楚，那么它生成的基本上算是0RAND_MAX之間的等概率隨機數(shù)列了。但是如果你第二次運行的時候會發(fā)現(xiàn)輸出結(jié)果仍和第一次一樣。：（原來ran

3、d（）生成偽隨機數(shù)時需要一個種子（計算偽隨機序列的初始數(shù)值）才行，如果種子相同就會得到相同的序列結(jié)果（這就是函數(shù)的好處T-T）。這個“優(yōu)點”被有的軟件利用于加密和解密。加密時，可以用某個種子數(shù)生成一個偽隨機序列并對數(shù)據(jù)進(jìn)行處理；解密時，再利用種子數(shù)生成一個偽隨機序列并對加密數(shù)據(jù)進(jìn)行還原。這樣，對于不知道種子數(shù)的人要想解密就需要多費些事了。當(dāng)然，這種完全相同的序列對于你來說是非常糟糕的。要解決這個問題，需要在每次產(chǎn)生隨機序列前，先指定不同的種子，這樣計算出來的隨機序列就不會完全相同了。srand（）用來設(shè)置rand（）產(chǎn)生隨機數(shù)時的隨機數(shù)種子。在調(diào)用rand（）函數(shù)產(chǎn)生隨機數(shù)前，必須先利用sra

4、nd（）設(shè)好隨機數(shù)種子（seed）,如果未設(shè)隨機數(shù)種子，rand（）在調(diào)用時會自動設(shè)隨機數(shù)種子為1（有人說默認(rèn)是0，困惑中）。上面的兩個例子就是因為沒有設(shè)置隨機數(shù)種子，每次隨機數(shù)種子都自動設(shè)成相同值1，進(jìn)而導(dǎo)致rand（）所產(chǎn)生的隨機數(shù)值都一樣。（可能有人知道C語言中的隨機函數(shù)random，可是random函數(shù)并不是ANSIC標(biāo)準(zhǔn)，所以說，random函數(shù)不能在gcc,vc等編譯器下編譯通過。我們可以自己編一個A0A）我們需要使程序每一次使用的種子都不一樣，現(xiàn)在主要問題是種子srand的選擇是不是接近隨機（不存在完全隨機），你也可以人為指定種子數(shù)。Windows9x/NT的游戲FreeCell

5、就允許用戶指定種子數(shù)，這樣用戶如果一次游戲沒有成功，下次還可以以同樣的發(fā)牌結(jié)果再玩一次。但我們還是喜歡系統(tǒng)自動生成最簡單的方法就是利用系統(tǒng)時間了（幾乎所有的人都這么做），因為時間的數(shù)值隨時間變化而變化，運行兩次，一般不會出現(xiàn)前一次和后一次相同的局面，time（NULL）會返回一個表示當(dāng)前系統(tǒng)時間的整數(shù)（它在time.h中，據(jù)說time（）函數(shù)求出來的是自1970年1月1日到現(xiàn)在的秒數(shù)，有的說是unix元年，不知道這兩個是不是一天：（，另外有的嫌麻煩會寫作time（0）。我們這么來寫：#include#include#includevoidmain()srand(int)time(0);for(

6、intx=0;x10;x+)printf(%dn,(rand();據(jù)說如果軟件一直開兩天，種子會有1/(60*60*24)個可能會重復(fù)，雖說這對于一般人已經(jīng)絕對足夠了，但縱然人不舒服，于是我在網(wǎng)上開到有這么寫的：#include#include#include#includevoidmain(void)inti;unsignedintseedVal;structtimebtimeBuf;ftime(&timeBuf);seedVal=(unsignedint)timeBuf.time&0 xFFFF)+(unsignedint)timeBlitm)A(unsignedint)tim

7、eBlitm);srand(unsignedint)seedVal);for(i=0;i10;+i)printf(%6dn,rand();(下面是關(guān)于它的解釋，但我也不是太明白，引用過來大家分析一下)“上面的程序先是調(diào)用_ftime()來檢查當(dāng)前時間，并把它的值存入結(jié)構(gòu)成員timeBuf.time中，當(dāng)前時間的值從1970年1月1日開始以秒計算。在調(diào)用了_ftime()之后，在結(jié)構(gòu)timeBuf的成員millitm中還存入了當(dāng)前那一秒已經(jīng)度過的毫秒數(shù)，但在DOS中這個數(shù)字實際上是以百分之一秒來計算的。然后，把毫秒數(shù)和秒數(shù)相加，再和毫秒數(shù)進(jìn)行異或運算。當(dāng)然也可以對這兩個結(jié)構(gòu)成員進(jìn)行更

8、多的計算，以控制seedVal的取值范圍，并進(jìn)一步加強它的隨機性，但上例用的邏輯運算就已經(jīng)足夠了?！笨聪旅娲a：voidmain()for(inti=0;i100000;i+)srand(unsigned)time(NULL);printf(%dn,rand();為什么總是生成一個數(shù)？因為此程序產(chǎn)生一個隨機數(shù)之前，都調(diào)用一次srand,而由于計算機運行很快，所以每用time得到的時間都是一樣的(time的時間精度較低，只有55ms)。這樣相當(dāng)于使用同一個種子產(chǎn)生隨機序列，所以產(chǎn)生的隨機數(shù)總是相同的。把srand放在循環(huán)外看看：srand(unsigned)time(NULL);for(inti

9、=0;i100000;i+)問題解決了：)既然生成的是0RAND_MAX之間均勻分布的隨機整數(shù)(我們姑且把以上方法生成的是理想的隨機數(shù)吧)，那么要生成0-x之間(包括0不包括x)的隨機數(shù)就把rand()改成rand()/(double)RAND_MAX*x，要生成x-y之間(包括x不包括y)的就是rand()/(double)RAND_MAX*(y-x)+x了。但是如果要生0-10之間的整數(shù)很多人會這么寫：#include#include#includevoidmain()srand(int)time(0);for(intx=0;x10;x+)printf(%dn,(rand()%10);x-

10、y的就是rand()%(y-x)+x?懂一點概率的就知道這樣寫，會使得到的數(shù)列分布不均的，但是大家確實都喜歡這么寫因為在x的值比較小，RAND_MAX相對較大，而生成的數(shù)列有不算太大，又是用來解決精確度要求不高的問題(如一些游戲目標(biāo)，傳說游戲中踩地雷式的遇敵就是用rand()實現(xiàn)的.當(dāng)主角在地圖上走的時候動不動冒出三兩小兵挑釁兼找死.它的實現(xiàn)方式是設(shè)主角所立位置為0，主角每走一步，變量加1，當(dāng)變量=隨機取得的數(shù)時，小兵出現(xiàn))，這樣寫足夠了下面再討論生成m個小于n的不重復(fù)隨機數(shù)的算法本人認(rèn)為算法結(jié)構(gòu)很重要，但語句結(jié)構(gòu)也很重要，所以我喜歡一個算法給出多個語句結(jié)構(gòu)最容易想到的傻瓜算法，逐個產(chǎn)生這些隨

11、機數(shù)，每產(chǎn)生一個，都跟前面的隨機數(shù)比較，如果重復(fù)，就重新產(chǎn)生：算法一(1)srand(unsigned)time(NULL);for(j=0;jm;j+)a:aj=rand()%n;for(i=0;ij;i+)if(ai=aj)gotoa;很早的時候?qū)W編程都喜歡用goto語句，因為過去算法是用流程圖表示的，用goto可以直接轉(zhuǎn)譯，而且循環(huán)語句發(fā)展不完善，僅僅是作為條件分支的一個補充，如果條件分支箭頭向上就是一個循環(huán)，而且goto可以實現(xiàn)過去循環(huán)所不能實現(xiàn)的結(jié)構(gòu)，形成很巧妙的循環(huán)交叉。所以過去一般認(rèn)為有兩種結(jié)構(gòu)，順序和分支，循環(huán)是分支的特殊情況。但是break和continue語句使這些結(jié)構(gòu)實現(xiàn)

12、成為可能，后來發(fā)現(xiàn)goto的使用會造成維護和調(diào)試的許多麻煩，所以循環(huán)逐漸代替了goto,使程序更有層次?，F(xiàn)在編程不建議用goto了，如果用goto還會被認(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+但是后來都建議用for循環(huán)，這樣可以使循環(huán)條件跟緊湊：算法一(3)srand(unsigned)time(NULL);for(j=0;jm;j+)aj=rand()%n;for(i=0;ij;i+

13、)if(ai=aj)i=-1;aj=rand()%n;但這是個很笨的方法，且比較次數(shù)呈線性增長，越往后次數(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是生成的隨機數(shù)列這樣做也太麻煩了，生成的直接做個標(biāo)記不就行了？算法三(1-1)i=rand()%m;ai=1;b0=i;for(j=1;jm;j+)for(i=rand()%m;ai=1;i=rand()%m);bj=i;ai=1;寫緊湊一些吧，直接：算法

14、三(1-2)for(j=0;jm;j+)for(i=rand()%m;ai=1;i=rand()%m);bj=i;ai=1;但是我看到了更簡潔的：intn=某值；intan=0；for(i=1;i=n;i+)while(ax=rand()%n);ax=i;這個無循環(huán)體的while保證am是初始化的0狀態(tài)。這生成了n個，我們只取m個，這太浪費了，結(jié)合一下：intn=某值，m=某值；intan=0,bmfor(i=1;i=n;i+)while(ax=rand()%n);bi=x;ax=1;但是總叫人不舒服，對這種算法誰有更好的寫法呢？這種算法越到后面，遇到已使用過的元素的可能性越高，重復(fù)次數(shù)就越多，但是當(dāng)m較小時還是很好的：)這都不太讓人滿意么？看看下面這個：算法四(1)for(i=0;i0;i-)w=rand()%i;t=ai;ai=aw;aw=t;這個算法很不錯，有人會懷疑其隨機性，但個人認(rèn)為是沒問題的，首先第二行按順序用0到n填滿整個數(shù)組；第三行，是隨機產(chǎn)生從0到n-2個數(shù)組下標(biāo)，把這個下標(biāo)的元素值跟n-1下標(biāo)的元素值交換，一直進(jìn)行到下標(biāo)為1的元素。因此它只需要遍歷一次就能產(chǎn)生全部的隨機數(shù)。但這樣會生成n個小于n的隨機數(shù)，我們只要m個，再加兩句：for(i=0;im;i+)bi=ai;