愛華網(wǎng)c語言中的隨機(jī)函數(shù)分析與生成m個(gè)不重復(fù)隨機(jī)數(shù)算法比較
一說起隨機(jī)函數(shù)，恐怕又有人說這是老生長談了……一般很多人都形成了自己的固定格式，因?yàn)殡S機(jī)數(shù)用處比較大，用的時(shí)候比較多，拿過來就用了。但是新手不這么干，他們總是抱有疑惑，我就是一個(gè)新手，而且較菜……為了讓跟我一樣的菜鳥看明白，我會(huì)盡量的說得讓高手們不屑一顧（：由于可能內(nèi)容太多可能會(huì)分篇，大家見諒^
計(jì)算機(jī)的好處是精確，所以它不擅長模擬信號(hào)，但它的缺點(diǎn)也是如此。于是在一些模擬問題上計(jì)算機(jī)遇到麻煩了……比如所隨機(jī)數(shù)，因?yàn)楹瘮?shù)嘛，計(jì)算過程總會(huì)是確定的，確定的算法就會(huì)生成確定的結(jié)果。各種編程語言返回的隨機(jī)數(shù)（確切地說是偽隨機(jī)數(shù)）實(shí)際上都是根據(jù)遞推公式計(jì)算的一組數(shù)值，當(dāng)序列足夠長，這組數(shù)值近似滿足均勻分布。c的標(biāo)準(zhǔn)函數(shù)庫提供一隨機(jī)數(shù)生成器rand（定義在stdlib.h），能返回0－RAND_MAX之間均勻分布的偽隨機(jī)整數(shù)（RAND_MAX至少為32767，一般都默認(rèn)為32767）。
例如：
#include<stdio.h>
#include<stdlib.h>
void main()
{
for(int i=0;i<10;i+)
printf("%dn",rand());
}
如果我們是第一次運(yùn)行，而且對(duì)其不太清楚，那么它生成的基本上算是0－RAND_MAX之間的等概率隨機(jī)數(shù)列了。但是如果你第二次運(yùn)行的時(shí)候會(huì)發(fā)現(xiàn)輸出結(jié)果仍和第一次一樣。：（原來rand（）生成偽隨機(jī)數(shù)時(shí)需要一個(gè)種子（計(jì)算偽隨機(jī)序列的初始數(shù)值）才行，如果種子相同就會(huì)得到相同的序列結(jié)果（這就是函數(shù)的好處T_T）。這個(gè)“優(yōu)點(diǎn)”被有的軟件利用于加密和解密。加密時(shí)，可以用某個(gè)種子數(shù)生成一個(gè)偽隨機(jī)序列并對(duì)數(shù)據(jù)進(jìn)行處理；解密時(shí)，再利用種子數(shù)生成一個(gè)偽隨機(jī)序列并對(duì)加密數(shù)據(jù)進(jìn)行還原。這樣，對(duì)于不知道種子數(shù)的人要想解密就需要多費(fèi)些事了。當(dāng)然，這種完全相同的序列對(duì)于你來說是非常糟糕的。要解決這個(gè)問題，需要在每次產(chǎn)生隨機(jī)序列前，先指定不同的種子，這樣計(jì)算出來的隨機(jī)序列就不會(huì)完全相同了。
srand()用來設(shè)置rand()產(chǎn)生隨機(jī)數(shù)時(shí)的隨機(jī)數(shù)種子。在調(diào)用rand()函數(shù)產(chǎn)生隨機(jī)數(shù)前，必須先利用srand()設(shè)好隨機(jī)數(shù)種子（seed）,如果未設(shè)隨機(jī)數(shù)種子,rand()在調(diào)用時(shí)會(huì)自動(dòng)設(shè)隨機(jī)數(shù)種子為1（有人說默認(rèn)是0，困惑中）。上面的兩個(gè)例子就是因?yàn)闆]有設(shè)置隨機(jī)數(shù)種子，每次隨機(jī)數(shù)種子都自動(dòng)設(shè)成相同值1，進(jìn)而導(dǎo)致rand()所產(chǎn)生的隨機(jī)數(shù)值都一樣。(可能有人知道C語言中的隨機(jī)函數(shù)random，可是random函數(shù)并不是ANSIC標(biāo)準(zhǔn)，所以說，random函數(shù)不能在gcc,vc等編譯器下編譯通過。我們可以自己編一個(gè)^0^）我們需要使程序每一次使用的種子都不一樣，現(xiàn)在主要問題是種子srand的選擇是不是接近隨機(jī)（不存在完全隨機(jī)），你也可以人為指定種子數(shù)。Windows9x/NT的游戲FreeCell就允許用戶指定種子數(shù)，這樣用戶如果一次游戲沒有成功，下次還可以以同樣的發(fā)牌結(jié)果再玩一次。但我們還是喜歡系統(tǒng)自動(dòng)生成……最簡單的方法就是利用系統(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.h中，據(jù)說time()函數(shù)求出來的是自1970年1月1日到現(xiàn)在的秒數(shù)，有的說是unix元年，不知道這兩個(gè)是不是一天……:（，另外有的嫌麻煩會(huì)寫作time（0））。我們這么來寫：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void main()
{
srand((int)time(0));
for(int x=0;x<10;x++)
printf("%dn",(rand());
}
據(jù)說如果軟件一直開兩天，種子會(huì)有1/(60*60*24)個(gè)可能會(huì)重復(fù)，雖說這對(duì)于一般人已經(jīng)絕對(duì)足夠了，但縱然人不舒服，于是我在網(wǎng)上開到有這么寫的：
#include<stdio.h>
#include<stdlib.h>
#include<sys/types.h>
#include<sys/timeb.h>
void main(void)
{
int i;
unsigned intseedVal;
struct timebtimeBuf;
ftime(&timeBuf);
seedVal=((((unsignedint)timeBuf.time&0xFFFF)+
(unsigned int)timeBuf.millitm)^
(unsigned int)timeBuf.millitm);
srand((unsigned int)seedVal);
for(i=0;i<10;++i)
printf("mn",rand());
}
（下面是關(guān)于它的解釋，但我也不是太明白，引用過來大家分析一下）
“上面的程序先是調(diào)用_ftime()來檢查當(dāng)前時(shí)間，并把它的值存入結(jié)構(gòu)成員timeBuf.time中，當(dāng)前時(shí)間的值從1970年1月1日開始以秒計(jì)算。在調(diào)用了_ftime()之后，在結(jié)構(gòu)timeBuf的成員millitm中還存入了當(dāng)前那一秒已經(jīng)度過的毫秒數(shù)，但在DOS中這個(gè)數(shù)字實(shí)際上是以百分之一秒來計(jì)算的。然后，把毫秒數(shù)和秒數(shù)相加，再和毫秒數(shù)進(jìn)行異或運(yùn)算。當(dāng)然也可以對(duì)這兩個(gè)結(jié)構(gòu)成員進(jìn)行更多的計(jì)算，以控制seedVal的取值范圍，并進(jìn)一步加強(qiáng)它的隨機(jī)性，但上例用的邏輯運(yùn)算就已經(jīng)足夠了。”
看下面代碼：
void main()
{
for(int i=0;i<100000;i++)
{
srand( (unsigned)time( NULL ) );
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;i<100000;i++)
問題解決了：）
既然生成的是0－RAND_MAX之間均勻分布的隨機(jī)整數(shù)（我們姑且把以上方法生成的是理想的隨機(jī)數(shù)吧），那么要生成0-x之間(包括0不包括x)的隨機(jī)數(shù)就把rand（）改成rand()/(double)RAND_MAX*x ，要生成x-y之間（包括x不包括y）的就是rand()/(double)RAND_MAX*(y-x)+x了。但是如果要生0-10之間的整數(shù)很多人會(huì)這么寫：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void main()
{
srand((int)time(0));
for(int x=0;x<10;x++)
printf("%dn",(rand());
}
那么生成x到y(tǒng)之間（包括x不包括y）的隨機(jī)數(shù)就是 rand()%(y-x)+x
???懂一點(diǎn)概率的就知道這樣寫，會(huì)使得到的數(shù)列分布不均的，但是大家確實(shí)都喜歡這么寫……因?yàn)樵趚的值比較小，RAND_MAX相對(duì)較大，而生成的數(shù)列有不算太大，又是用來解決精確度要求不高的問題（如一些游戲目標(biāo),傳說游戲中踩地雷式的遇敵就是用rand()實(shí)現(xiàn)的.當(dāng)主角在地圖上走的時(shí)候動(dòng)不動(dòng)冒出三兩小兵挑釁兼找死.它的實(shí)現(xiàn)方式是設(shè)主角所立位置為0，主角每走一步，變量加1，當(dāng)變量==隨機(jī)取得的數(shù)時(shí)，小兵出現(xiàn)），這樣寫足夠了……
下面再討論生成m個(gè)小于n的不重復(fù)隨機(jī)數(shù)的算法
更確切的說是生成n以內(nèi)的m個(gè)不重復(fù)的隨機(jī)整數(shù)（m<=n）。通俗點(diǎn)講就是不放回隨機(jī)抽樣……當(dāng)m=n的時(shí)候，這種算法會(huì)被稱為洗牌算法，當(dāng)然，當(dāng)m<n的時(shí)候，有時(shí)候習(xí)慣上稱其為洗牌算法……
本人認(rèn)為算法結(jié)構(gòu)很重要，但語句結(jié)構(gòu)也很重要，所以我喜歡一個(gè)算法給出多個(gè)語句結(jié)構(gòu)……
最容易想到的傻瓜算法，逐個(gè)產(chǎn)生這些隨機(jī)數(shù)，每產(chǎn)生一個(gè)，都跟前面的隨機(jī)數(shù)比較，如果重復(fù)，就重新產(chǎn)生：
算法一（1）
srand((unsigned)time(NULL));
for(j = 0; j < m; j++) {
a:a[j] = rand() % n;
for(i=0;i<j;i++){if(a[i]==a[j])goto a;}
很早的時(shí)候?qū)W編程都喜歡用goto語句，因?yàn)檫^去算法是用流程圖表示的，用goto可以直接轉(zhuǎn)譯，而且循環(huán)語句發(fā)展不完善，僅僅是作為條件分支的一個(gè)補(bǔ)充，如果條件分支箭頭向上就是一個(gè)循環(huán)，而且goto可以實(shí)現(xiàn)過去循環(huán)所不能實(shí)現(xiàn)的結(jié)構(gòu)，形成很巧妙的循環(huán)交叉。所以過去一般認(rèn)為有兩種結(jié)構(gòu)，順序和分支，循環(huán)是分支的特殊情況。但是break和continue語句使這些結(jié)構(gòu)實(shí)現(xiàn)成為可能，后來發(fā)現(xiàn)goto的使用會(huì)造成維護(hù)和調(diào)試的許多麻煩，所以循環(huán)逐漸代替了goto，使程序更有層次?，F(xiàn)在編程不建議用goto了，如果用goto還會(huì)被認(rèn)為編程修養(yǎng)不好……
（幾天前聽說有的地方都已經(jīng)不提倡使用break和continue了，而且還不提倡中途return，替代方法是使用flag變量和if來讓原本使用break或continue中斷執(zhí)行的代碼排除執(zhí)行……不過個(gè)人覺得這種提倡有點(diǎn)勉強(qiáng)……盡管這使得函數(shù)出口變得更加統(tǒng)一……）
言歸正題，把它的goto去掉：
算法一（2）
srand((unsigned)time(NULL));
j=0;
while (j<m)
{
a[j] = rand() % n ;
for(i=0;i<j;i++){if(a[i]==a[j]) break; }
if(i<j)continue;
j++
}
但是后來都建議用for循環(huán)，這樣可以使循環(huán)條件跟緊湊：
算法一（3）
srand((unsigned)time(NULL));
for(j=0;j<m;j++)
{a[j]=rand()%n;
for(i=0;i<j;i++)
{if(a[i]==a[j])
{i=-1;a[j]=rand()%n;}
}
}
但這是個(gè)很笨的方法，且比較次數(shù)呈線性增長，越往后次數(shù)越多……另一個(gè)想法是生成一個(gè)就把它從中去掉，就可以實(shí)現(xiàn)不重復(fù)了：
算法二（1）
for (i=0;i<n;i++)
a[i]=i+1;
for(i=0;i<m;i++)
{j=rand()%(n-i);
b[i]=a[j];
for (k=j;k<n-i-2;k++)
a[k]=a[k+1];
}
b[]是生成的隨機(jī)數(shù)列
這樣做也太麻煩了，生成的直接做個(gè)標(biāo)記不就行了？
算法三（1-1）
i=rand()%m;
a[i]=1;b[0]=i;
for(j=1;j<m;j++)
{for (i=rand()%m;a[i]==1;i=rand()%m);
b[j]=i;a[i]=1;
}
寫緊湊一些吧，直接：
算法三（1-2）
for(j=0;j<m;j++)
{for (i=rand()%m;a[i]==1;i=rand()%m);
b[j]=i;a[i]=1;
}
但是我看到了更簡潔的：
int n=某值；
int a[n]={0}；
for (i=1;i<=n;i++)
{while(a[x=rand()%n]);
a[x]=i;
}
這個(gè)無循環(huán)體的while保證a[m]是初始化的0狀態(tài)。這生成了n個(gè)，我們只取m個(gè)，這太浪費(fèi)了，結(jié)合一下：
int n=某值，m=某值；
int a[n]={0},b[m]
for (i=1;i<=n;i++)
{while(a[x=rand()%n]);
b[i]=x;a[x]=1;
}
但是總叫人不舒服，對(duì)這種算法誰有更好的寫法呢？
（傳說當(dāng)n較大時(shí)，算法一和算法三有使程序陷入死循環(huán)的風(fēng)險(xiǎn)）
這種算法越到后面，遇到已使用過的元素的可能性越高，重復(fù)次數(shù)就越多，但是當(dāng)m較小時(shí)還是很好的：）
這都不太讓人滿意么？看看下面這個(gè)：
算法四（1）
for (i=0;i<n;i++)
a[i]=i+1;
for (i=n-1;i>0;i--)
{w=rand()%(i+1);
t=a[i];
a[i]=a[w];
a[w]=t;
}
這個(gè)算法很不錯(cuò)，有人會(huì)懷疑其隨機(jī)性，但個(gè)人認(rèn)為是沒問題的，首先第二行按順序用0到n填滿整個(gè)數(shù)組；第三行，是隨機(jī)產(chǎn)生n-1個(gè)1到i（包括1也包括i）的數(shù)組下標(biāo)，把這個(gè)下標(biāo)的元素值跟下標(biāo)為i的元素值交換，一直進(jìn)行到下標(biāo)為1的元素。因此它只需要遍歷一次就能產(chǎn)生全部的隨機(jī)數(shù)。
但這樣會(huì)生成n個(gè)小于n的隨機(jī)數(shù)，也就是說這其實(shí)是個(gè)洗牌算法，但是我們只要m個(gè)，再加兩句：
for(i=0;i<m;i++)
b[i]=a[i];
b[]是生成的隨機(jī)數(shù)列
如果m和n很接近的話或者相等是最好，但可能不是……那改一下：
算法四（2）
for (i=0;i<n;i++)
a[i]=i+1;
for (i=0;i<m;i++)
{w=rand()%n;
t=a[i];
a[i]=a[w];
a[w]=t;
}
但是條件反過來了，如果m遠(yuǎn)小于n還行，如果接近，其隨機(jī)性就存在問題了（為什么？因?yàn)榭傮w在抽樣過程中是減小的），再改一下：
算法四（3）
for (i=0;i<n;i++)
a[i]=i+1;
for (i=0;i<m;i++)
{w=rand()%(n-i)+i;
t=a[i];
a[i]=a[w];
a[w]=t;
}
這樣可以萬無一失了……
上面的算法想到的都是在a[0]到a[m-1]中存的自然是我們想要的隨機(jī)數(shù)……當(dāng)然也可以反過來取……其實(shí)算法四（1）快要成功了……
算法四（4）
for (i=0;i<n;i++)
a[i]=i+1;
for (i=n-1;i>n-m-1;i--)
{w=rand()%(i+1);
t=a[i];
a[i]=a[w];
a[w]=t;
}
坑爹呀！這跟算法四（1）好像基本一樣嘛！?。。ê冒?，我承認(rèn)其實(shí)我是直接復(fù)制過來的……）但是有一點(diǎn)不太一樣……呃……好吧，其實(shí)這點(diǎn)不一樣也沒有什么不一樣的……因?yàn)樗惴ㄋ模?）生成的是n個(gè)，這個(gè)生成的是m個(gè)，自然在循環(huán)條件上有點(diǎn)小差異了……但是……還是有一點(diǎn)不一樣啊……那就是……這m個(gè)隨機(jī)數(shù)生成在a數(shù)組的后面……從a[n-1]和a[n-m]就是我們想要的隨機(jī)數(shù)……如果你非要取出來，可能是這樣：
for(i=0;i<m;i++)
b[i]=a[n-i-1];
這就是所謂一念之差啊……
之前這篇博文因?yàn)橐荒钪?，算法四?）少了個(gè)"+1",結(jié)果，導(dǎo)致生成的隨機(jī)數(shù)有問題：生成的隨機(jī)數(shù)的頻數(shù)分布矩陣的對(duì)角線全是0。但是這個(gè)問題卻一直未被人發(fā)現(xiàn)，直到兩年后，樓下有位熱心的新浪網(wǎng)友發(fā)現(xiàn)了這個(gè)問題，而這個(gè)問題也直到博文發(fā)表三年后的今天才被更正過來……悲劇啊……我希望這個(gè)“+1”不會(huì)誤導(dǎo)太多的網(wǎng)友……但是對(duì)于那些沒有考究過本文就轉(zhuǎn)發(fā)并且還不標(biāo)明轉(zhuǎn)發(fā)出處的那些網(wǎng)友，本人就無能為力了……
【加粗字體 為2011年11月25日0點(diǎn)34分重新編輯添加】
